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  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   9  */
  10
  11 #include "mono/metadata/mono-mlist.h"
  12 #include "mono/metadata/appdomain.h"
  13 #include "mono/metadata/class-internals.h"
  14 #include "mono/metadata/object-internals.h"
  15
  16
  17 static
  18 MonoMList*  mono_mlist_alloc_checked       (MonoObject *data, MonoError *error);
  19
  20
  21 /* matches the System.MonoListItem object*/
  22 struct _MonoMList {
  23         MonoObject object;
  24         MonoMList *next;
  25         MonoObject *data;
  26 };
  27
  28 /*
  29  * note: we only allocate in the root domain: this lists are
  30  * not exposed to managed code
  31  */
  32 static MonoVTable *monolist_item_vtable = NULL;
  33
  34 /**
  35  * mono_mlist_alloc:
  36  * @data: object to use as data
  37  *
  38  * Allocates a new managed list node with @data as the contents.
  39  * A managed list node also represents a singly-linked list.
  40  * Managed lists are garbage collected, so there is no free routine
  41  * and the user is required to keep references to the managed list
  42  * to prevent it from being garbage collected.
  43  */
  44 MonoMList*
  45 mono_mlist_alloc (MonoObject *data)
  46 {
  47         MonoError error;
  48         MonoMList *result = mono_mlist_alloc_checked (data, &error);
  49         mono_error_cleanup (&error);
  50         return result;
  51 }
  52
  53 /**
  54  * mono_mlist_alloc_checked:
  55  * @data: object to use as data
  56  * @error: set on error
  57  *
  58  * Allocates a new managed list node with @data as the contents.  A
  59  * managed list node also represents a singly-linked list.  Managed
  60  * lists are garbage collected, so there is no free routine and the
  61  * user is required to keep references to the managed list to prevent
  62  * it from being garbage collected. On failure returns NULL and sets
  63  * @error.
  64  */
  65 MonoMList*
  66 mono_mlist_alloc_checked (MonoObject *data, MonoError *error)
  67 {
  68         mono_error_init (error);
  69         MonoMList* res;
  70         if (!monolist_item_vtable) {
  71                 MonoClass *klass = mono_class_load_from_name (mono_defaults.corlib, "System", "MonoListItem");
  72                 monolist_item_vtable = mono_class_vtable (mono_get_root_domain (), klass);
  73                 g_assert (monolist_item_vtable);
  74         }
  75         res = (MonoMList*)mono_object_new_fast_checked (monolist_item_vtable, error);
  76         return_val_if_nok (error, NULL);
  77         MONO_OBJECT_SETREF (res, data, data);
  78         return res;
  79 }
  80
  81 /**
  82  * mono_mlist_get_data:
  83  * @list: the managed list node
  84  *
  85  * Get the object stored in the list node @list.
  86  */
  87 MonoObject*
  88 mono_mlist_get_data (MonoMList* list)
  89 {
  90         return list->data;
  91 }
  92
  93 /**
  94  * mono_mlist_set_data:
  95  * @list: the managed list node
  96  *
  97  * Set the object content in the list node @list.
  98  */
  99 void
 100 mono_mlist_set_data (MonoMList* list, MonoObject *data)
 101 {
 102         MONO_OBJECT_SETREF (list, data, data);
 103 }
 104
 105 /**
 106  * mono_mlist_set_next:
 107  * @list: a managed list node
 108  * @next: list node that will be next for the @list node.
 109  *
 110  * Set next node for @list to @next.
 111  */
 112 MonoMList *
 113 mono_mlist_set_next (MonoMList* list, MonoMList *next)
 114 {
 115         if (!list)
 116                 return next;
 117
 118         MONO_OBJECT_SETREF (list, next, next);
 119         return list;
 120 }
 121
 122 /**
 123  * mono_mlist_length:
 124  * @list: the managed list
 125  *
 126  * Get the number of items in the list @list.
 127  * Since managed lists are singly-linked, this operation takes O(n) time.
 128  */
 129 int
 130 mono_mlist_length (MonoMList* list)
 131 {
 132         int len = 0;
 133         while (list) {
 134                 list = list->next;
 135                 ++len;
 136         }
 137         return len;
 138 }
 139
 140 /**
 141  * mono_mlist_next:
 142  * @list: the managed list node
 143  *
 144  * Returns the next managed list node starting from @list.
 145  */
 146 MonoMList*
 147 mono_mlist_next (MonoMList* list)
 148 {
 149         return list->next;
 150 }
 151
 152 /**
 153  * mono_mlist_last:
 154  * @list: the managed list node
 155  *
 156  * Returns the last managed list node in list @list.
 157  * Since managed lists are singly-linked, this operation takes O(n) time.
 158  */
 159 MonoMList*
 160 mono_mlist_last (MonoMList* list)
 161 {
 162         if (list) {
 163                 while (list->next)
 164                         list = list->next;
 165                 return list;
 166         }
 167         return NULL;
 168 }
 169
 170 /**
 171  * mono_mlist_prepend:
 172  * @list: the managed list
 173  * @data: the object to add to the list
 174  *
 175  * Allocate a new list node with @data as content and prepend it
 176  * to the list @list. @list can be NULL.
 177  */
 178 MonoMList*
 179 mono_mlist_prepend (MonoMList* list, MonoObject *data)
 180 {
 181         MonoError error;
 182         MonoMList *result = mono_mlist_prepend_checked (list, data, &error);
 183         mono_error_cleanup (&error);
 184         return result;
 185 }
 186
 187 /**
 188  * mono_mlist_prepend_checked:
 189  * @list: the managed list
 190  * @data: the object to add to the list
 191  * @error: set on error
 192  *
 193  * Allocate a new list node with @data as content and prepend it to
 194  * the list @list. @list can be NULL. On failure returns NULL and sets
 195  * @error.
 196  */
 197 MonoMList*
 198 mono_mlist_prepend_checked (MonoMList* list, MonoObject *data, MonoError *error)
 199 {
 200         mono_error_init (error);
 201         MonoMList* res = mono_mlist_alloc_checked (data, error);
 202         return_val_if_nok (error, NULL);
 203
 204         if (list)
 205                 MONO_OBJECT_SETREF (res, next, list);
 206         return res;
 207 }
 208
 209 /**
 210  * mono_mlist_append:
 211  * @list: the managed list
 212  * @data: the object to add to the list
 213  *
 214  * Allocate a new list node with @data as content and append it
 215  * to the list @list. @list can be NULL.
 216  * Since managed lists are singly-linked, this operation takes O(n) time.
 217  */
 218 MonoMList*
 219 mono_mlist_append (MonoMList* list, MonoObject *data)
 220 {
 221         MonoError error;
 222         MonoMList *result = mono_mlist_append_checked (list, data, &error);
 223         mono_error_cleanup (&error);
 224         return result;
 225 }
 226
 227 /**
 228  * mono_mlist_append_checked:
 229  * @list: the managed list
 230  * @data: the object to add to the list
 231  * @error: set on error
 232  *
 233  * Allocate a new list node with @data as content and append it
 234  * to the list @list. @list can be NULL.
 235  * Since managed lists are singly-linked, this operation takes O(n) time.
 236  * On failure returns NULL and sets @error.
 237  */
 238 MonoMList*
 239 mono_mlist_append_checked (MonoMList* list, MonoObject *data, MonoError *error)
 240 {
 241         mono_error_init (error);
 242         MonoMList* res = mono_mlist_alloc_checked (data, error);
 243         return_val_if_nok (error, NULL);
 244
 245         if (list) {
 246                 MonoMList* last = mono_mlist_last (list);
 247                 MONO_OBJECT_SETREF (last, next, res);
 248                 return list;
 249         } else {
 250                 return res;
 251         }
 252 }
 253
 254 static MonoMList*
 255 find_prev (MonoMList* list, MonoMList *item)
 256 {
 257         MonoMList* prev = NULL;
 258         while (list) {
 259                 if (list == item)
 260                         break;
 261                 prev = list;
 262                 list = list->next;
 263         }
 264         return prev;
 265 }
 266
 267 /**
 268  * mono_mlist_remove_item:
 269  * @list: the managed list
 270  * @data: the object to remove from the list
 271  *
 272  * Remove the list node @item from the managed list @list.
 273  * Since managed lists are singly-linked, this operation can take O(n) time.
 274  */
 275 MonoMList*
 276 mono_mlist_remove_item (MonoMList* list, MonoMList *item)
 277 {
 278         MonoMList* prev;
 279         if (list == item) {
 280                 list = item->next;
 281                 item->next = NULL;
 282                 return list;
 283         }
 284         prev = find_prev (list, item);
 285         if (prev) {
 286                 MONO_OBJECT_SETREF (prev, next, item->next);
 287                 item->next = NULL;
 288                 return list;
 289         } else {
 290                 /* not found */
 291                 return list;
 292         }
 293 }
 294