ptrlist.c

   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 split
 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 element 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 element 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 }