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*
mono_mlist_alloc(MonoObject * data)46 mono_mlist_alloc (MonoObject *data)
47 {
48 MonoError 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*
mono_mlist_alloc_checked(MonoObject * data,MonoError * error)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 (mono_get_root_domain (), klass);
73 g_assert (monolist_item_vtable);
74 }
75 res = (MonoMList*)mono_object_new_specific_checked (monolist_item_vtable, error);
76 return_val_if_nok (error, NULL);
77 MONO_OBJECT_SETREF (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*
mono_mlist_get_data(MonoMList * list)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
mono_mlist_set_data(MonoMList * list,MonoObject * data)98 mono_mlist_set_data (MonoMList* list, MonoObject *data)
99 {
100 MONO_OBJECT_SETREF (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 *
mono_mlist_set_next(MonoMList * list,MonoMList * next)110 mono_mlist_set_next (MonoMList* list, MonoMList *next)
111 {
112 if (!list)
113 return next;
114
115 MONO_OBJECT_SETREF (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
mono_mlist_length(MonoMList * list)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*
mono_mlist_next(MonoMList * list)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*
mono_mlist_last(MonoMList * list)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*
mono_mlist_prepend(MonoMList * list,MonoObject * data)172 mono_mlist_prepend (MonoMList* list, MonoObject *data)
173 {
174 MonoError 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*
mono_mlist_prepend_checked(MonoMList * list,MonoObject * data,MonoError * error)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 (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*
mono_mlist_append(MonoMList * list,MonoObject * data)210 mono_mlist_append (MonoMList* list, MonoObject *data)
211 {
212 MonoError 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*
mono_mlist_append_checked(MonoMList * list,MonoObject * data,MonoError * error)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 (last, next, res);
238 return list;
239 } else {
240 return res;
241 }
242 }
243
244 static MonoMList*
find_prev(MonoMList * list,MonoMList * item)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*
mono_mlist_remove_item(MonoMList * list,MonoMList * item)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 (prev, next, item->next);
276 item->next = NULL;
277 return list;
278 } else {
279 /* not found */
280 return list;
281 }
282 }
283
284