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