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
  26 #if 0
  27 static void hash_consistency_check(struct thash_head *head)
  28 {
  29         uint32_t i;
  30         struct thash_item *item, *prev;
  31
  32         for (i = 0; i < HASH_SIZE(*head); i++) {
  33                 item = head->entries[i];
  34                 prev = NULL;
  35                 while (item) {
  36                         assert(HASH_KEY(*head, item->hashval) == i);
  37                         assert(!prev || item->hashval >= prev->hashval);
  38                         prev = item;
  39                         item = item->next;
  40                 }
  41         }
  42 }
  43 #else
  44 #define hash_consistency_check(x)
  45 #endif
  46
  47 void typesafe_hash_grow(struct thash_head *head)
  48 {
  49         uint32_t newsize = head->count, i, j;
  50         uint8_t newshift, delta;
  51
  52         hash_consistency_check(head);
  53
  54         newsize |= newsize >> 1;
  55         newsize |= newsize >> 2;
  56         newsize |= newsize >> 4;
  57         newsize |= newsize >> 8;
  58         newsize |= newsize >> 16;
  59         newsize++;
  60         newshift = __builtin_ctz(newsize) + 1;
  61
  62         if (head->maxshift && newshift > head->maxshift)
  63                 newshift = head->maxshift;
  64         if (newshift == head->tabshift)
  65                 return;
  66         newsize = _HASH_SIZE(newshift);
  67
  68         head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
  69                         sizeof(head->entries[0]) * newsize);
  70         memset(head->entries + HASH_SIZE(*head), 0,
  71                         sizeof(head->entries[0]) *
  72                                 (newsize - HASH_SIZE(*head)));
  73
  74         delta = newshift - head->tabshift;
  75
  76         i = HASH_SIZE(*head);
  77         if (i == 0)
  78                 goto out;
  79         do {
  80                 struct thash_item **apos, *item;
  81
  82                 i--;
  83                 apos = &head->entries[i];
  84
  85                 for (j = 0; j < (1U << delta); j++) {
  86                         item = *apos;
  87                         *apos = NULL;
  88
  89                         head->entries[(i << delta) + j] = item;
  90                         apos = &head->entries[(i << delta) + j];
  91
  92                         while ((item = *apos)) {
  93                                 uint32_t midbits;
  94                                 midbits = _HASH_KEY(newshift, item->hashval);
  95                                 midbits &= (1 << delta) - 1;
  96                                 if (midbits > j)
  97                                         break;
  98                                 apos = &item->next;
  99                         }
 100                 }
 101         } while (i > 0);
 102
 103 out:
 104         head->tabshift = newshift;
 105         hash_consistency_check(head);
 106 }
 107
 108 void typesafe_hash_shrink(struct thash_head *head)
 109 {
 110         uint32_t newsize = head->count, i, j;
 111         uint8_t newshift, delta;
 112
 113         hash_consistency_check(head);
 114
 115         if (!head->count) {
 116                 XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries);
 117                 head->tabshift = 0;
 118                 return;
 119         }
 120
 121         newsize |= newsize >> 1;
 122         newsize |= newsize >> 2;
 123         newsize |= newsize >> 4;
 124         newsize |= newsize >> 8;
 125         newsize |= newsize >> 16;
 126         newsize++;
 127         newshift = __builtin_ctz(newsize) + 1;
 128
 129         if (head->minshift && newshift < head->minshift)
 130                 newshift = head->minshift;
 131         if (newshift == head->tabshift)
 132                 return;
 133         newsize = _HASH_SIZE(newshift);
 134
 135         delta = head->tabshift - newshift;
 136
 137         for (i = 0; i < newsize; i++) {
 138                 struct thash_item **apos = &head->entries[i];
 139
 140                 for (j = 0; j < (1U << delta); j++) {
 141                         *apos = head->entries[(i << delta) + j];
 142                         while (*apos)
 143                                 apos = &(*apos)->next;
 144                 }
 145         }
 146         head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
 147                         sizeof(head->entries[0]) * newsize);
 148         head->tabshift = newshift;
 149
 150         hash_consistency_check(head);
 151 }
 152
 153 /* skiplist */
 154
 155 static inline struct sskip_item *sl_level_get(struct sskip_item *item,
 156                         size_t level)
 157 {
 158         if (level < SKIPLIST_OVERFLOW)
 159                 return item->next[level];
 160         if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
 161                 return item->next[level];
 162
 163         uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 164         ptrval &= UINTPTR_MAX - 3;
 165         struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 166         return oflow->next[level - SKIPLIST_OVERFLOW];
 167 }
 168
 169 static inline void sl_level_set(struct sskip_item *item, size_t level,
 170                 struct sskip_item *value)
 171 {
 172         if (level < SKIPLIST_OVERFLOW)
 173                 item->next[level] = value;
 174         else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
 175                 item->next[level] = value;
 176         else {
 177                 uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 178                 ptrval &= UINTPTR_MAX - 3;
 179                 struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 180                 oflow->next[level - SKIPLIST_OVERFLOW] = value;
 181         }
 182 }
 183
 184 struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
 185                 struct sskip_item *item,
 186                 int (*cmpfn)(const struct sskip_item *a,
 187                                 const struct sskip_item *b))
 188 {
 189         size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel;
 190         struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext;
 191         int cmpval;
 192
 193         /* level / newlevel are 1-counted here */
 194         newlevel = __builtin_ctz(random()) + 1;
 195         if (newlevel > SKIPLIST_MAXDEPTH)
 196                 newlevel = SKIPLIST_MAXDEPTH;
 197
 198         next = NULL;
 199         while (level >= newlevel) {
 200                 next = sl_level_get(prev, level - 1);
 201                 if (!next) {
 202                         level--;
 203                         continue;
 204                 }
 205                 cmpval = cmpfn(next, item);
 206                 if (cmpval < 0) {
 207                         prev = next;
 208                         continue;
 209                 } else if (cmpval == 0) {
 210                         return next;
 211                 }
 212                 level--;
 213         }
 214
 215         /* check for duplicate item - could be removed if code doesn't rely
 216          * on it, but not really work the complication. */
 217         auxlevel = level;
 218         auxprev = prev;
 219         while (auxlevel) {
 220                 auxlevel--;
 221                 auxnext = sl_level_get(auxprev, auxlevel);
 222                 cmpval = 1;
 223                 while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) {
 224                         auxprev = auxnext;
 225                         auxnext = sl_level_get(auxprev, auxlevel);
 226                 }
 227                 if (cmpval == 0)
 228                         return auxnext;
 229         };
 230
 231         head->count++;
 232         memset(item, 0, sizeof(*item));
 233         if (newlevel > SKIPLIST_EMBED) {
 234                 struct sskip_overflow *oflow;
 235                 oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *)
 236                                 * (newlevel - SKIPLIST_OVERFLOW));
 237                 item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *)
 238                                 ((uintptr_t)oflow | 1);
 239         }
 240
 241         sl_level_set(item, level, next);
 242         sl_level_set(prev, level, item);
 243         /* level is now 0-counted and < newlevel*/
 244         while (level) {
 245                 level--;
 246                 next = sl_level_get(prev, level);
 247                 while (next && cmpfn(next, item) < 0) {
 248                         prev = next;
 249                         next = sl_level_get(prev, level);
 250                 }
 251
 252                 sl_level_set(item, level, next);
 253                 sl_level_set(prev, level, item);
 254         };
 255         return NULL;
 256 }
 257
 258 /* NOTE: level counting below is 1-based since that makes the code simpler! */
 259
 260 struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
 261                 const struct sskip_item *item, int (*cmpfn)(
 262                                 const struct sskip_item *a,
 263                                 const struct sskip_item *b))
 264 {
 265         size_t level = SKIPLIST_MAXDEPTH;
 266         struct sskip_item *prev = &head->hitem, *next;
 267         int cmpval;
 268
 269         while (level) {
 270                 next = sl_level_get(prev, level - 1);
 271                 if (!next) {
 272                         level--;
 273                         continue;
 274                 }
 275                 cmpval = cmpfn(next, item);
 276                 if (cmpval < 0) {
 277                         prev = next;
 278                         continue;
 279                 }
 280                 if (cmpval == 0)
 281                         return next;
 282                 level--;
 283         }
 284         return NULL;
 285 }
 286
 287 struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
 288                 const struct sskip_item *item, int (*cmpfn)(
 289                                 const struct sskip_item *a,
 290                                 const struct sskip_item *b))
 291 {
 292         size_t level = SKIPLIST_MAXDEPTH;
 293         struct sskip_item *prev = &head->hitem, *next;
 294         int cmpval;
 295
 296         while (level) {
 297                 next = sl_level_get(prev, level - 1);
 298                 if (!next) {
 299                         level--;
 300                         continue;
 301                 }
 302                 cmpval = cmpfn(next, item);
 303                 if (cmpval < 0) {
 304                         prev = next;
 305                         continue;
 306                 }
 307                 if (cmpval == 0)
 308                         return next;
 309                 level--;
 310         }
 311         return next;
 312 }
 313
 314 struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
 315                 const struct sskip_item *item, int (*cmpfn)(
 316                                 const struct sskip_item *a,
 317                                 const struct sskip_item *b))
 318 {
 319         size_t level = SKIPLIST_MAXDEPTH;
 320         struct sskip_item *prev = &head->hitem, *next, *best = NULL;
 321         int cmpval;
 322
 323         while (level) {
 324                 next = sl_level_get(prev, level - 1);
 325                 if (!next) {
 326                         level--;
 327                         continue;
 328                 }
 329                 cmpval = cmpfn(next, item);
 330                 if (cmpval < 0) {
 331                         best = prev = next;
 332                         continue;
 333                 }
 334                 level--;
 335         }
 336         return best;
 337 }
 338
 339 void typesafe_skiplist_del(struct sskip_head *head, struct sskip_item *item,
 340                 int (*cmpfn)(const struct sskip_item *a,
 341                                 const struct sskip_item *b))
 342 {
 343         size_t level = SKIPLIST_MAXDEPTH;
 344         struct sskip_item *prev = &head->hitem, *next;
 345         int cmpval;
 346
 347         while (level) {
 348                 next = sl_level_get(prev, level - 1);
 349                 if (!next) {
 350                         level--;
 351                         continue;
 352                 }
 353                 if (next == item) {
 354                         sl_level_set(prev, level - 1,
 355                                 sl_level_get(item, level - 1));
 356                         level--;
 357                         continue;
 358                 }
 359                 cmpval = cmpfn(next, item);
 360                 if (cmpval < 0) {
 361                         prev = next;
 362                         continue;
 363                 }
 364                 level--;
 365         }
 366
 367         /* TBD: assert when trying to remove non-existing item? */
 368         head->count--;
 369
 370         if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
 371                 uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
 372                 ptrval &= UINTPTR_MAX - 3;
 373                 struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
 374                 XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
 375         }
 376         memset(item, 0, sizeof(*item));
 377 }