lib/typesafe.c

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