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                 MonoClass *klass = mono_class_load_from_name (mono_defaults.corlib, "System", "MonoListItem");
  72                 monolist_item_vtable = mono_class_vtable_checked (mono_get_root_domain (), klass, error);
  73                 mono_error_assert_ok  (error);
  74         }
  75         res = (MonoMList*)mono_object_new_specific_checked (monolist_item_vtable, error);
  76         return_val_if_nok (error, NULL);
  77         MONO_OBJECT_SETREF_INTERNAL (res, data, data);
  78         return res;
  79 }
  80
  81 /**
  82  * mono_mlist_get_data:
  83  * \param list the managed list node
  84  * Get the object stored in the list node \p list.
  85  */
  86 MonoObject*
  87 mono_mlist_get_data (MonoMList* list)
  88 {
  89         return list->data;
  90 }
  91
  92 /**
  93  * mono_mlist_set_data:
  94  * \param list the managed list node
  95  * Set the object content in the list node \p list.
  96  */
  97 void
  98 mono_mlist_set_data (MonoMList* list, MonoObject *data)
  99 {
 100         MONO_OBJECT_SETREF_INTERNAL (list, data, data);
 101 }
 102
 103 /**
 104  * mono_mlist_set_next:
 105  * \param list a managed list node
 106  * \param next list node that will be next for the \p list node.
 107  * Set next node for \p list to \p next.
 108  */
 109 MonoMList *
 110 mono_mlist_set_next (MonoMList* list, MonoMList *next)
 111 {
 112         if (!list)
 113                 return next;
 114
 115         MONO_OBJECT_SETREF_INTERNAL (list, next, next);
 116         return list;
 117 }
 118
 119 /**
 120  * mono_mlist_length:
 121  * \param list the managed list
 122  * Get the number of items in the list \p list.
 123  * Since managed lists are singly-linked, this operation takes O(n) time.
 124  */
 125 int
 126 mono_mlist_length (MonoMList* list)
 127 {
 128         int len = 0;
 129         while (list) {
 130                 list = list->next;
 131                 ++len;
 132         }
 133         return len;
 134 }
 135
 136 /**
 137  * mono_mlist_next:
 138  * \param list the managed list node
 139  * Returns the next managed list node starting from \p list.
 140  */
 141 MonoMList*
 142 mono_mlist_next (MonoMList* list)
 143 {
 144         return list->next;
 145 }
 146
 147 /**
 148  * mono_mlist_last:
 149  * \param list the managed list node
 150  * Returns the last managed list node in list \p list.
 151  * Since managed lists are singly-linked, this operation takes O(n) time.
 152  */
 153 MonoMList*
 154 mono_mlist_last (MonoMList* list)
 155 {
 156         if (list) {
 157                 while (list->next)
 158                         list = list->next;
 159                 return list;
 160         }
 161         return NULL;
 162 }
 163
 164 /**
 165  * mono_mlist_prepend:
 166  * \param list the managed list
 167  * \param data the object to add to the list
 168  * Allocate a new list node with \p data as content and prepend it
 169  * to the list \p list. \p list can be NULL.
 170  */
 171 MonoMList*
 172 mono_mlist_prepend (MonoMList* list, MonoObject *data)
 173 {
 174         ERROR_DECL (error);
 175         MonoMList *result = mono_mlist_prepend_checked (list, data, error);
 176         mono_error_cleanup (error);
 177         return result;
 178 }
 179
 180 /**
 181  * mono_mlist_prepend_checked:
 182  * \param list the managed list
 183  * \param data the object to add to the list
 184  * \param error set on error
 185  * Allocate a new list node with \p data as content and prepend it to
 186  * the list \p list. \p list can be NULL. On failure returns NULL and sets
 187  * \p error.
 188  */
 189 MonoMList*
 190 mono_mlist_prepend_checked (MonoMList* list, MonoObject *data, MonoError *error)
 191 {
 192         error_init (error);
 193         MonoMList* res = mono_mlist_alloc_checked (data, error);
 194         return_val_if_nok (error, NULL);
 195
 196         if (list)
 197                 MONO_OBJECT_SETREF_INTERNAL (res, next, list);
 198         return res;
 199 }
 200
 201 /**
 202  * mono_mlist_append:
 203  * \param list the managed list
 204  * \param data the object to add to the list
 205  * Allocate a new list node with \p data as content and append it
 206  * to the list \p list. \p list can be NULL.
 207  * Since managed lists are singly-linked, this operation takes O(n) time.
 208  */
 209 MonoMList*
 210 mono_mlist_append (MonoMList* list, MonoObject *data)
 211 {
 212         ERROR_DECL (error);
 213         MonoMList *result = mono_mlist_append_checked (list, data, error);
 214         mono_error_cleanup (error);
 215         return result;
 216 }
 217
 218 /**
 219  * mono_mlist_append_checked:
 220  * \param list the managed list
 221  * \param data the object to add to the list
 222  * \param error set on error
 223  * Allocate a new list node with \p data as content and append it
 224  * to the list \p list. \p list can be NULL.
 225  * Since managed lists are singly-linked, this operation takes O(n) time.
 226  * On failure returns NULL and sets \p error.
 227  */
 228 MonoMList*
 229 mono_mlist_append_checked (MonoMList* list, MonoObject *data, MonoError *error)
 230 {
 231         error_init (error);
 232         MonoMList* res = mono_mlist_alloc_checked (data, error);
 233         return_val_if_nok (error, NULL);
 234
 235         if (list) {
 236                 MonoMList* last = mono_mlist_last (list);
 237                 MONO_OBJECT_SETREF_INTERNAL (last, next, res);
 238                 return list;
 239         } else {
 240                 return res;
 241         }
 242 }
 243
 244 static MonoMList*
 245 find_prev (MonoMList* list, MonoMList *item)
 246 {
 247         MonoMList* prev = NULL;
 248         while (list) {
 249                 if (list == item)
 250                         break;
 251                 prev = list;
 252                 list = list->next;
 253         }
 254         return prev;
 255 }
 256
 257 /**
 258  * mono_mlist_remove_item:
 259  * \param list the managed list
 260  * \param data the object to remove from the list
 261  * Remove the list node \p item from the managed list \p list.
 262  * Since managed lists are singly-linked, this operation can take O(n) time.
 263  */
 264 MonoMList*
 265 mono_mlist_remove_item (MonoMList* list, MonoMList *item)
 266 {
 267         MonoMList* prev;
 268         if (list == item) {
 269                 list = item->next;
 270                 item->next = NULL;
 271                 return list;
 272         }
 273         prev = find_prev (list, item);
 274         if (prev) {
 275                 MONO_OBJECT_SETREF_INTERNAL (prev, next, item->next);
 276                 item->next = NULL;
 277                 return list;
 278         } else {
 279                 /* not found */
 280                 return list;
 281         }
 282 }
 283