Print this page
new smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/ptrlist.c
+++ new/usr/src/tools/smatch/src/ptrlist.c
1 1 /*
2 2 * ptrlist.c
3 3 *
4 - * Pointer list manipulation
5 - *
6 4 * (C) Copyright Linus Torvalds 2003-2005
7 5 */
6 +
7 +///
8 +// Pointer list manipulation
9 +// -------------------------
10 +
8 11 #include <stdlib.h>
9 12 #include <string.h>
10 13 #include <assert.h>
11 14
12 15 #include "ptrlist.h"
13 16 #include "allocate.h"
14 17 #include "compat.h"
15 18
16 19 __DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
17 20 __ALLOCATOR(struct ptr_list, "ptr list", ptrlist);
18 21 __ALLOCATOR(struct ptr_list, "rl ptr list", rl_ptrlist);
19 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.
20 27 int ptr_list_size(struct ptr_list *head)
21 28 {
22 29 int nr = 0;
23 30
24 31 if (head) {
25 32 struct ptr_list *list = head;
26 33 do {
27 34 nr += list->nr - list->rm;
28 35 } while ((list = list->next) != head);
29 36 }
30 37 return nr;
31 38 }
32 39
33 -/*
34 - * Linearize the entries of a list up to a total of 'max',
35 - * and return the nr of entries linearized.
36 - *
37 - * The array to linearize into (second argument) should really
38 - * be "void *x[]", but we want to let people fill in any kind
39 - * of pointer array, so let's just call it "void **".
40 - */
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 **``.
41 154 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
42 155 {
43 156 int nr = 0;
44 157 if (head && max > 0) {
45 158 struct ptr_list *list = head;
46 159
47 160 do {
48 161 int i = list->nr;
49 162 if (i > max)
50 163 i = max;
51 164 memcpy(arr, list->list, i*sizeof(void *));
|
↓ open down ↓ |
1 lines elided |
↑ open up ↑ |
52 165 arr += i;
53 166 nr += i;
54 167 max -= i;
55 168 if (!max)
56 169 break;
57 170 } while ((list = list->next) != head);
58 171 }
59 172 return nr;
60 173 }
61 174
62 -/*
63 - * When we've walked the list and deleted entries,
64 - * we may need to re-pack it so that we don't have
65 - * any empty blocks left (empty blocks upset the
66 - * walking code
67 - */
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).
68 184 void pack_ptr_list(struct ptr_list **listp)
69 185 {
70 186 struct ptr_list *head = *listp;
71 187
72 188 if (head) {
73 189 struct ptr_list *entry = head;
74 190 do {
75 191 struct ptr_list *next;
76 192 restart:
77 193 next = entry->next;
78 194 if (!entry->nr) {
79 195 struct ptr_list *prev;
80 196 if (next == entry) {
81 197 __free_ptrlist(entry);
82 198 *listp = NULL;
83 199 return;
84 200 }
85 201 prev = entry->prev;
86 202 prev->next = next;
87 203 next->prev = prev;
88 204 __free_ptrlist(entry);
89 205 if (entry == head) {
90 206 *listp = next;
|
↓ open down ↓ |
13 lines elided |
↑ open up ↑ |
91 207 head = next;
92 208 entry = next;
93 209 goto restart;
94 210 }
95 211 }
96 212 entry = next;
97 213 } while (entry != head);
98 214 }
99 215 }
100 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.
101 224 void split_ptr_list_head(struct ptr_list *head)
102 225 {
103 226 int old = head->nr, nr = old / 2;
104 227 struct ptr_list *newlist = __alloc_ptrlist(0);
105 228 struct ptr_list *next = head->next;
106 229
107 230 old -= nr;
108 231 head->nr = old;
109 232 newlist->next = next;
110 233 next->prev = newlist;
111 234 newlist->prev = head;
112 235 head->next = newlist;
113 236 newlist->nr = nr;
114 237 memcpy(newlist->list, head->list + old, nr * sizeof(void *));
115 238 memset(head->list + old, 0xf0, nr * sizeof(void *));
116 239 }
117 240
118 241 int rl_ptrlist_hack;
119 -void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
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)
120 251 {
121 252 struct ptr_list *list = *listp;
122 253 struct ptr_list *last = NULL; /* gcc complains needlessly */
123 254 void **ret;
124 255 int nr;
125 256
126 - /* The low two bits are reserved for tags */
127 - assert((3 & (unsigned long)ptr) == 0);
128 - assert((~3 & tag) == 0);
129 - ptr = (void *)(tag | (unsigned long)ptr);
130 -
131 257 if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
132 258 struct ptr_list *newlist;
133 259
134 260 if (rl_ptrlist_hack)
135 261 newlist = __alloc_rl_ptrlist(0);
136 262 else
137 263 newlist = __alloc_ptrlist(0);
138 264 if (!list) {
139 265 newlist->next = newlist;
140 266 newlist->prev = newlist;
141 267 *listp = newlist;
142 268 } else {
143 269 newlist->prev = last;
144 270 newlist->next = list;
145 271 list->prev = newlist;
146 272 last->next = newlist;
147 273 }
|
↓ open down ↓ |
7 lines elided |
↑ open up ↑ |
148 274 last = newlist;
149 275 nr = 0;
150 276 }
151 277 ret = last->list + nr;
152 278 *ret = ptr;
153 279 nr++;
154 280 last->nr = nr;
155 281 return ret;
156 282 }
157 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.
158 330 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
159 331 {
160 332 void *ptr;
161 333
162 334 FOR_EACH_PTR(*list, ptr) {
163 335 if (ptr == entry) {
164 336 DELETE_CURRENT_PTR(ptr);
165 337 if (!--count)
166 338 goto out;
167 339 }
168 340 } END_FOR_EACH_PTR(ptr);
169 341 assert(count <= 0);
170 342 out:
171 343 pack_ptr_list(list);
172 344 return count;
173 345 }
174 346
175 -int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
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)
176 355 {
177 356 void *ptr;
178 357
179 358 FOR_EACH_PTR(*list, ptr) {
180 359 if (ptr==old_ptr) {
181 360 REPLACE_CURRENT_PTR(ptr, new_ptr);
182 361 if (!--count)
183 362 goto out;
184 363 }
185 364 }END_FOR_EACH_PTR(ptr);
186 365 assert(count <= 0);
187 366 out:
188 367 return count;
189 368 }
190 369
191 -/* This removes the last entry, but doesn't pack the ptr list */
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
192 376 void * undo_ptr_list_last(struct ptr_list **head)
193 377 {
194 378 struct ptr_list *last, *first = *head;
195 379
196 380 if (!first)
197 381 return NULL;
198 382 last = first;
199 383 do {
200 384 last = last->prev;
201 385 if (last->nr) {
202 386 void *ptr;
203 387 int nr = --last->nr;
204 388 ptr = last->list[nr];
205 389 last->list[nr] = (void *)0xf1f1f1f1;
206 390 return ptr;
207 391 }
208 392 } while (last != first);
209 393 return NULL;
210 394 }
211 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.
212 400 void * delete_ptr_list_last(struct ptr_list **head)
213 401 {
214 402 void *ptr = NULL;
215 403 struct ptr_list *last, *first = *head;
216 404
217 405 if (!first)
218 406 return NULL;
219 407 last = first->prev;
220 408 if (last->nr)
221 409 ptr = last->list[--last->nr];
222 410 if (last->nr <=0) {
223 411 first->prev = last->prev;
224 412 last->prev->next = first;
225 413 if (last == first)
226 414 *head = NULL;
227 415 __free_ptrlist(last);
228 416 }
229 417 return ptr;
230 418 }
231 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.
232 425 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
233 426 {
234 427 void *entry;
235 428 FOR_EACH_PTR(a, entry) {
236 429 add_ptr_list(b, entry);
237 430 } END_FOR_EACH_PTR(entry);
238 431 }
239 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.
240 490 void __free_ptr_list(struct ptr_list **listp)
241 491 {
242 492 struct ptr_list *tmp, *list = *listp;
243 493
244 494 if (!list)
245 495 return;
246 496
247 497 list->prev->next = NULL;
248 498 while (list) {
249 499 tmp = list;
250 500 list = list->next;
251 501 __free_ptrlist(tmp);
252 502 }
253 503
254 504 *listp = NULL;
255 505 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX