db: move function_ptr to raw SQL
[smatch.git] / ptrlist.c
blob2620412f6f5b5400b6dfd546c45be6f0988fb23a
1 /*
2 * ptrlist.c
4 * Pointer list manipulation
6 * (C) Copyright Linus Torvalds 2003-2005
7 */
8 #include <stdlib.h>
9 #include <string.h>
10 #include <assert.h>
12 #include "ptrlist.h"
13 #include "allocate.h"
14 #include "compat.h"
16 __DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
17 __ALLOCATOR(struct ptr_list, "ptr list", ptrlist);
19 int ptr_list_size(struct ptr_list *head)
21 int nr = 0;
23 if (head) {
24 struct ptr_list *list = head;
25 do {
26 nr += list->nr;
27 } while ((list = list->next) != head);
29 return nr;
33 * Linearize the entries of a list up to a total of 'max',
34 * and return the nr of entries linearized.
36 * The array to linearize into (second argument) should really
37 * be "void *x[]", but we want to let people fill in any kind
38 * of pointer array, so let's just call it "void *".
40 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
42 int nr = 0;
43 if (head && max > 0) {
44 struct ptr_list *list = head;
46 do {
47 int i = list->nr;
48 if (i > max)
49 i = max;
50 memcpy(arr, list->list, i*sizeof(void *));
51 arr += i;
52 nr += i;
53 max -= i;
54 if (!max)
55 break;
56 } while ((list = list->next) != head);
58 return nr;
62 * When we've walked the list and deleted entries,
63 * we may need to re-pack it so that we don't have
64 * any empty blocks left (empty blocks upset the
65 * walking code
67 void pack_ptr_list(struct ptr_list **listp)
69 struct ptr_list *head = *listp;
71 if (head) {
72 struct ptr_list *entry = head;
73 do {
74 struct ptr_list *next;
75 restart:
76 next = entry->next;
77 if (!entry->nr) {
78 struct ptr_list *prev;
79 if (next == entry) {
80 __free_ptrlist(entry);
81 *listp = NULL;
82 return;
84 prev = entry->prev;
85 prev->next = next;
86 next->prev = prev;
87 __free_ptrlist(entry);
88 if (entry == head) {
89 *listp = next;
90 head = next;
91 entry = next;
92 goto restart;
95 entry = next;
96 } while (entry != head);
100 void split_ptr_list_head(struct ptr_list *head)
102 int old = head->nr, nr = old / 2;
103 struct ptr_list *newlist = __alloc_ptrlist(0);
104 struct ptr_list *next = head->next;
106 old -= nr;
107 head->nr = old;
108 newlist->next = next;
109 next->prev = newlist;
110 newlist->prev = head;
111 head->next = newlist;
112 newlist->nr = nr;
113 memcpy(newlist->list, head->list + old, nr * sizeof(void *));
114 memset(head->list + old, 0xf0, nr * sizeof(void *));
117 void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
119 struct ptr_list *list = *listp;
120 struct ptr_list *last = NULL; /* gcc complains needlessly */
121 void **ret;
122 int nr;
124 /* The low two bits are reserved for tags */
125 assert((3 & (unsigned long)ptr) == 0);
126 assert((~3 & tag) == 0);
127 ptr = (void *)(tag | (unsigned long)ptr);
129 if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
130 struct ptr_list *newlist = __alloc_ptrlist(0);
131 if (!list) {
132 newlist->next = newlist;
133 newlist->prev = newlist;
134 *listp = newlist;
135 } else {
136 newlist->prev = last;
137 newlist->next = list;
138 list->prev = newlist;
139 last->next = newlist;
141 last = newlist;
142 nr = 0;
144 ret = last->list + nr;
145 *ret = ptr;
146 nr++;
147 last->nr = nr;
148 return ret;
151 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
153 void *ptr;
155 FOR_EACH_PTR(*list, ptr) {
156 if (ptr == entry) {
157 DELETE_CURRENT_PTR(ptr);
158 if (!--count)
159 goto out;
161 } END_FOR_EACH_PTR(ptr);
162 assert(count <= 0);
163 out:
164 pack_ptr_list(list);
165 return count;
168 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
170 void *ptr;
172 FOR_EACH_PTR(*list, ptr) {
173 if (ptr==old_ptr) {
174 REPLACE_CURRENT_PTR(ptr, new_ptr);
175 if (!--count)
176 goto out;
178 }END_FOR_EACH_PTR(ptr);
179 assert(count <= 0);
180 out:
181 return count;
184 /* This removes the last entry, but doesn't pack the ptr list */
185 void * undo_ptr_list_last(struct ptr_list **head)
187 struct ptr_list *last, *first = *head;
189 if (!first)
190 return NULL;
191 last = first;
192 do {
193 last = last->prev;
194 if (last->nr) {
195 void *ptr;
196 int nr = --last->nr;
197 ptr = last->list[nr];
198 last->list[nr] = (void *)0xf1f1f1f1;
199 return ptr;
201 } while (last != first);
202 return NULL;
205 void * delete_ptr_list_last(struct ptr_list **head)
207 void *ptr = NULL;
208 struct ptr_list *last, *first = *head;
210 if (!first)
211 return NULL;
212 last = first->prev;
213 if (last->nr)
214 ptr = last->list[--last->nr];
215 if (last->nr <=0) {
216 first->prev = last->prev;
217 last->prev->next = first;
218 if (last == first)
219 *head = NULL;
220 __free_ptrlist(last);
222 return ptr;
225 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
227 void *entry;
228 FOR_EACH_PTR(a, entry) {
229 add_ptr_list(b, entry);
230 } END_FOR_EACH_PTR(entry);
233 void __free_ptr_list(struct ptr_list **listp)
235 struct ptr_list *tmp, *list = *listp;
237 if (!list)
238 return;
240 list->prev->next = NULL;
241 while (list) {
242 tmp = list;
243 list = list->next;
244 __free_ptrlist(tmp);
247 *listp = NULL;