Print this page
11972 resync smatch
   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 }
   1 /*
   2  * ptrlist.c
   3  *


   4  * (C) Copyright Linus Torvalds 2003-2005
   5  */
   6 
   7 ///
   8 // Pointer list manipulation
   9 // -------------------------
  10 
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <assert.h>
  14 
  15 #include "ptrlist.h"
  16 #include "allocate.h"
  17 #include "compat.h"
  18 
  19 __DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
  20 __ALLOCATOR(struct ptr_list, "ptr list", ptrlist);
  21 __ALLOCATOR(struct ptr_list, "rl ptr list", rl_ptrlist);
  22 
  23 ///
  24 // get the size of a ptrlist
  25 // @head: the head of the list
  26 // @return: the size of the list given by @head.
  27 int ptr_list_size(struct ptr_list *head)
  28 {
  29         int nr = 0;
  30 
  31         if (head) {
  32                 struct ptr_list *list = head;
  33                 do {
  34                         nr += list->nr - list->rm;
  35                 } while ((list = list->next) != head);
  36         }
  37         return nr;
  38 }
  39 
  40 ///
  41 // test if a list is empty
  42 // @head: the head of the list
  43 // @return: ``true`` if the list is empty, ``false`` otherwise.
  44 bool ptr_list_empty(const struct ptr_list *head)
  45 {
  46         const struct ptr_list *list = head;
  47 
  48         if (!head)
  49                 return true;
  50 
  51         do {
  52                 if (list->nr - list->rm)
  53                         return false;
  54         } while ((list = list->next) != head);
  55 
  56         return true;
  57 }
  58 
  59 ///
  60 // test is a list contains more than one element
  61 // @head: the head of the list
  62 // @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
  63 bool ptr_list_multiple(const struct ptr_list *head)
  64 {
  65         const struct ptr_list *list = head;
  66         int nr = 0;
  67 
  68         if (!head)
  69                 return false;
  70 
  71         do {
  72                 nr += list->nr - list->rm;
  73                 if (nr > 1)
  74                         return true;
  75         } while ((list = list->next) != head);
  76 
  77         return false;
  78 }
  79 
  80 ///
  81 // get the first element of a ptrlist
  82 // @head: the head of the list
  83 // @return: the first element of the list or ``NULL`` if the list is empty
  84 void *first_ptr_list(struct ptr_list *head)
  85 {
  86         struct ptr_list *list = head;
  87 
  88         if (!head)
  89                 return NULL;
  90 
  91         while (list->nr == 0) {
  92                 list = list->next;
  93                 if (list == head)
  94                         return NULL;
  95         }
  96         return PTR_ENTRY_NOTAG(list, 0);
  97 }
  98 
  99 ///
 100 // get the last element of a ptrlist
 101 // @head: the head of the list
 102 // @return: the last element of the list or ``NULL`` if the list is empty
 103 void *last_ptr_list(struct ptr_list *head)
 104 {
 105         struct ptr_list *list;
 106 
 107         if (!head)
 108                 return NULL;
 109         list = head->prev;
 110         while (list->nr == 0) {
 111                 if (list == head)
 112                         return NULL;
 113                 list = list->prev;
 114         }
 115         return PTR_ENTRY_NOTAG(list, list->nr-1);
 116 }
 117 
 118 ///
 119 // get the nth element of a ptrlist
 120 // @head: the head of the list
 121 // @return: the nth element of the list or ``NULL`` if the list is too short.
 122 void *ptr_list_nth_entry(struct ptr_list *list, unsigned int idx)
 123 {
 124         struct ptr_list *head = list;
 125 
 126         if (!head)
 127                 return NULL;
 128 
 129         do {
 130                 unsigned int nr = list->nr;
 131 
 132                 if (idx < nr)
 133                         return list->list[idx];
 134                 else
 135                         idx -= nr;
 136         } while ((list = list->next) != head);
 137         return NULL;
 138 }
 139 
 140 ///
 141 // linearize the entries of a list
 142 //
 143 // @head: the list to be linearized
 144 // @arr: a ``void*`` array to fill with @head's entries
 145 // @max: the maximum number of entries to store into @arr
 146 // @return: the number of entries linearized.
 147 //
 148 // Linearize the entries of a list up to a total of @max,
 149 // and return the nr of entries linearized.
 150 //
 151 // The array to linearize into (@arr) should really
 152 // be ``void *x[]``, but we want to let people fill in any kind
 153 // of pointer array, so let's just call it ``void **``.
 154 int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
 155 {
 156         int nr = 0;
 157         if (head && max > 0) {
 158                 struct ptr_list *list = head;
 159 
 160                 do {
 161                         int i = list->nr;
 162                         if (i > max) 
 163                                 i = max;
 164                         memcpy(arr, list->list, i*sizeof(void *));
 165                         arr += i;
 166                         nr += i;
 167                         max -= i;
 168                         if (!max)
 169                                 break;
 170                 } while ((list = list->next) != head);
 171         }
 172         return nr;
 173 }
 174 
 175 ///
 176 // pack a ptrlist
 177 //
 178 // @listp: a pointer to the list to be packed.
 179 //
 180 // When we've walked the list and deleted entries,
 181 // we may need to re-pack it so that we don't have
 182 // any empty blocks left (empty blocks upset the
 183 // walking code).
 184 void pack_ptr_list(struct ptr_list **listp)
 185 {
 186         struct ptr_list *head = *listp;
 187 
 188         if (head) {
 189                 struct ptr_list *entry = head;
 190                 do {
 191                         struct ptr_list *next;
 192 restart:
 193                         next = entry->next;
 194                         if (!entry->nr) {
 195                                 struct ptr_list *prev;
 196                                 if (next == entry) {
 197                                         __free_ptrlist(entry);
 198                                         *listp = NULL;
 199                                         return;
 200                                 }
 201                                 prev = entry->prev;
 202                                 prev->next = next;
 203                                 next->prev = prev;
 204                                 __free_ptrlist(entry);
 205                                 if (entry == head) {
 206                                         *listp = next;
 207                                         head = next;
 208                                         entry = next;
 209                                         goto restart;
 210                                 }
 211                         }
 212                         entry = next;
 213                 } while (entry != head);
 214         }
 215 }               
 216 
 217 ///
 218 // split a ptrlist block
 219 // @head: the ptrlist block to be splitted
 220 //
 221 // A new block is inserted just after @head and the entries
 222 // at the half end of @head are moved to this new block.
 223 // The goal being to create space inside @head for a new entry.
 224 void split_ptr_list_head(struct ptr_list *head)
 225 {
 226         int old = head->nr, nr = old / 2;
 227         struct ptr_list *newlist = __alloc_ptrlist(0);
 228         struct ptr_list *next = head->next;
 229 
 230         old -= nr;
 231         head->nr = old;
 232         newlist->next = next;
 233         next->prev = newlist;
 234         newlist->prev = head;
 235         head->next = newlist;
 236         newlist->nr = nr;
 237         memcpy(newlist->list, head->list + old, nr * sizeof(void *));
 238         memset(head->list + old, 0xf0, nr * sizeof(void *));
 239 }
 240 
 241 int rl_ptrlist_hack;
 242 ///
 243 // add an entry to a ptrlist
 244 // @listp: a pointer to the list
 245 // @ptr: the entry to add to the list
 246 // @return: the address where the new entry is stored.
 247 //
 248 // :note: code must not use this function and should use
 249 //      :func:`add_ptr_list` instead.
 250 void **__add_ptr_list(struct ptr_list **listp, void *ptr)
 251 {
 252         struct ptr_list *list = *listp;
 253         struct ptr_list *last = NULL; /* gcc complains needlessly */
 254         void **ret;
 255         int nr;
 256 





 257         if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
 258                 struct ptr_list *newlist;
 259 
 260                 if (rl_ptrlist_hack)
 261                         newlist = __alloc_rl_ptrlist(0);
 262                 else
 263                         newlist = __alloc_ptrlist(0);
 264                 if (!list) {
 265                         newlist->next = newlist;
 266                         newlist->prev = newlist;
 267                         *listp = newlist;
 268                 } else {
 269                         newlist->prev = last;
 270                         newlist->next = list;
 271                         list->prev = newlist;
 272                         last->next = newlist;
 273                 }
 274                 last = newlist;
 275                 nr = 0;
 276         }
 277         ret = last->list + nr;
 278         *ret = ptr;
 279         nr++;
 280         last->nr = nr;
 281         return ret;
 282 }
 283 
 284 ///
 285 // add a tagged entry to a ptrlist
 286 // @listp: a pointer to the list
 287 // @ptr: the entry to add to the list
 288 // @tag: the tag to add to @ptr
 289 // @return: the address where the new entry is stored.
 290 //
 291 // :note: code must not use this function and should use
 292 //      :func:`add_ptr_list_tag` instead.
 293 void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
 294 {
 295         /* The low two bits are reserved for tags */
 296         assert((3 & (unsigned long)ptr) == 0);
 297         assert((~3 & tag) == 0);
 298 
 299         ptr = (void *)(tag | (unsigned long)ptr);
 300 
 301         return __add_ptr_list(listp, ptr);
 302 }
 303 
 304 ///
 305 // test if some entry is already present in a ptrlist
 306 // @list: the head of the list
 307 // @entry: the entry to test
 308 // @return: ``true`` if the entry is already present, ``false`` otherwise.
 309 bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry)
 310 {
 311         const struct ptr_list *list = head;
 312 
 313         if (!head)
 314                 return false;
 315         do {
 316                 int nr = list->nr;
 317                 int i;
 318                 for (i = 0; i < nr; i++)
 319                         if (list->list[i] == entry)
 320                                 return true;
 321         } while ((list = list->next) != head);
 322         return false;
 323 }
 324 
 325 ///
 326 // delete an entry from a ptrlist
 327 // @list: a pointer to the list
 328 // @entry: the item to be deleted
 329 // @count: the minimum number of times @entry should be deleted or 0.
 330 int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
 331 {
 332         void *ptr;
 333 
 334         FOR_EACH_PTR(*list, ptr) {
 335                 if (ptr == entry) {
 336                         DELETE_CURRENT_PTR(ptr);
 337                         if (!--count)
 338                                 goto out;
 339                 }
 340         } END_FOR_EACH_PTR(ptr);
 341         assert(count <= 0);
 342 out:
 343         pack_ptr_list(list);
 344         return count;
 345 }
 346 
 347 ///
 348 // replace an entry in a ptrlist
 349 // @list: a pointer to the list
 350 // @old_ptr: the entry to be replaced
 351 // @new_ptr: the new entry
 352 // @count: the minimum number of times @entry should be deleted or 0.
 353 int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr,
 354         void *new_ptr, int count)
 355 {
 356         void *ptr;
 357 
 358         FOR_EACH_PTR(*list, ptr) {
 359                 if (ptr==old_ptr) {
 360                         REPLACE_CURRENT_PTR(ptr, new_ptr);
 361                         if (!--count)
 362                                 goto out;
 363                 }
 364         }END_FOR_EACH_PTR(ptr);
 365         assert(count <= 0);
 366 out:
 367         return count;
 368 }
 369 
 370 ///
 371 // remove the last entry of a ptrlist
 372 // @head: a pointer to the list
 373 // @return: the last elemant of the list or NULL if the list is empty.
 374 //
 375 // :note: this doesn't repack the list
 376 void * undo_ptr_list_last(struct ptr_list **head)
 377 {
 378         struct ptr_list *last, *first = *head;
 379 
 380         if (!first)
 381                 return NULL;
 382         last = first;
 383         do {
 384                 last = last->prev;
 385                 if (last->nr) {
 386                         void *ptr;
 387                         int nr = --last->nr;
 388                         ptr = last->list[nr];
 389                         last->list[nr] = (void *)0xf1f1f1f1;
 390                         return ptr;
 391                 }
 392         } while (last != first);
 393         return NULL;
 394 }
 395 
 396 ///
 397 // remove the last entry and repack the list
 398 // @head: a pointer to the list
 399 // @return: the last elemant of the list or NULL if the list is empty.
 400 void * delete_ptr_list_last(struct ptr_list **head)
 401 {
 402         void *ptr = NULL;
 403         struct ptr_list *last, *first = *head;
 404 
 405         if (!first)
 406                 return NULL;
 407         last = first->prev;
 408         if (last->nr)
 409                 ptr = last->list[--last->nr];
 410         if (last->nr <=0) {
 411                 first->prev = last->prev;
 412                 last->prev->next = first;
 413                 if (last == first)
 414                         *head = NULL;
 415                 __free_ptrlist(last);
 416         }
 417         return ptr;
 418 }
 419 
 420 ///
 421 // concat two ptrlists
 422 // @a: the source list
 423 // @b: a pointer to the destination list.
 424 // The element of @a are added at the end of @b.
 425 void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
 426 {
 427         void *entry;
 428         FOR_EACH_PTR(a, entry) {
 429                 add_ptr_list(b, entry);
 430         } END_FOR_EACH_PTR(entry);
 431 }
 432 
 433 ///
 434 // copy the elements of a list at the end of another list.
 435 // @listp: a pointer to the destination list.
 436 // @src: the head of the source list.
 437 void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src)
 438 {
 439         struct ptr_list *head, *tail;
 440         struct ptr_list *cur = src;
 441         int idx;
 442 
 443         if (!src)
 444                 return;
 445         head = *listp;
 446         if (!head) {
 447                 *listp = src;
 448                 return;
 449         }
 450 
 451         tail = head->prev;
 452         idx = tail->nr;
 453         do {
 454                 struct ptr_list *next;
 455                 int nr = cur->nr;
 456                 int i;
 457                 for (i = 0; i < nr;) {
 458                         void *ptr = cur->list[i++];
 459                         if (!ptr)
 460                                 continue;
 461                         if (idx >= LIST_NODE_NR) {
 462                                 struct ptr_list *prev = tail;
 463                                 tail = __alloc_ptrlist(0);
 464                                 prev->next = tail;
 465                                 tail->prev = prev;
 466                                 prev->nr = idx;
 467                                 idx = 0;
 468                         }
 469                         tail->list[idx++] = ptr;
 470                 }
 471 
 472                 next = cur->next;
 473                 __free_ptrlist(cur);
 474                 cur = next;
 475         } while (cur != src);
 476 
 477         tail->nr = idx;
 478         head->prev = tail;
 479         tail->next = head;
 480 }
 481 
 482 ///
 483 // free a ptrlist
 484 // @listp: a pointer to the list
 485 // Each blocks of the list are freed (but the entries
 486 // themselves are not freed).
 487 //
 488 // :note: code must not use this function and should use
 489 //      the macro :func:`free_ptr_list` instead.
 490 void __free_ptr_list(struct ptr_list **listp)
 491 {
 492         struct ptr_list *tmp, *list = *listp;
 493 
 494         if (!list)
 495                 return;
 496 
 497         list->prev->next = NULL;
 498         while (list) {
 499                 tmp = list;
 500                 list = list->next;
 501                 __free_ptrlist(tmp);
 502         }
 503 
 504         *listp = NULL;
 505 }