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