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 } 256