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