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