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                                         *listp = NULL;
  76                                         return;
  77                                 }
  78                                 prev = entry->prev;
  79                                 prev->next = next;
  80                                 next->prev = prev;
  81                                 free(entry);
  82                                 if (entry == head) {
  83                                         *listp = next;
  84                                         head = next;
  85                                         entry = next;
  86                                         goto restart;
  87                                 }
  88                         }
  89                         entry = next;
  90                 } while (entry != head);
  91         }
  92 }
  93
  94 void split_ptr_list_head(struct ptr_list *head)
  95 {
  96         int old = head->nr, nr = old / 2;
  97         struct ptr_list *newlist = malloc(sizeof(*newlist));
  98         struct ptr_list *next = head->next;
  99
 100         old -= nr;
 101         head->nr = old;
 102         newlist->next = next;
 103         next->prev = newlist;
 104         newlist->prev = head;
 105         head->next = newlist;
 106         newlist->nr = nr;
 107         memcpy(newlist->list, head->list + old, nr * sizeof(void *));
 108         memset(head->list + old, 0xf0, nr * sizeof(void *));
 109 }
 110
 111 void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
 112 {
 113         struct ptr_list *list = *listp;
 114         struct ptr_list *last = NULL; /* gcc complains needlessly */
 115         void **ret;
 116         int nr;
 117
 118         /* The low two bits are reserved for tags */
 119         assert((3 & (unsigned long)ptr) == 0);
 120         assert((~3 & tag) == 0);
 121         ptr = (void *)(tag | (unsigned long)ptr);
 122
 123         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 124                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 125                 assert(newlist);
 126                 memset(newlist, 0, sizeof(*newlist));
 127                 if (!list) {
 128                         newlist->next = newlist;
 129                         newlist->prev = newlist;
 130                         *listp = newlist;
 131                 } else {
 132                         newlist->prev = last;
 133                         newlist->next = list;
 134                         list->prev = newlist;
 135                         last->next = newlist;
 136                 }
 137                 last = newlist;
 138                 nr = 0;
 139         }
 140         ret = last->list + nr;
 141         *ret = ptr;
 142         nr++;
 143         last->nr = nr;
 144         return ret;
 145 }
 146
 147 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 148 {
 149         void *ptr;
 150
 151         FOR_EACH_PTR(*list, ptr) {
 152                 if (ptr == entry) {
 153                         DELETE_CURRENT_PTR(ptr);
 154                         if (!--count)
 155                                 goto out;
 156                 }
 157         } END_FOR_EACH_PTR(ptr);
 158         assert(count <= 0);
 159 out:
 160         pack_ptr_list(list);
 161         return count;
 162 }
 163
 164 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
 165 {
 166         void *ptr;
 167
 168         FOR_EACH_PTR(*list, ptr) {
 169                 if (ptr==old_ptr) {
 170                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 171                         if (!--count)
 172                                 goto out;
 173                 }
 174         }END_FOR_EACH_PTR(ptr);
 175         assert(count <= 0);
 176 out:
 177         return count;
 178 }
 179
 180 /* This removes the last entry, but doesn't pack the ptr list */
 181 void * undo_ptr_list_last(struct ptr_list **head)
 182 {
 183         struct ptr_list *last, *first = *head;
 184
 185         if (!first)
 186                 return NULL;
 187         last = first;
 188         do {
 189                 last = last->prev;
 190                 if (last->nr) {
 191                         void *ptr;
 192                         int nr = --last->nr;
 193                         ptr = last->list[nr];
 194                         last->list[nr] = (void *)0xf1f1f1f1;
 195                         return ptr;
 196                 }
 197         } while (last != first);
 198         return NULL;
 199 }
 200
 201 void * delete_ptr_list_last(struct ptr_list **head)
 202 {
 203         void *ptr = NULL;
 204         struct ptr_list *last, *first = *head;
 205
 206         if (!first)
 207                 return NULL;
 208         last = first->prev;
 209         if (last->nr)
 210                 ptr = last->list[--last->nr];
 211         if (last->nr <=0) {
 212                 first->prev = last->prev;
 213                 last->prev->next = first;
 214                 if (last == first)
 215                         *head = NULL;
 216                 free(last);
 217         }
 218         return ptr;
 219 }
 220
 221 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 222 {
 223         void *entry;
 224         FOR_EACH_PTR(a, entry) {
 225                 add_ptr_list(b, entry);
 226         } END_FOR_EACH_PTR(entry);
 227 }
 228
 229 void __free_ptr_list(struct ptr_list **listp)
 230 {
 231         struct ptr_list *tmp, *list = *listp;
 232
 233         if (!list)
 234                 return;
 235
 236         list->prev->next = NULL;
 237         while (list) {
 238                 tmp = list;
 239                 list = list->next;
 240                 free(tmp);
 241         }
 242
 243         *listp = NULL;
 244 }