mono/metadata/mono-mlist.c

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