mono/metadata/mono-mlist.c

   1 /*
   2  * mono-mlist.c: Managed object list implementation
   3  *
   4  * Author:
   5  *   Paolo Molaro (lupus@ximian.com)
   6  *
   7  * Copyright 2006-2009 Novell, Inc (http://www.novell.com)
   8  */
   9
  10 #include "mono/metadata/mono-mlist.h"
  11 #include "mono/metadata/appdomain.h"
  12 #include "mono/metadata/class-internals.h"
  13 #include "mono/metadata/object-internals.h"
  14
  15 /* matches the System.MonoListItem object*/
  16 struct _MonoMList {
  17         MonoObject object;
  18         MonoMList *next;
  19         MonoObject *data;
  20 };
  21
  22 /*
  23  * note: we only allocate in the root domain: this lists are
  24  * not exposed to managed code
  25  */
  26 static MonoVTable *monolist_item_vtable = NULL;
  27
  28 /**
  29  * mono_mlist_alloc:
  30  * @data: object to use as data
  31  *
  32  * Allocates a new managed list node with @data as the contents.
  33  * A managed list node also represents a singly-linked list.
  34  * Managed lists are garbage collected, so there is no free routine
  35  * and the user is required to keep references to the managed list
  36  * to prevent it from being garbage collected.
  37  */
  38 MonoMList*
  39 mono_mlist_alloc (MonoObject *data)
  40 {
  41         MonoError error;
  42         MonoMList* res;
  43         if (!monolist_item_vtable) {
  44                 MonoClass *klass = mono_class_load_from_name (mono_defaults.corlib, "System", "MonoListItem");
  45                 monolist_item_vtable = mono_class_vtable (mono_get_root_domain (), klass);
  46                 g_assert (monolist_item_vtable);
  47         }
  48         res = (MonoMList*)mono_object_new_fast_checked (monolist_item_vtable, &error);
  49         mono_error_raise_exception (&error);
  50         MONO_OBJECT_SETREF (res, data, data);
  51         return res;
  52 }
  53
  54 /**
  55  * mono_mlist_get_data:
  56  * @list: the managed list node
  57  *
  58  * Get the object stored in the list node @list.
  59  */
  60 MonoObject*
  61 mono_mlist_get_data (MonoMList* list)
  62 {
  63         return list->data;
  64 }
  65
  66 /**
  67  * mono_mlist_set_data:
  68  * @list: the managed list node
  69  *
  70  * Set the object content in the list node @list.
  71  */
  72 void
  73 mono_mlist_set_data (MonoMList* list, MonoObject *data)
  74 {
  75         MONO_OBJECT_SETREF (list, data, data);
  76 }
  77
  78 /**
  79  * mono_mlist_set_next:
  80  * @list: a managed list node
  81  * @next: list node that will be next for the @list node.
  82  *
  83  * Set next node for @list to @next.
  84  */
  85 MonoMList *
  86 mono_mlist_set_next (MonoMList* list, MonoMList *next)
  87 {
  88         if (!list)
  89                 return next;
  90
  91         MONO_OBJECT_SETREF (list, next, next);
  92         return list;
  93 }
  94
  95 /**
  96  * mono_mlist_length:
  97  * @list: the managed list
  98  *
  99  * Get the number of items in the list @list.
 100  * Since managed lists are singly-linked, this operation takes O(n) time.
 101  */
 102 int
 103 mono_mlist_length (MonoMList* list)
 104 {
 105         int len = 0;
 106         while (list) {
 107                 list = list->next;
 108                 ++len;
 109         }
 110         return len;
 111 }
 112
 113 /**
 114  * mono_mlist_next:
 115  * @list: the managed list node
 116  *
 117  * Returns the next managed list node starting from @list.
 118  */
 119 MonoMList*
 120 mono_mlist_next (MonoMList* list)
 121 {
 122         return list->next;
 123 }
 124
 125 /**
 126  * mono_mlist_last:
 127  * @list: the managed list node
 128  *
 129  * Returns the last managed list node in list @list.
 130  * Since managed lists are singly-linked, this operation takes O(n) time.
 131  */
 132 MonoMList*
 133 mono_mlist_last (MonoMList* list)
 134 {
 135         if (list) {
 136                 while (list->next)
 137                         list = list->next;
 138                 return list;
 139         }
 140         return NULL;
 141 }
 142
 143 /**
 144  * mono_mlist_prepend:
 145  * @list: the managed list
 146  * @data: the object to add to the list
 147  *
 148  * Allocate a new list node with @data as content and prepend it
 149  * to the list @list. @list can be NULL.
 150  */
 151 MonoMList*
 152 mono_mlist_prepend (MonoMList* list, MonoObject *data)
 153 {
 154         MonoMList* res = mono_mlist_alloc (data);
 155         if (list)
 156                 MONO_OBJECT_SETREF (res, next, list);
 157         return res;
 158 }
 159
 160 /**
 161  * mono_mlist_append:
 162  * @list: the managed list
 163  * @data: the object to add to the list
 164  *
 165  * Allocate a new list node with @data as content and append it
 166  * to the list @list. @list can be NULL.
 167  * Since managed lists are singly-linked, this operation takes O(n) time.
 168  */
 169 MonoMList*
 170 mono_mlist_append (MonoMList* list, MonoObject *data)
 171 {
 172         MonoMList* res = mono_mlist_alloc (data);
 173         if (list) {
 174                 MonoMList* last = mono_mlist_last (list);
 175                 MONO_OBJECT_SETREF (last, next, res);
 176                 return list;
 177         } else {
 178                 return res;
 179         }
 180 }
 181
 182 static MonoMList*
 183 find_prev (MonoMList* list, MonoMList *item)
 184 {
 185         MonoMList* prev = NULL;
 186         while (list) {
 187                 if (list == item)
 188                         break;
 189                 prev = list;
 190                 list = list->next;
 191         }
 192         return prev;
 193 }
 194
 195 /**
 196  * mono_mlist_remove_item:
 197  * @list: the managed list
 198  * @data: the object to remove from the list
 199  *
 200  * Remove the list node @item from the managed list @list.
 201  * Since managed lists are singly-linked, this operation can take O(n) time.
 202  */
 203 MonoMList*
 204 mono_mlist_remove_item (MonoMList* list, MonoMList *item)
 205 {
 206         MonoMList* prev;
 207         if (list == item) {
 208                 list = item->next;
 209                 item->next = NULL;
 210                 return list;
 211         }
 212         prev = find_prev (list, item);
 213         if (prev) {
 214                 MONO_OBJECT_SETREF (prev, next, item->next);
 215                 item->next = NULL;
 216                 return list;
 217         } else {
 218                 /* not found */
 219                 return list;
 220         }
 221 }
 222