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