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                 g_assert (monolist_item_vtable);
  45         }
  46         res = (MonoMList*)mono_object_new_fast (monolist_item_vtable);
  47         MONO_OBJECT_SETREF (res, data, data);
  48         return res;
  49 }
  50
  51 /**
  52  * mono_mlist_get_data:
  53  * @list: the managed list node
  54  *
  55  * Get the object stored in the list node @list.
  56  */
  57 MonoObject*
  58 mono_mlist_get_data (MonoMList* list)
  59 {
  60         return list->data;
  61 }
  62
  63 /**
  64  * mono_mlist_set_data:
  65  * @list: the managed list node
  66  *
  67  * Set the object content in the list node @list.
  68  */
  69 void
  70 mono_mlist_set_data (MonoMList* list, MonoObject *data)
  71 {
  72         MONO_OBJECT_SETREF (list, data, data);
  73 }
  74
  75 /**
  76  * mono_mlist_length:
  77  * @list: the managed list
  78  *
  79  * Get the number of items in the list @list.
  80  * Since managed lists are singly-linked, this operation takes O(n) time.
  81  */
  82 int
  83 mono_mlist_length (MonoMList* list)
  84 {
  85         int len = 0;
  86         while (list) {
  87                 list = list->next;
  88                 ++len;
  89         }
  90         return len;
  91 }
  92
  93 /**
  94  * mono_mlist_next:
  95  * @list: the managed list node
  96  *
  97  * Returns the next managed list node starting from @list.
  98  */
  99 MonoMList*
 100 mono_mlist_next (MonoMList* list)
 101 {
 102         return list->next;
 103 }
 104
 105 /**
 106  * mono_mlist_last:
 107  * @list: the managed list node
 108  *
 109  * Returns the last managed list node in list @list.
 110  * Since managed lists are singly-linked, this operation takes O(n) time.
 111  */
 112 MonoMList*
 113 mono_mlist_last (MonoMList* list)
 114 {
 115         if (list) {
 116                 while (list->next)
 117                         list = list->next;
 118                 return list;
 119         }
 120         return NULL;
 121 }
 122
 123 /**
 124  * mono_mlist_prepend:
 125  * @list: the managed list
 126  * @data: the object to add to the list
 127  *
 128  * Allocate a new list node with @data as content and prepend it
 129  * to the list @list. @list can be NULL.
 130  */
 131 MonoMList*
 132 mono_mlist_prepend (MonoMList* list, MonoObject *data)
 133 {
 134         MonoMList* res = mono_mlist_alloc (data);
 135         if (list)
 136                 MONO_OBJECT_SETREF (res, next, list);
 137         return res;
 138 }
 139
 140 /**
 141  * mono_mlist_append:
 142  * @list: the managed list
 143  * @data: the object to add to the list
 144  *
 145  * Allocate a new list node with @data as content and append it
 146  * to the list @list. @list can be NULL.
 147  * Since managed lists are singly-linked, this operation takes O(n) time.
 148  */
 149 MonoMList*
 150 mono_mlist_append (MonoMList* list, MonoObject *data)
 151 {
 152         MonoMList* res = mono_mlist_alloc (data);
 153         if (list) {
 154                 MonoMList* last = mono_mlist_last (list);
 155                 MONO_OBJECT_SETREF (last, next, res);
 156                 return list;
 157         } else {
 158                 return res;
 159         }
 160 }
 161
 162 static MonoMList*
 163 find_prev (MonoMList* list, MonoMList *item)
 164 {
 165         MonoMList* prev = NULL;
 166         while (list) {
 167                 if (list == item)
 168                         break;
 169                 prev = list;
 170                 list = list->next;
 171         }
 172         return prev;
 173 }
 174
 175 /**
 176  * mono_mlist_remove_item:
 177  * @list: the managed list
 178  * @data: the object to add to the list
 179  *
 180  * Remove the list node @item from the managed list @list.
 181  * Since managed lists are singly-linked, this operation can take O(n) time.
 182  */
 183 MonoMList*
 184 mono_mlist_remove_item (MonoMList* list, MonoMList *item)
 185 {
 186         MonoMList* prev;
 187         if (list == item) {
 188                 list = item->next;
 189                 item->next = NULL;
 190                 return list;
 191         }
 192         prev = find_prev (list, item);
 193         if (prev) {
 194                 MONO_OBJECT_SETREF (prev, next, item->next);
 195                 item->next = NULL;
 196                 return list;
 197         } else {
 198                 /* not found */
 199                 return list;
 200         }
 201 }
 202