xsh/ptable.h

   1 /* This is a pointer table implementation essentially copied from the ptr_table
   2  * implementation in perl's sv.c, except that it has been modified to use memory
   3  * shared across threads.
   4  * Copyright goes to the original authors, bug reports to me. */
   5
   6 /* This header is designed to be included several times with different
   7  * definitions for PTABLE_NAME and PTABLE_VAL_ALLOC/FREE(). */
   8
   9 #include "util.h" /* VOID2(), XSH_ASSERT(), xPMS */
  10
  11 /* --- Configuration ------------------------------------------------------- */
  12
  13 #ifndef PTABLE_USE_DEFAULT
  14 # define PTABLE_USE_DEFAULT 0
  15 #endif
  16
  17 #if PTABLE_USE_DEFAULT
  18 # if defined(PTABLE_VAL_ALLOC) || defined(PTABLE_VAL_FREE)
  19 #  error the default ptable is only available when PTABLE_VAL_ALLOC/FREE are unset
  20 # endif
  21 # undef  PTABLE_NAME
  22 # define PTABLE_NAME ptable_default
  23 # undef  PTABLE_VAL_NEED_CONTEXT
  24 # define PTABLE_VAL_NEED_CONTEXT 0
  25 #else
  26 # ifndef PTABLE_NAME
  27 #  error PTABLE_NAME must be defined
  28 # endif
  29 # ifndef PTABLE_VAL_NEED_CONTEXT
  30 #  define PTABLE_VAL_NEED_CONTEXT 1
  31 # endif
  32 #endif
  33
  34 #ifndef PTABLE_JOIN
  35 # define PTABLE_PASTE(A, B) A ## B
  36 # define PTABLE_JOIN(A, B)  PTABLE_PASTE(A, B)
  37 #endif
  38
  39 #ifndef PTABLE_PREFIX
  40 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
  41 #endif
  42
  43 #ifndef PTABLE_NEED_SPLICE
  44 # define PTABLE_NEED_SPLICE 0
  45 #endif
  46
  47 #ifndef PTABLE_NEED_WALK
  48 # define PTABLE_NEED_WALK 0
  49 #endif
  50
  51 #ifndef PTABLE_NEED_STORE
  52 # define PTABLE_NEED_STORE 1
  53 #endif
  54
  55 #ifndef PTABLE_NEED_VIVIFY
  56 # define PTABLE_NEED_VIVIFY 0
  57 #elif PTABLE_NEED_VIVIFY
  58 # undef  PTABLE_NEED_VIVIFY
  59 # ifndef PTABLE_VAL_ALLOC
  60 #  error need to define PTABLE_VAL_ALLOC() to use ptable_vivify()
  61 # endif
  62 # define PTABLE_NEED_VIVIFY 1
  63 #endif
  64
  65 #ifndef PTABLE_NEED_DELETE
  66 # define PTABLE_NEED_DELETE 1
  67 #endif
  68
  69 #ifndef PTABLE_NEED_CLEAR
  70 # define PTABLE_NEED_CLEAR 1
  71 #endif
  72
  73 #undef PTABLE_NEED_ENT_VIVIFY
  74 #if PTABLE_NEED_SPLICE || PTABLE_NEED_STORE || PTABLE_NEED_VIVIFY
  75 # define PTABLE_NEED_ENT_VIVIFY 1
  76 #else
  77 # define PTABLE_NEED_ENT_VIVIFY 0
  78 #endif
  79
  80 #undef PTABLE_NEED_ENT_DETACH
  81 #if PTABLE_NEED_SPLICE || PTABLE_NEED_DELETE
  82 # define PTABLE_NEED_ENT_DETACH 1
  83 #else
  84 # define PTABLE_NEED_ENT_DETACH 0
  85 #endif
  86
  87 /* ... Context for ptable_*() functions calling PTABLE_VAL_ALLOC/FREE() .... */
  88
  89 #undef pPTBL
  90 #undef pPTBL_
  91 #undef aPTBL
  92 #undef aPTBL_
  93
  94 #if PTABLE_VAL_NEED_CONTEXT
  95 # define pPTBL  pTHX
  96 # define pPTBL_ pTHX_
  97 # define aPTBL  aTHX
  98 # define aPTBL_ aTHX_
  99 #else
 100 # define pPTBL  pPMS
 101 # define pPTBL_ pPMS_
 102 # define aPTBL  aPMS
 103 # define aPTBL_ aPMS_
 104 #endif
 105
 106 /* --- <ptable> struct ----------------------------------------------------- */
 107
 108 #ifndef ptable_ent
 109 typedef struct ptable_ent {
 110  struct ptable_ent *next;
 111  const void *       key;
 112  void *             val;
 113 } ptable_ent;
 114 #define ptable_ent ptable_ent
 115 #endif /* !ptable_ent */
 116
 117 #ifndef ptable
 118 typedef struct ptable {
 119  ptable_ent **ary;
 120  size_t       max;
 121  size_t       items;
 122 } ptable;
 123 #define ptable ptable
 124 #endif /* !ptable */
 125
 126 /* --- Private interface --------------------------------------------------- */
 127
 128 #ifndef PTABLE_HASH
 129 # define PTABLE_HASH(ptr) \
 130      ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
 131 #endif
 132
 133 #ifndef ptable_bucket
 134 # define ptable_bucket(T, K) (PTABLE_HASH(K) & (T)->max)
 135 #endif
 136
 137 #ifndef ptable_ent_find
 138 static ptable_ent *ptable_ent_find(const ptable *t, const void *key) {
 139 #define ptable_ent_find ptable_ent_find
 140  ptable_ent  *ent;
 141  const size_t idx = ptable_bucket(t, key);
 142
 143  ent = t->ary[idx];
 144  for (; ent; ent = ent->next) {
 145   if (ent->key == key)
 146    return ent;
 147  }
 148
 149  return NULL;
 150 }
 151 #endif /* !ptable_ent_find */
 152
 153 #if PTABLE_NEED_ENT_VIVIFY
 154
 155 #ifndef ptable_split
 156 static void ptable_split(pPMS_ ptable *t) {
 157 #define ptable_split(T) ptable_split(aPMS_ (T))
 158  ptable_ent      **ary = t->ary;
 159  const size_t old_size = t->max + 1;
 160  size_t       new_size = old_size * 2;
 161  size_t       i;
 162
 163  ary = VOID2(ptable_ent **,
 164              PerlMemShared_realloc(ary, new_size * sizeof *ary));
 165  Zero(ary + old_size, new_size - old_size, sizeof *ary);
 166  t->max = --new_size;
 167  t->ary = ary;
 168
 169  for (i = 0; i < old_size; i++, ary++) {
 170   ptable_ent **curentp, **entp, *ent;
 171
 172   ent = *ary;
 173   if (!ent)
 174    continue;
 175   entp    = ary;
 176   curentp = ary + old_size;
 177
 178   do {
 179    if ((new_size & PTABLE_HASH(ent->key)) != i) {
 180     *entp     = ent->next;
 181     ent->next = *curentp;
 182     *curentp  = ent;
 183    } else {
 184     entp = &ent->next;
 185    }
 186    ent = *entp;
 187   } while (ent);
 188  }
 189 }
 190 #endif /* !ptable_split */
 191
 192 #ifndef ptable_ent_vivify
 193 static ptable_ent *ptable_ent_vivify(pPMS_ ptable *t, const void *key) {
 194 #define ptable_ent_vivify(T, K) ptable_ent_vivify(aPMS_ (T), (K))
 195  ptable_ent  *ent;
 196  const size_t idx = ptable_bucket(t, key);
 197
 198  ent = t->ary[idx];
 199  for (; ent; ent = ent->next) {
 200   if (ent->key == key)
 201    return ent;
 202  }
 203
 204  ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
 205
 206  ent->key    = key;
 207  ent->val    = NULL;
 208  ent->next   = t->ary[idx];
 209  t->ary[idx] = ent;
 210
 211  t->items++;
 212  if (ent->next && t->items > t->max)
 213   ptable_split(t);
 214
 215  return ent;
 216 }
 217 #endif /* !ptable_ent_vivify */
 218
 219 #endif /* PTABLE_NEED_ENT_VIVIFY */
 220
 221 #if PTABLE_NEED_ENT_DETACH
 222
 223 #ifndef ptable_ent_detach
 224 static ptable_ent *ptable_ent_detach(ptable *t, const void *key) {
 225 #define ptable_ent_detach ptable_ent_detach
 226  ptable_ent  *prev, *ent;
 227  const size_t idx = ptable_bucket(t, key);
 228
 229  prev = NULL;
 230  ent  = t->ary[idx];
 231  for (; ent; prev = ent, ent = ent->next) {
 232   if (ent->key == key) {
 233    if (prev)
 234     prev->next  = ent->next;
 235    else
 236     t->ary[idx] = ent->next;
 237    break;
 238   }
 239  }
 240
 241  return ent;
 242 }
 243 #endif /* !ptable_ent_detach */
 244
 245 #endif /* PTABLE_NEED_ENT_DETACH */
 246
 247 /* --- Public interface ---------------------------------------------------- */
 248
 249 /* ... Common symbols ...................................................... */
 250
 251 #ifndef ptable_new
 252 static ptable *ptable_new(pPMS_ size_t init_buckets) {
 253 #define ptable_new(B) ptable_new(aPMS_ (B))
 254  ptable *t;
 255
 256  if (init_buckets < 4) {
 257   init_buckets = 4;
 258  } else {
 259   init_buckets--;
 260   init_buckets |= init_buckets >> 1;
 261   init_buckets |= init_buckets >> 2;
 262   init_buckets |= init_buckets >> 4;
 263   init_buckets |= init_buckets >> 8;
 264   init_buckets |= init_buckets >> 16;
 265   if (sizeof(init_buckets) > 4)
 266    init_buckets |= init_buckets >> 32;
 267   init_buckets++;
 268  }
 269
 270  XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
 271
 272  t        = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
 273  t->max   = init_buckets - 1;
 274  t->items = 0;
 275  t->ary   = VOID2(ptable_ent **,
 276                               PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
 277  return t;
 278 }
 279 #endif /* !ptable_new */
 280
 281 #ifndef ptable_fetch
 282 static void *ptable_fetch(const ptable *t, const void *key) {
 283 #define ptable_fetch ptable_fetch
 284  const ptable_ent *ent = ptable_ent_find(t, key);
 285
 286  return ent ? ent->val : NULL;
 287 }
 288 #endif /* !ptable_fetch */
 289
 290 #if PTABLE_NEED_SPLICE
 291
 292 #ifndef ptable_splice
 293 static void *ptable_splice(pPMS_ ptable *t, const void *key, void *new_val) {
 294 #define ptable_splice(T, K, V) ptable_splice(aPMS_ (T), (K), (V))
 295  ptable_ent *ent;
 296  void       *old_val = NULL;
 297
 298  if (new_val) {
 299   ent      = ptable_ent_vivify(t, key);
 300   old_val  = ent->val;
 301   ent->val = new_val;
 302  } else {
 303   ent = ptable_ent_detach(t, key);
 304   if (ent) {
 305    old_val = ent->val;
 306    PerlMemShared_free(ent);
 307   }
 308  }
 309
 310  return old_val;
 311 }
 312 #endif /* !ptable_splice */
 313
 314 #endif /* PTABLE_NEED_SPLICE */
 315
 316 #if PTABLE_NEED_WALK
 317
 318 #ifndef ptable_walk
 319 static void ptable_walk(pTHX_ ptable *t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) {
 320 #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD))
 321  if (t && t->items) {
 322   register ptable_ent **array = t->ary;
 323   size_t i = t->max;
 324   do {
 325    ptable_ent *entry;
 326    for (entry = array[i]; entry; entry = entry->next)
 327     if (entry->val)
 328      cb(aTHX_ entry, userdata);
 329   } while (i--);
 330  }
 331 }
 332 #endif /* !ptable_walk */
 333
 334 #endif /* PTABLE_NEED_WALK */
 335
 336 /* ... Specialized symbols ................................................. */
 337
 338 #if PTABLE_NEED_STORE
 339
 340 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_store)
 341 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
 342  ptable_ent *ent = ptable_ent_vivify(t, key);
 343
 344 #ifdef PTABLE_VAL_FREE
 345  PTABLE_VAL_FREE(ent->val);
 346 #endif
 347
 348  ent->val = val;
 349
 350  return;
 351 }
 352 # if PTABLE_USE_DEFAULT
 353 #  define ptable_default_store ptable_default_store
 354 # endif
 355 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_store) */
 356
 357 #endif /* PTABLE_NEED_STORE */
 358
 359 #if PTABLE_NEED_VIVIFY
 360
 361 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify)
 362 static void *PTABLE_PREFIX(_vivify)(pPTBL_ ptable *t, const void *key) {
 363  ptable_ent *ent = ptable_ent_vivify(t, key);
 364
 365  if (!ent->val) {
 366   PTABLE_VAL_ALLOC(ent->val);
 367  }
 368
 369  return ent->val;
 370 }
 371 # if PTABLE_USE_DEFAULT
 372 #  define ptable_default_vivify ptable_default_vivify
 373 # endif
 374 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify) */
 375
 376 #endif /* PTABLE_NEED_VIVIFY */
 377
 378 #if PTABLE_NEED_DELETE
 379
 380 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_delete)
 381 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
 382  ptable_ent *ent = ptable_ent_detach(t, key);
 383
 384 #ifdef PTABLE_VAL_FREE
 385  if (ent) {
 386   PTABLE_VAL_FREE(ent->val);
 387  }
 388 #endif
 389
 390  PerlMemShared_free(ent);
 391 }
 392 # if PTABLE_USE_DEFAULT
 393 #  define ptable_default_delete ptable_default_delete
 394 # endif
 395 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_delete) */
 396
 397 #endif /* PTABLE_NEED_DELETE */
 398
 399 #if PTABLE_NEED_CLEAR
 400
 401 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_clear)
 402 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
 403  if (t && t->items) {
 404   register ptable_ent **array = t->ary;
 405   size_t idx = t->max;
 406
 407   do {
 408    ptable_ent *entry = array[idx];
 409    while (entry) {
 410     ptable_ent *nentry = entry->next;
 411 #ifdef PTABLE_VAL_FREE
 412     PTABLE_VAL_FREE(entry->val);
 413 #endif
 414     PerlMemShared_free(entry);
 415     entry = nentry;
 416    }
 417    array[idx] = NULL;
 418   } while (idx--);
 419
 420   t->items = 0;
 421  }
 422 }
 423 # if PTABLE_USE_DEFAULT
 424 #  define ptable_default_clear ptable_default_clear
 425 # endif
 426 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_clear) */
 427
 428 #endif /* PTABLE_NEED_CLEAR */
 429
 430 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_free)
 431 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
 432  if (!t)
 433   return;
 434  PTABLE_PREFIX(_clear)(aPTBL_ t);
 435  PerlMemShared_free(t->ary);
 436  PerlMemShared_free(t);
 437 }
 438 # if PTABLE_USE_DEFAULT
 439 #  define ptable_default_free ptable_default_free
 440 # endif
 441 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_free) */
 442
 443 /* --- Cleanup ------------------------------------------------------------- */
 444
 445 #undef PTABLE_WAS_DEFAULT
 446 #if PTABLE_USE_DEFAULT
 447 # define PTABLE_WAS_DEFAULT 1
 448 #else
 449 # define PTABLE_WAS_DEFAULT 0
 450 #endif
 451
 452 #undef PTABLE_NAME
 453 #undef PTABLE_VAL_ALLOC
 454 #undef PTABLE_VAL_FREE
 455 #undef PTABLE_VAL_NEED_CONTEXT
 456 #undef PTABLE_USE_DEFAULT
 457
 458 #undef PTABLE_NEED_SPLICE
 459 #undef PTABLE_NEED_WALK
 460 #undef PTABLE_NEED_STORE
 461 #undef PTABLE_NEED_VIVIFY
 462 #undef PTABLE_NEED_DELETE
 463 #undef PTABLE_NEED_CLEAR
 464
 465 #undef PTABLE_NEED_ENT_VIVIFY
 466 #undef PTABLE_NEED_ENT_DETACH