1 /*
2 * ptrlist.c
3 *
4 * (C) Copyright Linus Torvalds 2003-2005
5 */
6
7 ///
8 // Pointer list manipulation
9 // -------------------------
10
11 #include <stdlib.h>
12 #include <string.h>
13 #include <assert.h>
14
15 #include "ptrlist.h"
16 #include "allocate.h"
17 #include "compat.h"
18
19 __DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
20 __ALLOCATOR(struct ptr_list, "ptr list", ptrlist);
21 __ALLOCATOR(struct ptr_list, "rl ptr list", rl_ptrlist);
22
23 ///
24 // get the size of a ptrlist
25 // @head: the head of the list
26 // @return: the size of the list given by @head.
27 int ptr_list_size(struct ptr_list *head)
28 {
29 int nr = 0;
30
31 if (head) {
32 struct ptr_list *list = head;
33 do {
34 nr += list->nr - list->rm;
35 } while ((list = list->next) != head);
36 }
37 return nr;
38 }
39
40 ///
41 // test if a list is empty
42 // @head: the head of the list
43 // @return: ``true`` if the list is empty, ``false`` otherwise.
44 bool ptr_list_empty(const struct ptr_list *head)
45 {
46 const struct ptr_list *list = head;
47
48 if (!head)
49 return true;
50
51 do {
52 if (list->nr - list->rm)
53 return false;
54 } while ((list = list->next) != head);
55
56 return true;
57 }
58
59 ///
60 // test is a list contains more than one element
61 // @head: the head of the list
62 // @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
63 bool ptr_list_multiple(const struct ptr_list *head)
64 {
65 const struct ptr_list *list = head;
66 int nr = 0;
67
68 if (!head)
69 return false;
70
71 do {
72 nr += list->nr - list->rm;
73 if (nr > 1)
74 return true;
75 } while ((list = list->next) != head);
76
77 return false;
78 }
79
80 ///
81 // get the first element of a ptrlist
82 // @head: the head of the list
83 // @return: the first element of the list or ``NULL`` if the list is empty
84 void *first_ptr_list(struct ptr_list *head)
85 {
86 struct ptr_list *list = head;
87
88 if (!head)
89 return NULL;
90
91 while (list->nr == 0) {
92 list = list->next;
93 if (list == head)
94 return NULL;
95 }
96 return PTR_ENTRY_NOTAG(list, 0);
97 }
98
99 ///
100 // get the last element of a ptrlist
101 // @head: the head of the list
102 // @return: the last element of the list or ``NULL`` if the list is empty
103 void *last_ptr_list(struct ptr_list *head)
104 {
105 struct ptr_list *list;
106
107 if (!head)
108 return NULL;
109 list = head->prev;
110 while (list->nr == 0) {
111 if (list == head)
112 return NULL;
113 list = list->prev;
114 }
115 return PTR_ENTRY_NOTAG(list, list->nr-1);
116 }
117
118 ///
119 // get the nth element of a ptrlist
120 // @head: the head of the list
121 // @return: the nth element of the list or ``NULL`` if the list is too short.
122 void *ptr_list_nth_entry(struct ptr_list *list, unsigned int idx)
123 {
124 struct ptr_list *head = list;
125
126 if (!head)
127 return NULL;
128
129 do {
130 unsigned int nr = list->nr;
131
132 if (idx < nr)
133 return list->list[idx];
134 else
135 idx -= nr;
136 } while ((list = list->next) != head);
137 return NULL;
138 }
139
140 ///
141 // linearize the entries of a list
142 //
143 // @head: the list to be linearized
144 // @arr: a ``void*`` array to fill with @head's entries
145 // @max: the maximum number of entries to store into @arr
146 // @return: the number of entries linearized.
147 //
148 // Linearize the entries of a list up to a total of @max,
149 // and return the nr of entries linearized.
150 //
151 // The array to linearize into (@arr) should really
152 // be ``void *x[]``, but we want to let people fill in any kind
153 // of pointer array, so let's just call it ``void **``.
154 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
155 {
156 int nr = 0;
157 if (head && max > 0) {
158 struct ptr_list *list = head;
159
160 do {
161 int i = list->nr;
162 if (i > max)
163 i = max;
164 memcpy(arr, list->list, i*sizeof(void *));
165 arr += i;
166 nr += i;
167 max -= i;
168 if (!max)
169 break;
170 } while ((list = list->next) != head);
171 }
172 return nr;
173 }
174
175 ///
176 // pack a ptrlist
177 //
178 // @listp: a pointer to the list to be packed.
179 //
180 // When we've walked the list and deleted entries,
181 // we may need to re-pack it so that we don't have
182 // any empty blocks left (empty blocks upset the
183 // walking code).
184 void pack_ptr_list(struct ptr_list **listp)
185 {
186 struct ptr_list *head = *listp;
187
188 if (head) {
189 struct ptr_list *entry = head;
190 do {
191 struct ptr_list *next;
192 restart:
193 next = entry->next;
194 if (!entry->nr) {
195 struct ptr_list *prev;
196 if (next == entry) {
197 __free_ptrlist(entry);
198 *listp = NULL;
199 return;
200 }
201 prev = entry->prev;
202 prev->next = next;
203 next->prev = prev;
204 __free_ptrlist(entry);
205 if (entry == head) {
206 *listp = next;
207 head = next;
208 entry = next;
209 goto restart;
210 }
211 }
212 entry = next;
213 } while (entry != head);
214 }
215 }
216
217 ///
218 // split a ptrlist block
219 // @head: the ptrlist block to be splitted
220 //
221 // A new block is inserted just after @head and the entries
222 // at the half end of @head are moved to this new block.
223 // The goal being to create space inside @head for a new entry.
224 void split_ptr_list_head(struct ptr_list *head)
225 {
226 int old = head->nr, nr = old / 2;
227 struct ptr_list *newlist = __alloc_ptrlist(0);
228 struct ptr_list *next = head->next;
229
230 old -= nr;
231 head->nr = old;
232 newlist->next = next;
233 next->prev = newlist;
234 newlist->prev = head;
235 head->next = newlist;
236 newlist->nr = nr;
237 memcpy(newlist->list, head->list + old, nr * sizeof(void *));
238 memset(head->list + old, 0xf0, nr * sizeof(void *));
239 }
240
241 int rl_ptrlist_hack;
242 ///
243 // add an entry to a ptrlist
244 // @listp: a pointer to the list
245 // @ptr: the entry to add to the list
246 // @return: the address where the new entry is stored.
247 //
248 // :note: code must not use this function and should use
249 // :func:`add_ptr_list` instead.
250 void **__add_ptr_list(struct ptr_list **listp, void *ptr)
251 {
252 struct ptr_list *list = *listp;
253 struct ptr_list *last = NULL; /* gcc complains needlessly */
254 void **ret;
255 int nr;
256
257 if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
258 struct ptr_list *newlist;
259
260 if (rl_ptrlist_hack)
261 newlist = __alloc_rl_ptrlist(0);
262 else
263 newlist = __alloc_ptrlist(0);
264 if (!list) {
265 newlist->next = newlist;
266 newlist->prev = newlist;
267 *listp = newlist;
268 } else {
269 newlist->prev = last;
270 newlist->next = list;
271 list->prev = newlist;
272 last->next = newlist;
273 }
274 last = newlist;
275 nr = 0;
276 }
277 ret = last->list + nr;
278 *ret = ptr;
279 nr++;
280 last->nr = nr;
281 return ret;
282 }
283
284 ///
285 // add a tagged entry to a ptrlist
286 // @listp: a pointer to the list
287 // @ptr: the entry to add to the list
288 // @tag: the tag to add to @ptr
289 // @return: the address where the new entry is stored.
290 //
291 // :note: code must not use this function and should use
292 // :func:`add_ptr_list_tag` instead.
293 void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
294 {
295 /* The low two bits are reserved for tags */
296 assert((3 & (unsigned long)ptr) == 0);
297 assert((~3 & tag) == 0);
298
299 ptr = (void *)(tag | (unsigned long)ptr);
300
301 return __add_ptr_list(listp, ptr);
302 }
303
304 ///
305 // test if some entry is already present in a ptrlist
306 // @list: the head of the list
307 // @entry: the entry to test
308 // @return: ``true`` if the entry is already present, ``false`` otherwise.
309 bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry)
310 {
311 const struct ptr_list *list = head;
312
313 if (!head)
314 return false;
315 do {
316 int nr = list->nr;
317 int i;
318 for (i = 0; i < nr; i++)
319 if (list->list[i] == entry)
320 return true;
321 } while ((list = list->next) != head);
322 return false;
323 }
324
325 ///
326 // delete an entry from a ptrlist
327 // @list: a pointer to the list
328 // @entry: the item to be deleted
329 // @count: the minimum number of times @entry should be deleted or 0.
330 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
331 {
332 void *ptr;
333
334 FOR_EACH_PTR(*list, ptr) {
335 if (ptr == entry) {
336 DELETE_CURRENT_PTR(ptr);
337 if (!--count)
338 goto out;
339 }
340 } END_FOR_EACH_PTR(ptr);
341 assert(count <= 0);
342 out:
343 pack_ptr_list(list);
344 return count;
345 }
346
347 ///
348 // replace an entry in a ptrlist
349 // @list: a pointer to the list
350 // @old_ptr: the entry to be replaced
351 // @new_ptr: the new entry
352 // @count: the minimum number of times @entry should be deleted or 0.
353 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr,
354 void *new_ptr, int count)
355 {
356 void *ptr;
357
358 FOR_EACH_PTR(*list, ptr) {
359 if (ptr==old_ptr) {
360 REPLACE_CURRENT_PTR(ptr, new_ptr);
361 if (!--count)
362 goto out;
363 }
364 }END_FOR_EACH_PTR(ptr);
365 assert(count <= 0);
366 out:
367 return count;
368 }
369
370 ///
371 // remove the last entry of a ptrlist
372 // @head: a pointer to the list
373 // @return: the last elemant of the list or NULL if the list is empty.
374 //
375 // :note: this doesn't repack the list
376 void * undo_ptr_list_last(struct ptr_list **head)
377 {
378 struct ptr_list *last, *first = *head;
379
380 if (!first)
381 return NULL;
382 last = first;
383 do {
384 last = last->prev;
385 if (last->nr) {
386 void *ptr;
387 int nr = --last->nr;
388 ptr = last->list[nr];
389 last->list[nr] = (void *)0xf1f1f1f1;
390 return ptr;
391 }
392 } while (last != first);
393 return NULL;
394 }
395
396 ///
397 // remove the last entry and repack the list
398 // @head: a pointer to the list
399 // @return: the last elemant of the list or NULL if the list is empty.
400 void * delete_ptr_list_last(struct ptr_list **head)
401 {
402 void *ptr = NULL;
403 struct ptr_list *last, *first = *head;
404
405 if (!first)
406 return NULL;
407 last = first->prev;
408 if (last->nr)
409 ptr = last->list[--last->nr];
410 if (last->nr <=0) {
411 first->prev = last->prev;
412 last->prev->next = first;
413 if (last == first)
414 *head = NULL;
415 __free_ptrlist(last);
416 }
417 return ptr;
418 }
419
420 ///
421 // concat two ptrlists
422 // @a: the source list
423 // @b: a pointer to the destination list.
424 // The element of @a are added at the end of @b.
425 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
426 {
427 void *entry;
428 FOR_EACH_PTR(a, entry) {
429 add_ptr_list(b, entry);
430 } END_FOR_EACH_PTR(entry);
431 }
432
433 ///
434 // copy the elements of a list at the end of another list.
435 // @listp: a pointer to the destination list.
436 // @src: the head of the source list.
437 void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src)
438 {
439 struct ptr_list *head, *tail;
440 struct ptr_list *cur = src;
441 int idx;
442
443 if (!src)
444 return;
445 head = *listp;
446 if (!head) {
447 *listp = src;
448 return;
449 }
450
451 tail = head->prev;
452 idx = tail->nr;
453 do {
454 struct ptr_list *next;
455 int nr = cur->nr;
456 int i;
457 for (i = 0; i < nr;) {
458 void *ptr = cur->list[i++];
459 if (!ptr)
460 continue;
461 if (idx >= LIST_NODE_NR) {
462 struct ptr_list *prev = tail;
463 tail = __alloc_ptrlist(0);
464 prev->next = tail;
465 tail->prev = prev;
466 prev->nr = idx;
467 idx = 0;
468 }
469 tail->list[idx++] = ptr;
470 }
471
472 next = cur->next;
473 __free_ptrlist(cur);
474 cur = next;
475 } while (cur != src);
476
477 tail->nr = idx;
478 head->prev = tail;
479 tail->next = head;
480 }
481
482 ///
483 // free a ptrlist
484 // @listp: a pointer to the list
485 // Each blocks of the list are freed (but the entries
486 // themselves are not freed).
487 //
488 // :note: code must not use this function and should use
489 // the macro :func:`free_ptr_list` instead.
490 void __free_ptr_list(struct ptr_list **listp)
491 {
492 struct ptr_list *tmp, *list = *listp;
493
494 if (!list)
495 return;
496
497 list->prev->next = NULL;
498 while (list) {
499 tmp = list;
500 list = list->next;
501 __free_ptrlist(tmp);
502 }
503
504 *listp = NULL;
505 }