xref: /illumos-gate/usr/src/tools/smatch/src/ptrlist.c (revision c85f09cc)
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.
ptr_list_size(struct ptr_list * 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.
ptr_list_empty(const struct ptr_list * head)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.
ptr_list_multiple(const struct ptr_list * head)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
first_ptr_list(struct ptr_list * head)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
last_ptr_list(struct ptr_list * head)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.
ptr_list_nth_entry(struct ptr_list * list,unsigned int idx)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 **``.
linearize_ptr_list(struct ptr_list * head,void ** arr,int max)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).
pack_ptr_list(struct ptr_list ** listp)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.
split_ptr_list_head(struct ptr_list * head)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.
__add_ptr_list(struct ptr_list ** listp,void * ptr)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.
__add_ptr_list_tag(struct ptr_list ** listp,void * ptr,unsigned long tag)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.
lookup_ptr_list_entry(const struct ptr_list * head,const void * entry)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.
delete_ptr_list_entry(struct ptr_list ** list,void * entry,int count)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.
replace_ptr_list_entry(struct ptr_list ** list,void * old_ptr,void * new_ptr,int count)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
undo_ptr_list_last(struct ptr_list ** head)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.
delete_ptr_list_last(struct ptr_list ** head)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.
concat_ptr_list(struct ptr_list * a,struct ptr_list ** 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.
copy_ptr_list(struct ptr_list ** listp,struct ptr_list * src)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.
__free_ptr_list(struct ptr_list ** listp)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 }
506