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