ptrlist.c

   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
  19 int ptr_list_size(struct ptr_list *head)
  20 {
  21         int nr = 0;
  22
  23         if (head) {
  24                 struct ptr_list *list = head;
  25                 do {
  26                         nr += list->nr;
  27                 } while ((list = list->next) != head);
  28         }
  29         return nr;
  30 }
  31
  32 /*
  33  * Linearize the entries of a list up to a total of 'max',
  34  * and return the nr of entries linearized.
  35  *
  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 **".
  39  */
  40 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
  41 {
  42         int nr = 0;
  43         if (head && max > 0) {
  44                 struct ptr_list *list = head;
  45
  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);
  57         }
  58         return nr;
  59 }
  60
  61 /*
  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
  66  */
  67 void pack_ptr_list(struct ptr_list **listp)
  68 {
  69         struct ptr_list *head = *listp;
  70
  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;
  83                                 }
  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;
  93                                 }
  94                         }
  95                         entry = next;
  96                 } while (entry != head);
  97         }
  98 }
  99
 100 void split_ptr_list_head(struct ptr_list *head)
 101 {
 102         int old = head->nr, nr = old / 2;
 103         struct ptr_list *newlist = __alloc_ptrlist(0);
 104         struct ptr_list *next = head->next;
 105
 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 *));
 115 }
 116
 117 void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
 118 {
 119         struct ptr_list *list = *listp;
 120         struct ptr_list *last = NULL; /* gcc complains needlessly */
 121         void **ret;
 122         int nr;
 123
 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);
 128
 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;
 140                 }
 141                 last = newlist;
 142                 nr = 0;
 143         }
 144         ret = last->list + nr;
 145         *ret = ptr;
 146         nr++;
 147         last->nr = nr;
 148         return ret;
 149 }
 150
 151 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 152 {
 153         void *ptr;
 154
 155         FOR_EACH_PTR(*list, ptr) {
 156                 if (ptr == entry) {
 157                         DELETE_CURRENT_PTR(ptr);
 158                         if (!--count)
 159                                 goto out;
 160                 }
 161         } END_FOR_EACH_PTR(ptr);
 162         assert(count <= 0);
 163 out:
 164         pack_ptr_list(list);
 165         return count;
 166 }
 167
 168 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 169 {
 170         void *ptr;
 171
 172         FOR_EACH_PTR(*list, ptr) {
 173                 if (ptr==old_ptr) {
 174                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 175                         if (!--count)
 176                                 goto out;
 177                 }
 178         }END_FOR_EACH_PTR(ptr);
 179         assert(count <= 0);
 180 out:
 181         return count;
 182 }
 183
 184 /* This removes the last entry, but doesn't pack the ptr list */
 185 void * undo_ptr_list_last(struct ptr_list **head)
 186 {
 187         struct ptr_list *last, *first = *head;
 188
 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;
 200                 }
 201         } while (last != first);
 202         return NULL;
 203 }
 204
 205 void * delete_ptr_list_last(struct ptr_list **head)
 206 {
 207         void *ptr = NULL;
 208         struct ptr_list *last, *first = *head;
 209
 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);
 221         }
 222         return ptr;
 223 }
 224
 225 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 226 {
 227         void *entry;
 228         FOR_EACH_PTR(a, entry) {
 229                 add_ptr_list(b, entry);
 230         } END_FOR_EACH_PTR(entry);
 231 }
 232
 233 void __free_ptr_list(struct ptr_list **listp)
 234 {
 235         struct ptr_list *tmp, *list = *listp;
 236
 237         if (!list)
 238                 return;
 239
 240         list->prev->next = NULL;
 241         while (list) {
 242                 tmp = list;
 243                 list = list->next;
 244                 __free_ptrlist(tmp);
 245         }
 246
 247         *listp = NULL;
 248 }