4 * (C) Copyright Linus Torvalds 2003-2005
8 // Pointer list manipulation
9 // -------------------------
11 // The data structure handled here is designed to hold pointers
12 // but two special cases need to be avoided or need special care:
13 // * NULL is used by {PREPARE,NEXT}_PTR_LIST() to indicate the end-of-list.
14 // Thus, NULL can't be stored in lists using this API but is fine to
15 // use with FOR_EACH_PTR() and its variants.
16 // * VOID is used to replace a removed pseudo 'usage'. Since phi-nodes
17 // (OP_PHI) use a list to store their operands, a VOID in a phi-node
18 // list must be ignored since it represents a removed operand. As
19 // consequence, VOIDs must never be used as phi-node operand.
20 // This is fine since phi-nodes make no sense with void values
21 // but VOID is also used for invalid types and in case of errors.
31 __DECLARE_ALLOCATOR(struct ptr_list
, ptrlist
);
32 __ALLOCATOR(struct ptr_list
, "ptr list", ptrlist
);
35 // get the size of a ptrlist
36 // @head: the head of the list
37 // @return: the size of the list given by @head.
38 int ptr_list_size(struct ptr_list
*head
)
43 struct ptr_list
*list
= head
;
45 nr
+= list
->nr
- list
->rm
;
46 } while ((list
= list
->next
) != head
);
52 // test if a list is empty
53 // @head: the head of the list
54 // @return: ``true`` if the list is empty, ``false`` otherwise.
55 bool ptr_list_empty(const struct ptr_list
*head
)
57 const struct ptr_list
*list
= head
;
63 if (list
->nr
- list
->rm
)
65 } while ((list
= list
->next
) != head
);
71 // test is a list contains more than one element
72 // @head: the head of the list
73 // @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
74 bool ptr_list_multiple(const struct ptr_list
*head
)
76 const struct ptr_list
*list
= head
;
83 nr
+= list
->nr
- list
->rm
;
86 } while ((list
= list
->next
) != head
);
92 // get the first element of a ptrlist
93 // @head: the head of the list
94 // @return: the first element of the list or ``NULL`` if the list is empty
95 void *first_ptr_list(struct ptr_list
*head
)
97 struct ptr_list
*list
= head
;
102 while (list
->nr
== 0) {
107 return PTR_ENTRY_NOTAG(list
, 0);
111 // get the last element of a ptrlist
112 // @head: the head of the list
113 // @return: the last element of the list or ``NULL`` if the list is empty
114 void *last_ptr_list(struct ptr_list
*head
)
116 struct ptr_list
*list
;
121 while (list
->nr
== 0) {
126 return PTR_ENTRY_NOTAG(list
, list
->nr
-1);
130 // get the nth element of a ptrlist
131 // @head: the head of the list
132 // @return: the nth element of the list or ``NULL`` if the list is too short.
133 void *ptr_list_nth_entry(struct ptr_list
*list
, unsigned int idx
)
135 struct ptr_list
*head
= list
;
141 unsigned int nr
= list
->nr
;
144 return list
->list
[idx
];
147 } while ((list
= list
->next
) != head
);
152 // linearize the entries of a list
154 // @head: the list to be linearized
155 // @arr: a ``void*`` array to fill with @head's entries
156 // @max: the maximum number of entries to store into @arr
157 // @return: the number of entries in the list.
159 // Linearize the entries of a list up to a total of @max,
160 // and return the number of entries in the list.
162 // The array to linearize into (@arr) should really
163 // be ``void *x[]``, but we want to let people fill in any kind
164 // of pointer array, so let's just call it ``void **``.
165 int linearize_ptr_list(struct ptr_list
*head
, void **arr
, int max
)
168 if (head
&& max
> 0) {
169 struct ptr_list
*list
= head
;
178 memcpy(arr
, list
->list
, i
*sizeof(void *));
181 } while ((list
= list
->next
) != head
);
189 // @listp: a pointer to the list to be packed.
191 // When we've walked the list and deleted entries,
192 // we may need to re-pack it so that we don't have
193 // any empty blocks left (empty blocks upset the
195 void pack_ptr_list(struct ptr_list
**listp
)
197 struct ptr_list
*head
= *listp
;
200 struct ptr_list
*entry
= head
;
202 struct ptr_list
*next
;
206 struct ptr_list
*prev
;
208 __free_ptrlist(entry
);
215 __free_ptrlist(entry
);
224 } while (entry
!= head
);
229 // split a ptrlist block
230 // @head: the ptrlist block to be split
232 // A new block is inserted just after @head and the entries
233 // at the half end of @head are moved to this new block.
234 // The goal being to create space inside @head for a new entry.
235 void split_ptr_list_head(struct ptr_list
*head
)
237 int old
= head
->nr
, nr
= old
/ 2;
238 struct ptr_list
*newlist
= __alloc_ptrlist(0);
239 struct ptr_list
*next
= head
->next
;
243 newlist
->next
= next
;
244 next
->prev
= newlist
;
245 newlist
->prev
= head
;
246 head
->next
= newlist
;
248 memcpy(newlist
->list
, head
->list
+ old
, nr
* sizeof(void *));
249 memset(head
->list
+ old
, 0xf0, nr
* sizeof(void *));
253 // add an entry to a ptrlist
254 // @listp: a pointer to the list
255 // @ptr: the entry to add to the list
256 // @return: the address where the new entry is stored.
258 // :note: code must not use this function and should use
259 // :func:`add_ptr_list` instead.
260 void **__add_ptr_list(struct ptr_list
**listp
, void *ptr
)
262 struct ptr_list
*list
= *listp
;
263 struct ptr_list
*last
= NULL
; /* gcc complains needlessly */
267 if (!list
|| (nr
= (last
= list
->prev
)->nr
) >= LIST_NODE_NR
) {
268 struct ptr_list
*newlist
= __alloc_ptrlist(0);
270 newlist
->next
= newlist
;
271 newlist
->prev
= newlist
;
274 newlist
->prev
= last
;
275 newlist
->next
= list
;
276 list
->prev
= newlist
;
277 last
->next
= newlist
;
282 ret
= last
->list
+ nr
;
290 // add a tagged entry to a ptrlist
291 // @listp: a pointer to the list
292 // @ptr: the entry to add to the list
293 // @tag: the tag to add to @ptr
294 // @return: the address where the new entry is stored.
296 // :note: code must not use this function and should use
297 // :func:`add_ptr_list_tag` instead.
298 void **__add_ptr_list_tag(struct ptr_list
**listp
, void *ptr
, unsigned long tag
)
300 /* The low two bits are reserved for tags */
301 assert((3 & (unsigned long)ptr
) == 0);
302 assert((~3 & tag
) == 0);
304 ptr
= (void *)(tag
| (unsigned long)ptr
);
306 return __add_ptr_list(listp
, ptr
);
310 // test if some entry is already present in a ptrlist
311 // @list: the head of the list
312 // @entry: the entry to test
313 // @return: ``true`` if the entry is already present, ``false`` otherwise.
314 bool lookup_ptr_list_entry(const struct ptr_list
*head
, const void *entry
)
316 const struct ptr_list
*list
= head
;
323 for (i
= 0; i
< nr
; i
++)
324 if (list
->list
[i
] == entry
)
326 } while ((list
= list
->next
) != head
);
331 // delete an entry from a ptrlist
332 // @list: a pointer to the list
333 // @entry: the item to be deleted
334 // @count: the minimum number of times @entry should be deleted or 0.
335 int delete_ptr_list_entry(struct ptr_list
**list
, void *entry
, int count
)
339 FOR_EACH_PTR(*list
, ptr
) {
341 DELETE_CURRENT_PTR(ptr
);
345 } END_FOR_EACH_PTR(ptr
);
353 // replace an entry in a ptrlist
354 // @list: a pointer to the list
355 // @old_ptr: the entry to be replaced
356 // @new_ptr: the new entry
357 // @count: the minimum number of times @entry should be deleted or 0.
358 int replace_ptr_list_entry(struct ptr_list
**list
, void *old_ptr
,
359 void *new_ptr
, int count
)
363 FOR_EACH_PTR(*list
, ptr
) {
365 REPLACE_CURRENT_PTR(ptr
, new_ptr
);
369 }END_FOR_EACH_PTR(ptr
);
376 // remove the last entry of a ptrlist
377 // @head: a pointer to the list
378 // @return: the last element of the list or NULL if the list is empty.
380 // :note: this doesn't repack the list
381 void * undo_ptr_list_last(struct ptr_list
**head
)
383 struct ptr_list
*last
, *first
= *head
;
393 ptr
= last
->list
[nr
];
394 last
->list
[nr
] = (void *)0xf1f1f1f1;
397 } while (last
!= first
);
402 // remove the last entry and repack the list
403 // @head: a pointer to the list
404 // @return: the last element of the list or NULL if the list is empty.
405 void * delete_ptr_list_last(struct ptr_list
**head
)
408 struct ptr_list
*last
, *first
= *head
;
414 ptr
= last
->list
[--last
->nr
];
416 first
->prev
= last
->prev
;
417 last
->prev
->next
= first
;
420 __free_ptrlist(last
);
426 // concat two ptrlists
427 // @a: the source list
428 // @b: a pointer to the destination list.
429 // The element of @a are added at the end of @b.
430 void concat_ptr_list(struct ptr_list
*a
, struct ptr_list
**b
)
433 FOR_EACH_PTR(a
, entry
) {
434 add_ptr_list(b
, entry
);
435 } END_FOR_EACH_PTR(entry
);
439 // copy the elements of a list at the end of another list.
440 // @listp: a pointer to the destination list.
441 // @src: the head of the source list.
442 void copy_ptr_list(struct ptr_list
**listp
, struct ptr_list
*src
)
444 struct ptr_list
*head
, *tail
;
445 struct ptr_list
*cur
= src
;
459 struct ptr_list
*next
;
462 for (i
= 0; i
< nr
;) {
463 void *ptr
= cur
->list
[i
++];
466 if (idx
>= LIST_NODE_NR
) {
467 struct ptr_list
*prev
= tail
;
468 tail
= __alloc_ptrlist(0);
474 tail
->list
[idx
++] = ptr
;
480 } while (cur
!= src
);
489 // @listp: a pointer to the list
490 // Each blocks of the list are freed (but the entries
491 // themselves are not freed).
493 // :note: code must not use this function and should use
494 // the macro :func:`free_ptr_list` instead.
495 void __free_ptr_list(struct ptr_list
**listp
)
497 struct ptr_list
*tmp
, *list
= *listp
;
502 list
->prev
->next
= NULL
;