1 /*
2 * ptrlist.c
3 *
4 * Pointer list manipulation
5 *
6 * (C) Copyright Linus Torvalds 2003-2005
7 */
8 #include <stdlib.h>
9 #include <string.h>
10 #include <assert.h>
11
12 #include "ptrlist.h"
13 #include "allocate.h"
14 #include "compat.h"
15
16 __DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
17 __ALLOCATOR(struct ptr_list, "ptr list", ptrlist);
18 __ALLOCATOR(struct ptr_list, "rl ptr list", rl_ptrlist);
19
20 int ptr_list_size(struct ptr_list *head)
21 {
22 int nr = 0;
23
24 if (head) {
25 struct ptr_list *list = head;
26 do {
27 nr += list->nr - list->rm;
28 } while ((list = list->next) != head);
29 }
30 return nr;
31 }
32
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 */
41 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
42 {
43 int nr = 0;
44 if (head && max > 0) {
45 struct ptr_list *list = head;
46
47 do {
48 int i = list->nr;
49 if (i > max)
50 i = max;
51 memcpy(arr, list->list, i*sizeof(void *));
52 arr += i;
53 nr += i;
54 max -= i;
55 if (!max)
56 break;
57 } while ((list = list->next) != head);
58 }
59 return nr;
60 }
61
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 */
68 void pack_ptr_list(struct ptr_list **listp)
69 {
70 struct ptr_list *head = *listp;
71
72 if (head) {
73 struct ptr_list *entry = head;
74 do {
75 struct ptr_list *next;
76 restart:
77 next = entry->next;
78 if (!entry->nr) {
79 struct ptr_list *prev;
80 if (next == entry) {
81 __free_ptrlist(entry);
82 *listp = NULL;
83 return;
84 }
85 prev = entry->prev;
86 prev->next = next;
87 next->prev = prev;
88 __free_ptrlist(entry);
89 if (entry == head) {
90 *listp = next;
91 head = next;
92 entry = next;
93 goto restart;
94 }
95 }
96 entry = next;
97 } while (entry != head);
98 }
99 }
100
101 void split_ptr_list_head(struct ptr_list *head)
102 {
103 int old = head->nr, nr = old / 2;
104 struct ptr_list *newlist = __alloc_ptrlist(0);
105 struct ptr_list *next = head->next;
106
107 old -= nr;
108 head->nr = old;
109 newlist->next = next;
110 next->prev = newlist;
111 newlist->prev = head;
112 head->next = newlist;
113 newlist->nr = nr;
114 memcpy(newlist->list, head->list + old, nr * sizeof(void *));
115 memset(head->list + old, 0xf0, nr * sizeof(void *));
116 }
117
118 int rl_ptrlist_hack;
119 void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
120 {
121 struct ptr_list *list = *listp;
122 struct ptr_list *last = NULL; /* gcc complains needlessly */
123 void **ret;
124 int nr;
125
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 if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
132 struct ptr_list *newlist;
133
134 if (rl_ptrlist_hack)
135 newlist = __alloc_rl_ptrlist(0);
136 else
137 newlist = __alloc_ptrlist(0);
138 if (!list) {
139 newlist->next = newlist;
140 newlist->prev = newlist;
141 *listp = newlist;
142 } else {
143 newlist->prev = last;
144 newlist->next = list;
145 list->prev = newlist;
146 last->next = newlist;
147 }
148 last = newlist;
149 nr = 0;
150 }
151 ret = last->list + nr;
152 *ret = ptr;
153 nr++;
154 last->nr = nr;
155 return ret;
156 }
157
158 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
159 {
160 void *ptr;
161
162 FOR_EACH_PTR(*list, ptr) {
163 if (ptr == entry) {
164 DELETE_CURRENT_PTR(ptr);
165 if (!--count)
166 goto out;
167 }
168 } END_FOR_EACH_PTR(ptr);
169 assert(count <= 0);
170 out:
171 pack_ptr_list(list);
172 return count;
173 }
174
175 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
176 {
177 void *ptr;
178
179 FOR_EACH_PTR(*list, ptr) {
180 if (ptr==old_ptr) {
181 REPLACE_CURRENT_PTR(ptr, new_ptr);
182 if (!--count)
183 goto out;
184 }
185 }END_FOR_EACH_PTR(ptr);
186 assert(count <= 0);
187 out:
188 return count;
189 }
190
191 /* This removes the last entry, but doesn't pack the ptr list */
192 void * undo_ptr_list_last(struct ptr_list **head)
193 {
194 struct ptr_list *last, *first = *head;
195
196 if (!first)
197 return NULL;
198 last = first;
199 do {
200 last = last->prev;
201 if (last->nr) {
202 void *ptr;
203 int nr = --last->nr;
204 ptr = last->list[nr];
205 last->list[nr] = (void *)0xf1f1f1f1;
206 return ptr;
207 }
208 } while (last != first);
209 return NULL;
210 }
211
212 void * delete_ptr_list_last(struct ptr_list **head)
213 {
214 void *ptr = NULL;
215 struct ptr_list *last, *first = *head;
216
217 if (!first)
218 return NULL;
219 last = first->prev;
220 if (last->nr)
221 ptr = last->list[--last->nr];
222 if (last->nr <=0) {
223 first->prev = last->prev;
224 last->prev->next = first;
225 if (last == first)
226 *head = NULL;
227 __free_ptrlist(last);
228 }
229 return ptr;
230 }
231
232 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
233 {
234 void *entry;
235 FOR_EACH_PTR(a, entry) {
236 add_ptr_list(b, entry);
237 } END_FOR_EACH_PTR(entry);
238 }
239
240 void __free_ptr_list(struct ptr_list **listp)
241 {
242 struct ptr_list *tmp, *list = *listp;
243
244 if (!list)
245 return;
246
247 list->prev->next = NULL;
248 while (list) {
249 tmp = list;
250 list = list->next;
251 __free_ptrlist(tmp);
252 }
253
254 *listp = NULL;
255 }