lib/typesafe.c

   1 /*
   2  * Copyright (c) 2019  David Lamparter, for NetDEF, Inc.
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #ifdef HAVE_CONFIG_H
  18 #include "config.h"
  19 #endif
  20
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include "typesafe.h"
  25 #include "memory.h"
  26 #include "network.h"
  27
  28 DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket");
  29 DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow");
  30 DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array");
  31
  32 struct slist_item typesafe_slist_sentinel = { NULL };
  33
  34 bool typesafe_list_member(const struct slist_head *head,
  35                           const struct slist_item *item)
  36 {
  37         struct slist_item *fromhead = head->first;
  38         struct slist_item **fromnext = (struct slist_item **)&item->next;
  39
  40         while (fromhead != _SLIST_LAST) {
  41                 if (fromhead == item || fromnext == head->last_next)
  42                         return true;
  43
  44                 fromhead = fromhead->next;
  45                 if (!*fromnext || *fromnext == _SLIST_LAST)
  46                         break;
  47                 fromnext = &(*fromnext)->next;
  48         }
  49
  50         return false;
  51 }
  52
  53 bool typesafe_dlist_member(const struct dlist_head *head,
  54                            const struct dlist_item *item)
  55 {
  56         const struct dlist_item *fromhead = head->hitem.next;
  57         const struct dlist_item *fromitem = item->next;
  58
  59         if (!item->prev || !item->next)
  60                 return false;
  61
  62         while (fromhead != &head->hitem && fromitem != item) {
  63                 if (fromitem == &head->hitem || fromhead == item)
  64                         return true;
  65                 fromhead = fromhead->next;
  66                 fromitem = fromitem->next;
  67         }
  68
  69         return false;
  70 }
  71
  72 #if 0
  73 static void hash_consistency_check(struct thash_head *head)
  74 {
  75         uint32_t i;
  76         struct thash_item *item, *prev;
  77
  78         for (i = 0; i < HASH_SIZE(*head); i++) {
  79                 item = head->entries[i];
  80                 prev = NULL;
  81                 while (item) {
  82                         assert(HASH_KEY(*head, item->hashval) == i);
  83                         assert(!prev || item->hashval >= prev->hashval);
  84                         prev = item;
  85                         item = item->next;
  86                 }
  87         }
  88 }
  89 #else
  90 #define hash_consistency_check(x)
  91 #endif
  92
  93 void typesafe_hash_grow(struct thash_head *head)
  94 {
  95         uint32_t newsize = head->count, i, j;
  96         uint8_t newshift, delta;
  97
  98         hash_consistency_check(head);
  99
 100         newsize |= newsize >> 1;
 101         newsize |= newsize >> 2;
 102         newsize |= newsize >> 4;
 103         newsize |= newsize >> 8;
 104         newsize |= newsize >> 16;
 105         newsize++;
 106         newshift = __builtin_ctz(newsize) + 1;
 107
 108         if (head->maxshift && newshift > head->maxshift)
 109                 newshift = head->maxshift;
 110         if (newshift == head->tabshift)
 111                 return;
 112         newsize = _HASH_SIZE(newshift);
 113
 114         head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
 115                         sizeof(head->entries[0]) * newsize);
 116         memset(head->entries + HASH_SIZE(*head), 0,
 117                         sizeof(head->entries[0]) *
 118                                 (newsize - HASH_SIZE(*head)));
 119
 120         delta = newshift - head->tabshift;
 121
 122         i = HASH_SIZE(*head);
 123         if (i == 0)
 124                 goto out;
 125         do {
 126                 struct thash_item **apos, *item;
 127
 128                 i--;
 129                 apos = &head->entries[i];
 130
 131                 for (j = 0; j < (1U << delta); j++) {
 132                         item = *apos;
 133                         *apos = NULL;
 134
 135                         head->entries[(i << delta) + j] = item;
 136                         apos = &head->entries[(i << delta) + j];
 137
 138                         while ((item = *apos)) {
 139                                 uint32_t midbits;
 140                                 midbits = _HASH_KEY(newshift, item->hashval);
 141                                 midbits &= (1 << delta) - 1;
 142                                 if (midbits > j)
 143                                         break;
 144                                 apos = &item->next;
 145                         }
 146                 }
 147         } while (i > 0);
 148
 149 out:
 150         head->tabshift = newshift;
 151         hash_consistency_check(head);
 152 }
 153
 154 void typesafe_hash_shrink(struct thash_head *head)
 155 {
 156         uint32_t newsize = head->count, i, j;
 157         uint8_t newshift, delta;
 158
 159         hash_consistency_check(head);
 160
 161         if (!head->count) {
 162                 XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries);
 163                 head->tabshift = 0;
 164                 return;
 165         }
 166
 167         newsize |= newsize >> 1;
 168         newsize |= newsize >> 2;
 169         newsize |= newsize >> 4;
 170         newsize |= newsize >> 8;
 171         newsize |= newsize >> 16;
 172         newsize++;
 173         newshift = __builtin_ctz(newsize) + 1;
 174
 175         if (head->minshift && newshift < head->minshift)
 176                 newshift = head->minshift;
 177         if (newshift == head->tabshift)
 178                 return;
 179         newsize = _HASH_SIZE(newshift);
 180
 181         delta = head->tabshift - newshift;
 182
 183         for (i = 0; i < newsize; i++) {
 184                 struct thash_item **apos = &head->entries[i];
 185
 186                 for (j = 0; j < (1U << delta); j++) {
 187                         *apos = head->entries[(i << delta) + j];
 188                         while (*apos)
 189                                 apos = &(*apos)->next;
 190                 }
 191         }
 192         head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
 193                         sizeof(head->entries[0]) * newsize);
 194         head->tabshift = newshift;
 195
 196         hash_consistency_check(head);
 197 }
 198
 199 /* skiplist */
 200
 201 static inline struct sskip_item *sl_level_get(const struct sskip_item *item,
 202                         size_t level)
 203 {
 204         if (level < SKIPLIST_OVERFLOW)
 205                 return item->next[level];
 206         if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
 207                 return item->next[level];
 208
 209         uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 210         ptrval &= UINTPTR_MAX - 3;
 211         struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 212         return oflow->next[level - SKIPLIST_OVERFLOW];
 213 }
 214
 215 static inline void sl_level_set(struct sskip_item *item, size_t level,
 216                 struct sskip_item *value)
 217 {
 218         if (level < SKIPLIST_OVERFLOW)
 219                 item->next[level] = value;
 220         else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
 221                 item->next[level] = value;
 222         else {
 223                 uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 224                 ptrval &= UINTPTR_MAX - 3;
 225                 struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 226                 oflow->next[level - SKIPLIST_OVERFLOW] = value;
 227         }
 228 }
 229
 230 struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
 231                 struct sskip_item *item,
 232                 int (*cmpfn)(const struct sskip_item *a,
 233                                 const struct sskip_item *b))
 234 {
 235         size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel;
 236         struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext;
 237         int cmpval;
 238
 239         /* level / newlevel are 1-counted here */
 240         newlevel = __builtin_ctz(frr_weak_random()) + 1;
 241         if (newlevel > SKIPLIST_MAXDEPTH)
 242                 newlevel = SKIPLIST_MAXDEPTH;
 243
 244         next = NULL;
 245         while (level >= newlevel) {
 246                 next = sl_level_get(prev, level - 1);
 247                 if (!next) {
 248                         level--;
 249                         continue;
 250                 }
 251                 cmpval = cmpfn(next, item);
 252                 if (cmpval < 0) {
 253                         prev = next;
 254                         continue;
 255                 } else if (cmpval == 0) {
 256                         return next;
 257                 }
 258                 level--;
 259         }
 260
 261         /* check for duplicate item - could be removed if code doesn't rely
 262          * on it, but not really work the complication. */
 263         auxlevel = level;
 264         auxprev = prev;
 265         while (auxlevel) {
 266                 auxlevel--;
 267                 auxnext = sl_level_get(auxprev, auxlevel);
 268                 cmpval = 1;
 269                 while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) {
 270                         auxprev = auxnext;
 271                         auxnext = sl_level_get(auxprev, auxlevel);
 272                 }
 273                 if (cmpval == 0)
 274                         return auxnext;
 275         };
 276
 277         head->count++;
 278         memset(item, 0, sizeof(*item));
 279         if (newlevel > SKIPLIST_EMBED) {
 280                 struct sskip_overflow *oflow;
 281                 oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *)
 282                                 * (newlevel - SKIPLIST_OVERFLOW));
 283                 item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *)
 284                                 ((uintptr_t)oflow | 1);
 285         }
 286
 287         sl_level_set(item, level, next);
 288         sl_level_set(prev, level, item);
 289         /* level is now 0-counted and < newlevel*/
 290         while (level) {
 291                 level--;
 292                 next = sl_level_get(prev, level);
 293                 while (next && cmpfn(next, item) < 0) {
 294                         prev = next;
 295                         next = sl_level_get(prev, level);
 296                 }
 297
 298                 sl_level_set(item, level, next);
 299                 sl_level_set(prev, level, item);
 300         };
 301         return NULL;
 302 }
 303
 304 /* NOTE: level counting below is 1-based since that makes the code simpler! */
 305
 306 const struct sskip_item *typesafe_skiplist_find(
 307                 const struct sskip_head *head,
 308                 const struct sskip_item *item, int (*cmpfn)(
 309                                 const struct sskip_item *a,
 310                                 const struct sskip_item *b))
 311 {
 312         size_t level = SKIPLIST_MAXDEPTH;
 313         const struct sskip_item *prev = &head->hitem, *next;
 314         int cmpval;
 315
 316         while (level) {
 317                 next = sl_level_get(prev, level - 1);
 318                 if (!next) {
 319                         level--;
 320                         continue;
 321                 }
 322                 cmpval = cmpfn(next, item);
 323                 if (cmpval < 0) {
 324                         prev = next;
 325                         continue;
 326                 }
 327                 if (cmpval == 0)
 328                         return next;
 329                 level--;
 330         }
 331         return NULL;
 332 }
 333
 334 const struct sskip_item *typesafe_skiplist_find_gteq(
 335                 const struct sskip_head *head,
 336                 const struct sskip_item *item, int (*cmpfn)(
 337                                 const struct sskip_item *a,
 338                                 const struct sskip_item *b))
 339 {
 340         size_t level = SKIPLIST_MAXDEPTH;
 341         const struct sskip_item *prev = &head->hitem, *next;
 342         int cmpval;
 343
 344         while (level) {
 345                 next = sl_level_get(prev, level - 1);
 346                 if (!next) {
 347                         level--;
 348                         continue;
 349                 }
 350                 cmpval = cmpfn(next, item);
 351                 if (cmpval < 0) {
 352                         prev = next;
 353                         continue;
 354                 }
 355                 if (cmpval == 0)
 356                         return next;
 357                 level--;
 358         }
 359         return next;
 360 }
 361
 362 const struct sskip_item *typesafe_skiplist_find_lt(
 363                 const struct sskip_head *head,
 364                 const struct sskip_item *item, int (*cmpfn)(
 365                                 const struct sskip_item *a,
 366                                 const struct sskip_item *b))
 367 {
 368         size_t level = SKIPLIST_MAXDEPTH;
 369         const struct sskip_item *prev = &head->hitem, *next, *best = NULL;
 370         int cmpval;
 371
 372         while (level) {
 373                 next = sl_level_get(prev, level - 1);
 374                 if (!next) {
 375                         level--;
 376                         continue;
 377                 }
 378                 cmpval = cmpfn(next, item);
 379                 if (cmpval < 0) {
 380                         best = prev = next;
 381                         continue;
 382                 }
 383                 level--;
 384         }
 385         return best;
 386 }
 387
 388 struct sskip_item *typesafe_skiplist_del(
 389         struct sskip_head *head, struct sskip_item *item,
 390         int (*cmpfn)(const struct sskip_item *a, const struct sskip_item *b))
 391 {
 392         size_t level = SKIPLIST_MAXDEPTH;
 393         struct sskip_item *prev = &head->hitem, *next;
 394         int cmpval;
 395         bool found = false;
 396
 397         while (level) {
 398                 next = sl_level_get(prev, level - 1);
 399                 if (!next) {
 400                         level--;
 401                         continue;
 402                 }
 403                 if (next == item) {
 404                         sl_level_set(prev, level - 1,
 405                                 sl_level_get(item, level - 1));
 406                         level--;
 407                         found = true;
 408                         continue;
 409                 }
 410                 cmpval = cmpfn(next, item);
 411                 if (cmpval < 0) {
 412                         prev = next;
 413                         continue;
 414                 }
 415                 level--;
 416         }
 417
 418         if (!found)
 419                 return NULL;
 420
 421         /* TBD: assert when trying to remove non-existing item? */
 422         head->count--;
 423
 424         if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
 425                 uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 426                 ptrval &= UINTPTR_MAX - 3;
 427                 struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 428                 XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
 429         }
 430         memset(item, 0, sizeof(*item));
 431
 432         return item;
 433 }
 434
 435 struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head)
 436 {
 437         size_t level = SKIPLIST_MAXDEPTH;
 438         struct sskip_item *prev = &head->hitem, *next, *item;
 439
 440         item = sl_level_get(prev, 0);
 441         if (!item)
 442                 return NULL;
 443
 444         do {
 445                 level--;
 446
 447                 next = sl_level_get(prev, level);
 448                 if (next != item)
 449                         continue;
 450
 451                 sl_level_set(prev, level, sl_level_get(item, level));
 452         } while (level);
 453
 454         head->count--;
 455
 456         if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
 457                 uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 458                 ptrval &= UINTPTR_MAX - 3;
 459                 struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 460                 XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
 461         }
 462         memset(item, 0, sizeof(*item));
 463
 464         return item;
 465 }
 466
 467 /* heap */
 468
 469 #if 0
 470 static void heap_consistency_check(struct heap_head *head,
 471                                    int (*cmpfn)(const struct heap_item *a,
 472                                                 const struct heap_item *b),
 473                                    uint32_t pos)
 474 {
 475         uint32_t rghtpos = pos + 1;
 476         uint32_t downpos = HEAP_NARY * (pos + 1);
 477
 478         if (pos + 1 > ~0U / HEAP_NARY)
 479                 downpos = ~0U;
 480
 481         if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) {
 482                 assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0);
 483                 heap_consistency_check(head, cmpfn, rghtpos);
 484         }
 485         if (downpos < head->count) {
 486                 assert(cmpfn(head->array[downpos], head->array[pos]) >= 0);
 487                 heap_consistency_check(head, cmpfn, downpos);
 488         }
 489 }
 490 #else
 491 #define heap_consistency_check(head, cmpfn, pos)
 492 #endif
 493
 494 void typesafe_heap_resize(struct heap_head *head, bool grow)
 495 {
 496         uint32_t newsize;
 497
 498         if (grow) {
 499                 newsize = head->arraysz;
 500                 if (newsize <= 36)
 501                         newsize = 72;
 502                 else if (newsize < 262144)
 503                         newsize += newsize / 2;
 504                 else if (newsize < 0xaaaa0000)
 505                         newsize += newsize / 3;
 506                 else
 507                         assert(!newsize);
 508         } else if (head->count > 0) {
 509                 newsize = head->count;
 510         } else {
 511                 XFREE(MTYPE_HEAP_ARRAY, head->array);
 512                 head->arraysz = 0;
 513                 return;
 514         }
 515
 516         newsize += HEAP_NARY - 1;
 517         newsize &= ~(HEAP_NARY - 1);
 518         if (newsize == head->arraysz)
 519                 return;
 520
 521         head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array,
 522                                newsize * sizeof(struct heap_item *));
 523         head->arraysz = newsize;
 524 }
 525
 526 void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos,
 527                 struct heap_item *item,
 528                 int (*cmpfn)(const struct heap_item *a,
 529                              const struct heap_item *b))
 530 {
 531         uint32_t rghtpos, downpos, moveto;
 532
 533         while (1) {
 534                 /* rghtpos: neighbor to the "right", inside block of NARY.
 535                  *          may be invalid if last in block, check nary_last()
 536                  * downpos: first neighbor in the "downwards" block further
 537                  *          away from the root
 538                  */
 539                 rghtpos = pos + 1;
 540
 541                 /* make sure we can use the full 4G items */
 542                 downpos = HEAP_NARY * (pos + 1);
 543                 if (pos + 1 > ~0U / HEAP_NARY)
 544                         /* multiplication overflowed.  ~0U is guaranteed
 545                          * to be an invalid index; size limit is enforced in
 546                          * resize()
 547                          */
 548                         downpos = ~0U;
 549
 550                 /* only used on break */
 551                 moveto = pos;
 552
 553 #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
 554                 if (downpos >= head->count
 555                     || cmpfn(head->array[downpos], item) >= 0) {
 556                         /* not moving down; either at end or down is >= item */
 557                         if (nary_last(pos) || rghtpos >= head->count
 558                             || cmpfn(head->array[rghtpos], item) >= 0)
 559                                 /* not moving right either - got our spot */
 560                                 break;
 561
 562                         moveto = rghtpos;
 563
 564                 /* else: downpos is valid and < item.  choose between down
 565                  * or right (if the latter is an option) */
 566                 } else if (nary_last(pos) || cmpfn(head->array[rghtpos],
 567                                                    head->array[downpos]) >= 0)
 568                         moveto = downpos;
 569                 else
 570                         moveto = rghtpos;
 571 #undef nary_last
 572
 573                 head->array[pos] = head->array[moveto];
 574                 head->array[pos]->index = pos;
 575                 pos = moveto;
 576         }
 577
 578         head->array[moveto] = item;
 579         item->index = moveto;
 580
 581         heap_consistency_check(head, cmpfn, 0);
 582 }
 583
 584 void typesafe_heap_pullup(struct heap_head *head, uint32_t pos,
 585                 struct heap_item *item,
 586                 int (*cmpfn)(const struct heap_item *a,
 587                              const struct heap_item *b))
 588 {
 589         uint32_t moveto;
 590
 591         while (pos != 0) {
 592                 if ((pos & (HEAP_NARY - 1)) == 0)
 593                         moveto = pos / HEAP_NARY - 1;
 594                 else
 595                         moveto = pos - 1;
 596
 597                 if (cmpfn(head->array[moveto], item) <= 0)
 598                         break;
 599
 600                 head->array[pos] = head->array[moveto];
 601                 head->array[pos]->index = pos;
 602
 603                 pos = moveto;
 604         }
 605
 606         head->array[pos] = item;
 607         item->index = pos;
 608
 609         heap_consistency_check(head, cmpfn, 0);
 610 }