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 object*/
  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_set_next:
  77  * @list: a managed list node
  78  * @next: list node that will be next for the @list node.
  79  *
  80  * Set next node for @list to @next.
  81  */
  82 MonoMList *
  83 mono_mlist_set_next (MonoMList* list, MonoMList *next)
  84 {
  85         if (!list)
  86                 return next;
  87
  88         MONO_OBJECT_SETREF (list, next, next);
  89         return list;
  90 }
  91
  92 /**
  93  * mono_mlist_length:
  94  * @list: the managed list
  95  *
  96  * Get the number of items in the list @list.
  97  * Since managed lists are singly-linked, this operation takes O(n) time.
  98  */
  99 int
 100 mono_mlist_length (MonoMList* list)
 101 {
 102         int len = 0;
 103         while (list) {
 104                 list = list->next;
 105                 ++len;
 106         }
 107         return len;
 108 }
 109
 110 /**
 111  * mono_mlist_next:
 112  * @list: the managed list node
 113  *
 114  * Returns the next managed list node starting from @list.
 115  */
 116 MonoMList*
 117 mono_mlist_next (MonoMList* list)
 118 {
 119         return list->next;
 120 }
 121
 122 /**
 123  * mono_mlist_last:
 124  * @list: the managed list node
 125  *
 126  * Returns the last managed list node in list @list.
 127  * Since managed lists are singly-linked, this operation takes O(n) time.
 128  */
 129 MonoMList*
 130 mono_mlist_last (MonoMList* list)
 131 {
 132         if (list) {
 133                 while (list->next)
 134                         list = list->next;
 135                 return list;
 136         }
 137         return NULL;
 138 }
 139
 140 /**
 141  * mono_mlist_prepend:
 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 prepend it
 146  * to the list @list. @list can be NULL.
 147  */
 148 MonoMList*
 149 mono_mlist_prepend (MonoMList* list, MonoObject *data)
 150 {
 151         MonoMList* res = mono_mlist_alloc (data);
 152         if (list)
 153                 MONO_OBJECT_SETREF (res, next, list);
 154         return res;
 155 }
 156
 157 /**
 158  * mono_mlist_append:
 159  * @list: the managed list
 160  * @data: the object to add to the list
 161  *
 162  * Allocate a new list node with @data as content and append it
 163  * to the list @list. @list can be NULL.
 164  * Since managed lists are singly-linked, this operation takes O(n) time.
 165  */
 166 MonoMList*
 167 mono_mlist_append (MonoMList* list, MonoObject *data)
 168 {
 169         MonoMList* res = mono_mlist_alloc (data);
 170         if (list) {
 171                 MonoMList* last = mono_mlist_last (list);
 172                 MONO_OBJECT_SETREF (last, next, res);
 173                 return list;
 174         } else {
 175                 return res;
 176         }
 177 }
 178
 179 static MonoMList*
 180 find_prev (MonoMList* list, MonoMList *item)
 181 {
 182         MonoMList* prev = NULL;
 183         while (list) {
 184                 if (list == item)
 185                         break;
 186                 prev = list;
 187                 list = list->next;
 188         }
 189         return prev;
 190 }
 191
 192 /**
 193  * mono_mlist_remove_item:
 194  * @list: the managed list
 195  * @data: the object to remove from the list
 196  *
 197  * Remove the list node @item from the managed list @list.
 198  * Since managed lists are singly-linked, this operation can take O(n) time.
 199  */
 200 MonoMList*
 201 mono_mlist_remove_item (MonoMList* list, MonoMList *item)
 202 {
 203         MonoMList* prev;
 204         if (list == item) {
 205                 list = item->next;
 206                 item->next = NULL;
 207                 return list;
 208         }
 209         prev = find_prev (list, item);
 210         if (prev) {
 211                 MONO_OBJECT_SETREF (prev, next, item->next);
 212                 item->next = NULL;
 213                 return list;
 214         } else {
 215                 /* not found */
 216                 return list;
 217         }
 218 }
 219