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