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