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