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