src/su/x-assoc-map.h

   1 /*@ Shared implementation of associative map-alike containers.
   2  *@ Include once, define a_TYPE correspondingly, include again.
   3  *@ XXX "Unroll" more.
   4  *
   5  * Copyright (c) 2001 - 2020 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
   6  * SPDX-License-Identifier: ISC
   7  *
   8  * Permission to use, copy, modify, and/or distribute this software for any
   9  * purpose with or without fee is hereby granted, provided that the above
  10  * copyright notice and this permission notice appear in all copies.
  11  *
  12  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  13  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  14  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  15  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  16  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  17  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  18  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  19  */
  20
  21 #ifndef a_ASSOC_MAP_H
  22 # define a_ASSOC_MAP_H
  23
  24 # undef a_TYPE_CSDICT
  25 # undef a_TYPE
  26 # undef a_TYPE_IS_DICT
  27 # undef a_TYPE_NAME
  28 # undef a_T
  29 # undef a_T_F
  30 # undef a_T_PRINAME
  31 # undef a_T_PUBNAME
  32 # undef a_T_PRISYM
  33 # undef a_T_PUBSYM
  34 # undef a_FUN
  35 # undef a_TK
  36 # undef a_N
  37 # undef a_N_F
  38 # undef a_N_ALLOC
  39 # undef a_N_FREE
  40 # undef a_V
  41 # undef a_V_F
  42 # undef a_V_PRINAME
  43 # undef a_V_PUBNAME
  44 # undef a_V_PRISYM
  45 # undef a_V_PUBSYM
  46 # undef a_LA
  47 # undef a_LA_F
  48
  49 # define a_TYPE_CSDICT 1
  50 #else
  51 # undef a_ASSOC_MAP_H
  52
  53 # if a_TYPE == a_TYPE_CSDICT
  54 #  define a_TYPE a_TYPE_CSDICT
  55 #  define a_TYPE_IS_DICT 1
  56 #  define a_TYPE_NAME "su_cs_dict"
  57 #  define a_T su_cs_dict
  58 #  define a_T_F(X) su_CONCAT(csd_, X)
  59 #  define a_T_PRINAME(X) su_CONCAT(su__CS_DICT_, X)
  60 #  define a_T_PUBNAME(X) su_CONCAT(su_CS_DICT_, X)
  61 #  define a_T_PRISYM(X) su_CONCAT(su__cs_dict_, X)
  62 #  define a_T_PUBSYM(X) su_CONCAT(su_cs_dict_, X)
  63 #  define a_FUN(X) su_CONCAT(a_csdict_, X)
  64 #  define a_TK char
  65 #  define a_N su__cs_dict_node
  66 #  define a_N_F(X) su_CONCAT(csdn_, X)
  67 #  define a_N_ALLOC(SELF,KLEN,FLAGS) \
  68    S(struct a_N*,su_ALLOCATE((VSTRUCT_SIZEOF(struct a_N, a_N_F(key)) +\
  69             (KLEN) +1), 1, ((FLAGS) & su_STATE_ERR_MASK)))
  70 #  define a_N_FREE(SELF,NP) su_FREE(NP)
  71 #  define a_V su_cs_dict_view
  72 #  define a_V_F(X) su_CONCAT(csdv_, X)
  73 #  define a_V_PRINAME(X) su_CONCAT(su__CS_DICT_VIEW_, X)
  74 #  define a_V_PUBNAME(X) su_CONCAT(su_CS_DICT_VIEW_, X)
  75 #  define a_V_PRISYM(X) su_CONCAT(su__cs_dict_view_, X)
  76 #  define a_V_PUBSYM(X) su_CONCAT(su_cs_dict_view_, X)
  77 #  define a_LA a_csdict_lookarg
  78 #  define a_LA_F(X) su_CONCAT(csdla_, X)
  79 # else /* a_TYPE == a_TYPE_CSDICT */
  80 #  error Unknown a_TYPE
  81 # endif
  82
  83 struct a_LA{
  84    struct a_N **la_slot;
  85    struct a_N *la_last; /* Only with AUTO_RESORT */
  86    u32 la_slotidx;
  87    u32 la_klen; /* Only if a_TYPE_IS_DICT */
  88    uz la_khash;
  89 };
  90
  91 /* force: ignore FROZEN state.  Return -1 if we did resize, successfully */
  92 SINLINE s32 a_FUN(check_resize)(struct a_T *self, boole force, u32 xcount);
  93 static s32 a_FUN(resize)(struct a_T *self, u32 xcount);
  94
  95 /* */
  96 static s32 a_FUN(assign)(struct a_T *self, struct a_T const *t, boole flags);
  97
  98 /* */
  99 static s32 a_FUN(node_new)(struct a_T *self, struct a_N **res,
 100       struct a_LA *lap, a_TK const *key, void *value);
 101
 102 /* */
 103 static s32 a_FUN(replace)(struct a_T *self, struct a_N *np, void *value);
 104 static struct a_T *a_FUN(remove)(struct a_T *self, struct a_N *np,
 105       struct a_LA *lap);
 106
 107 SINLINE s32
 108 a_FUN(check_resize)(struct a_T *self, boole force, u32 xcount){
 109    /* Simple approach: shift a 64-bit value, do not care for overflow */
 110    s32 rv;
 111    u64 s;
 112    NYD2_IN;
 113
 114    rv = su_ERR_NONE;
 115
 116    if(force || !(self->a_T_F(flags) & a_T_PUBNAME(FROZEN))){
 117       s = self->a_T_F(size);
 118
 119       if(xcount >= (s << self->a_T_F(tshift)) ||
 120             (xcount < (s >>= 1) &&
 121              (self->a_T_F(flags) & a_T_PUBNAME(AUTO_SHRINK))))
 122          rv = a_FUN(resize)(self, xcount);
 123    }else
 124       ASSERT(xcount == 0 || self->a_T_F(size) > 0);
 125
 126    NYD2_OU;
 127    return rv;
 128 }
 129
 130 static s32
 131 a_FUN(resize)(struct a_T *self, u32 xcount){
 132    s32 rv;
 133    struct a_N **narr, **arr;
 134    boole pow2;
 135    u32 size, nsize;
 136    NYD_IN;
 137
 138    size = self->a_T_F(size);
 139    pow2 = ((self->a_T_F(flags) & a_T_PUBNAME(POW2_SPACED)) != 0);
 140
 141    /* Calculate new size */
 142    /* C99 */{
 143       u32 onsize;
 144       boole grow;
 145
 146       /* >= to catch initial 0 size */
 147       grow = ((xcount >> self->a_T_F(tshift)) >= size);
 148       nsize = size;
 149
 150       for(;;){
 151          onsize = nsize;
 152
 153          if(pow2){
 154             ASSERT(nsize == 0 || nsize == 1 || IS_POW2(nsize));
 155             if(grow){
 156                if(nsize == 0)
 157                   nsize = 1u << 1;
 158                else if(UCMP(32, nsize, <, S32_MIN))
 159                   nsize <<= 1;
 160             }else if(nsize > (1u << 1))
 161                nsize >>= 1;
 162          }else
 163             nsize = grow ? su_prime_lookup_next(nsize)
 164                   : su_prime_lookup_former(nsize);
 165
 166          /* Refuse to excess storage bounds, but do not fail for this: simply
 167           * keep on going and place more nodes in the slots.
 168           * Because of the numbers we are talking about this is a theoretical
 169           * issue (at the time of this writing). */
 170          if(nsize == onsize)
 171             break;
 172          if(grow){
 173             /* (Again, shift 64-bit to avoid overflow) */
 174             if((S(u64,nsize) << self->a_T_F(tshift)) >= xcount)
 175                break;
 176          }else if((nsize >> 1) <= xcount)
 177             break;
 178       }
 179
 180       if(size == nsize){
 181          rv = su_ERR_NONE;
 182          goto jleave;
 183       }
 184    }
 185
 186    /* Try to allocate new array, give up on failure */
 187    narr = su_TCALLOCF(struct a_N*, nsize,
 188          (self->a_T_F(flags) & su_STATE_ERR_MASK));
 189    if(UNLIKELY(narr == NIL)){
 190       rv = su_err_no();
 191       goto jleave;
 192    }
 193
 194    /* We will succeed: move pointers over */
 195    self->a_T_F(size) = nsize;
 196
 197    arr = self->a_T_F(array);
 198    self->a_T_F(array) = narr;
 199
 200    if((xcount = self->a_T_F(count)) > 0){
 201       struct a_N *np, **npos, *xnp;
 202
 203       do for(np = arr[--size]; np != NIL; --xcount){
 204          uz i;
 205
 206          i = np->a_N_F(khash);
 207          i= pow2 ? i & (nsize - 1) : i % nsize;
 208          npos = &narr[i];
 209          xnp = np;
 210          np = np->a_N_F(next);
 211          xnp->a_N_F(next) = *npos;
 212          *npos = xnp;
 213       }while(xcount > 0 && size > 0);
 214    }
 215
 216    if(arr != NIL)
 217       su_FREE(arr);
 218
 219    rv = -1;
 220 jleave:
 221    NYD_OU;
 222    return rv;
 223 }
 224
 225 static s32
 226 a_FUN(assign)(struct a_T *self, struct a_T const *t, boole flags){
 227    s32 rv;
 228    NYD_IN;
 229    ASSERT(self);
 230
 231    /* Clear old elements first if there are any, and if necessary */
 232    rv = su_ERR_NONE;
 233 jerr:
 234    if(self->a_T_F(count) > 0){
 235       if(self->a_T_F(flags) & a_T_PUBNAME(OWNS))
 236          self = a_T_PUBSYM(clear_elems)(self);
 237       self->a_T_F(count) = 0;
 238    }
 239
 240    ASSERT_NYD_EXEC(t != NIL, rv = su_ERR_FAULT);
 241
 242    if(flags){
 243       self->a_T_F(flags) = t->a_T_F(flags);
 244       self->a_T_F(tbox) = t->a_T_F(tbox);
 245    }
 246
 247    if(rv != 0)
 248       goto jleave;
 249
 250    if(t->a_T_F(count) == 0)
 251       goto jleave;
 252
 253    /* We actually ignore a resize failure if we do have some backing store to
 254     * put elements into! */
 255    rv = a_FUN(check_resize)(self, TRU1, t->a_T_F(count));
 256    if(rv > su_ERR_NONE && self->a_T_F(array) == NIL)
 257       goto jleave;
 258
 259    /* C99 */{
 260       struct a_LA la;
 261       boole pow2;
 262       u32 size, tsize, tcnt;
 263       struct a_N **arr, **tarr, *np, *tnp;
 264
 265       arr = self->a_T_F(array);
 266       tarr = t->a_T_F(array);
 267       size = self->a_T_F(size);
 268       tsize = t->a_T_F(size);
 269       tcnt = t->a_T_F(count);
 270       pow2 = ((self->a_T_F(flags) & a_T_PUBNAME(POW2_SPACED)) != 0);
 271
 272       while(tcnt != 0){
 273          for(tnp = tarr[--tsize]; tnp != NIL; --tcnt, tnp = tnp->a_N_F(next)){
 274             uz i;
 275
 276             la.la_khash = i = tnp->a_N_F(khash);
 277             la.la_slotidx = S(u32,i = pow2 ? i & (size - 1) : i % size);
 278             la.la_slot = &arr[i];
 279 # if a_TYPE_IS_DICT
 280             la.la_klen = tnp->a_N_F(klen);
 281 # endif
 282             rv = a_FUN(node_new)(self, &np, &la, tnp->a_N_F(key),
 283                   tnp->a_N_F(data));
 284             if(UNLIKELY(rv != 0))
 285                goto jerr;
 286          }
 287       }
 288    }
 289
 290    ASSERT(rv == su_ERR_NONE);
 291 jleave:
 292    NYD_OU;
 293    return rv;
 294 }
 295
 296 static s32
 297 a_FUN(node_new)(struct a_T *self, struct a_N **res, struct a_LA *lap,
 298       a_TK const *key, void *value){
 299    s32 rv;
 300    u16 flags;
 301    void *xvalue;
 302    struct a_N *np;
 303    NYD_IN;
 304
 305    np = NIL;
 306    xvalue = NIL;
 307    flags = self->a_T_F(flags);
 308
 309    if(flags & a_T_PUBNAME(OWNS)){
 310       if(value != NIL){
 311          xvalue = value = (*self->a_T_F(tbox)->tb_clone)(value,
 312                (flags & su_STATE_ERR_MASK));
 313          if(UNLIKELY(xvalue == NIL) && !(flags & a_T_PUBNAME(NILISVALO))){
 314             rv = su_err_no();
 315             goto jleave;
 316          }
 317       }else
 318          ASSERT(flags & a_T_PUBNAME(NILISVALO));
 319    }
 320
 321    /* ..so create a new node */
 322    np = a_N_ALLOC(self, lap->la_klen, flags);
 323    if(UNLIKELY(np == NIL)){
 324       if(xvalue != NIL)
 325          (*self->a_T_F(tbox)->tb_delete)(xvalue);
 326       rv = su_ERR_NOMEM; /* (Cannot be overflow error) */
 327       goto jleave;
 328    }
 329    ++self->a_T_F(count);
 330
 331    np->a_N_F(next) = *lap->la_slot;
 332    *lap->la_slot = np;
 333    np->a_N_F(data) = value;
 334    np->a_N_F(khash) = lap->la_khash;
 335    np->a_N_F(klen) = lap->la_klen;
 336
 337 # if a_TYPE == a_TYPE_CSDICT
 338    su_mem_copy(np->a_N_F(key), key, lap->la_klen +1);
 339    if(flags & a_T_PUBNAME(CASE)){
 340       a_TK *nckey;
 341
 342       for(nckey = np->a_N_F(key); *nckey != '\0'; ++nckey)
 343          *nckey = su_cs_to_lower(*nckey);
 344    }
 345 # else
 346 #  error
 347 # endif
 348
 349    rv = su_ERR_NONE;
 350 jleave:
 351    *res = np;
 352    NYD_OU;
 353    return rv;
 354 }
 355
 356 static s32
 357 a_FUN(replace)(struct a_T *self, struct a_N *np, void *value){
 358    u16 flags;
 359    s32 rv;
 360    NYD_IN;
 361
 362    rv = su_ERR_NONE;
 363    flags = self->a_T_F(flags);
 364
 365    if(flags & a_T_PUBNAME(OWNS)){
 366       void *ndat;
 367
 368       ndat = np->a_N_F(data);
 369
 370       if(LIKELY(value != NIL)){
 371          if((flags & a_T_PUBNAME(NILISVALO)) && ndat != NIL){
 372             value = (*self->a_T_F(tbox)->tb_assign)(ndat,
 373                   value, (flags & su_STATE_ERR_MASK));
 374             if(LIKELY(value != NIL))
 375                ndat = NIL;
 376             else
 377                rv = su_err_no();
 378          }else{
 379             value = (*self->a_T_F(tbox)->tb_clone)(value,
 380                   (flags & su_STATE_ERR_MASK));
 381             if(UNLIKELY(value == NIL)){
 382                rv = su_err_no();
 383                ndat = NIL;
 384             }
 385          }
 386       }else
 387          ASSERT(flags & a_T_PUBNAME(NILISVALO));
 388
 389       if(ndat != NIL)
 390          (*self->a_T_F(tbox)->tb_delete)(ndat);
 391    }
 392
 393    np->a_N_F(data) = value;
 394
 395    NYD_OU;
 396    return rv;
 397 }
 398
 399 static struct a_T *
 400 a_FUN(remove)(struct a_T *self, struct a_N *np, struct a_LA *lap){
 401    NYD_IN;
 402
 403    --self->a_T_F(count);
 404
 405    if(np->a_N_F(data) != NIL && (self->a_T_F(flags) & a_T_PUBNAME(OWNS)))
 406       (*self->a_T_F(tbox)->tb_delete)(np->a_N_F(data));
 407    if(lap->la_last != NIL)
 408       lap->la_last->a_N_F(next) = np->a_N_F(next);
 409    else
 410       *lap->la_slot = np->a_N_F(next);
 411    a_N_FREE(self, np);
 412
 413    NYD_OU;
 414    return self;
 415 }
 416
 417 struct a_N *
 418 a_T_PRISYM(lookup)(struct a_T const *self, a_TK const *key,
 419       void *lookarg_or_nil){
 420 # if !a_TYPE_IS_DICT
 421    boole const key_is = (key != NIL);
 422 # else
 423    u32 klen;
 424 # endif
 425    u32 cnt, slotidx;
 426    uz khash;
 427    struct a_N *rv, **arr, *last;
 428    NYD_IN;
 429    ASSERT(self);
 430
 431    rv = NIL;
 432
 433 # if a_TYPE == a_TYPE_CSDICT
 434    khash = su_cs_len(key);
 435    klen = S(u32,khash);
 436    if(khash != klen)
 437       goto jleave;
 438    khash = ((self->a_T_F(flags) & a_T_PUBNAME(CASE)) ? su_cs_hash_case_cbuf
 439          : su_cs_hash_cbuf)(key, klen);
 440 # else
 441 #  error
 442 # endif
 443
 444    if(LIKELY((slotidx = self->a_T_F(size)) > 0))
 445       slotidx = (self->a_T_F(flags) & a_T_PUBNAME(POW2_SPACED))
 446             ? khash & (slotidx - 1) : khash % slotidx;
 447    arr = self->a_T_F(array) + slotidx;
 448
 449    if(lookarg_or_nil != NIL){
 450       struct a_LA *lap;
 451
 452       lap = S(struct a_LA*,lookarg_or_nil);
 453       lap->la_slot = arr;
 454       lap->la_last = NIL;
 455       lap->la_slotidx = slotidx;
 456 # if a_TYPE_IS_DICT
 457       lap->la_klen = klen;
 458 # endif
 459       lap->la_khash = khash;
 460    }
 461
 462    if(UNLIKELY((cnt = self->a_T_F(count)) == 0))
 463       goto jleave;
 464
 465    for(last = rv, rv = *arr; rv != NIL; last = rv, rv = rv->a_N_F(next)){
 466       if(khash != rv->a_N_F(khash))
 467          continue;
 468
 469 # if a_TYPE == a_TYPE_CSDICT
 470       if(klen != rv->a_N_F(klen))
 471          continue;
 472       if(((self->a_T_F(flags) & a_T_PUBNAME(CASE))
 473             ? R(sz(*)(void const*,void const*,uz),&su_cs_cmp_case_n)
 474             : &su_mem_cmp)(key, rv->a_N_F(key), klen))
 475          continue;
 476 # else
 477 #  error
 478 # endif
 479
 480       /* Match! */
 481       if(last != NIL){
 482          if(self->a_T_F(flags) & a_T_PUBNAME(HEAD_RESORT)){
 483             last->a_N_F(next) = rv->a_N_F(next);
 484             rv->a_N_F(next) = *arr;
 485             *arr = rv;
 486          }else if(lookarg_or_nil != NIL)
 487             S(struct a_LA*,lookarg_or_nil)->la_last = last;
 488       }
 489       break;
 490    }
 491
 492 jleave:
 493    NYD_OU;
 494    return rv;
 495 }
 496
 497 s32
 498 a_T_PRISYM(insrep)(struct a_T *self, a_TK const *key, void *value,
 499       up replace_and_view_or_nil){
 500    struct a_LA la;
 501    struct a_N *np;
 502    s32 rv;
 503    struct a_V *viewp;
 504    u16 flags;
 505    NYD_IN;
 506    ASSERT(self);
 507
 508    flags = self->a_T_F(flags);
 509    viewp = R(struct a_V*,replace_and_view_or_nil & ~TRU1);
 510
 511    /* Ensure this basic precondition */
 512    if(value == NIL &&
 513          (flags & a_T_PUBNAME(OWNS)) && !(flags & a_T_PUBNAME(NILISVALO))){
 514       rv = su_ERR_INVAL;
 515       goto jleave;
 516    }
 517
 518    /* But on error we will put new node in case we are empty, so create some
 519     * array space right away */
 520    if(UNLIKELY(self->a_T_F(size) == 0) &&
 521          (rv = a_FUN(resize)(self, 1)) > su_ERR_NONE)
 522       goto jleave;
 523
 524    /* Try to find a yet existing key */
 525    np = a_T_PRISYM(lookup)(self, key, &la);
 526
 527 # if a_TYPE == a_TYPE_CSDICT
 528    /* (Ensure documented maximum key length first) */
 529    if(UNLIKELY(UCMP(z, la.la_klen, >, S32_MAX))){
 530       rv = su_state_err(su_STATE_ERR_OVERFLOW, (flags & su_STATE_ERR_MASK),
 531             _(a_TYPE_NAME ": insertion: key length excess"));
 532       goto jleave;
 533    }
 534 # endif
 535
 536    /* Is it an insertion of something new? */
 537    if(LIKELY(np == NIL)){
 538       if(UNLIKELY((rv = a_FUN(node_new)(self, &np, &la, key, value)
 539             ) != su_ERR_NONE))
 540          goto jleave;
 541       /* Never grow array storage if no other node is in this slot.
 542        * And do not fail if a resize fails at this point, it would only be
 543        * expensive and of no value, especially as it seems the user is
 544        * ignoring ENOMEM++ */
 545       if(UNLIKELY(np->a_N_F(next) != NIL)){
 546          /* If we did resize and we have to know the node location, it seems
 547           * easiest and most efficient to simply perform another lookup */
 548          if(a_FUN(check_resize)(self, FAL0, self->a_T_F(count)
 549                ) < su_ERR_NONE && viewp != NIL)
 550             np = a_T_PRISYM(lookup)(self, key, &la);
 551       }
 552    }else{
 553       if(LIKELY(replace_and_view_or_nil & TRU1) &&
 554             ((rv = a_FUN(replace)(self, np, value)) != su_ERR_NONE))
 555          goto jleave;
 556       rv = -1;
 557    }
 558
 559 jleave:
 560    if(UNLIKELY(viewp != NIL)){
 561       if(LIKELY(rv <= su_ERR_NONE)){
 562          viewp->a_V_F(node) = *la.la_slot;
 563          viewp->a_V_F(index) = la.la_slotidx;
 564       }else
 565          viewp->a_V_F(node) = NIL;
 566    }
 567
 568    NYD_OU;
 569    return rv;
 570 }
 571
 572 #if DVLOR(1, 0)
 573 void
 574 a_T_PRISYM(stats)(struct a_T const *self){
 575    ul size, empties, multies, maxper, i, j;
 576    struct a_N **arr, *np;
 577    NYD_IN;
 578    ASSERT(self);
 579
 580    su_log_lock();
 581    su_log_write(su_LOG_INFO,
 582       "----------\n>>> " a_TYPE_NAME "(%p): statistics\n",
 583       self);
 584
 585    arr = self->a_T_F(array);
 586    size = self->a_T_F(size);
 587    empties = multies = maxper = 0;
 588
 589    /* First pass: overall stats */
 590    for(i = 0; i < size; ++i){
 591       j = 0;
 592       for(np = arr[i]; np != NIL; np = np->a_N_F(next))
 593          ++j;
 594       if(j == 0)
 595          ++empties;
 596       else{
 597          if(j > 1)
 598             ++multies;
 599          maxper = MAX(maxper, j);
 600       }
 601    }
 602    j = (multies != 0) ? multies : size - empties;
 603    if(j != 0)
 604       j = self->a_T_F(count) / j;
 605
 606    su_log_write(su_LOG_INFO,
 607       "* Overview\n"
 608       "  - POW2_SPACED=%d "
 609 # if a_TYPE != a_TYPE_CSDICT
 610          "OWNS_KEYS=%d "
 611 # endif
 612 # if a_TYPE == a_TYPE_CSDICT
 613          "CASE=%d "
 614 # endif
 615          "OWNS=%d "
 616          "\n"
 617       "  - HEAD_RESORT=%d AUTO_SHRINK=%d FROZEN=%d ERR_PASS=%d NILISVALO=%d\n"
 618       "  - Array size : %lu\n"
 619       "  - Elements   : %lu\n"
 620       "  - Tresh-Shift: %u\n"
 621       "* Distribution\n"
 622       "  - Slots: empty: %lu, multiple: %lu, maximum: %lu, avg/multi: ~%lu\n"
 623       "* Distribution, visual\n"
 624       ,
 625       ((self->a_T_F(flags) & a_T_PUBNAME(POW2_SPACED)) != 0),
 626 # if a_TYPE != a_TYPE_CSDICT
 627          ((self->a_T_F(flags) & a_T_PUBNAME(OWNS_KEYS)) != 0),
 628 # endif
 629 # if a_TYPE == a_TYPE_CSDICT
 630          ((self->a_T_F(flags) & a_T_PUBNAME(CASE)) != 0),
 631 # endif
 632          ((self->a_T_F(flags) & a_T_PUBNAME(OWNS)) != 0),
 633       ((self->a_T_F(flags) & a_T_PUBNAME(HEAD_RESORT)) != 0),
 634          ((self->a_T_F(flags) & a_T_PUBNAME(AUTO_SHRINK)) != 0),
 635          ((self->a_T_F(flags) & a_T_PUBNAME(FROZEN)) != 0),
 636          ((self->a_T_F(flags) & a_T_PUBNAME(ERR_PASS)) != 0),
 637          ((self->a_T_F(flags) & a_T_PUBNAME(NILISVALO)) != 0),
 638       (ul)self->a_T_F(size),
 639       (ul)self->a_T_F(count),
 640       (ui)self->a_T_F(tshift),
 641       (ul)empties, (ul)multies, (ul)maxper, (ul)j
 642    );
 643
 644    /* Second pass: visual distribution */
 645    for(i = 0; i < size; ++i){
 646       char buf[50], *cp;
 647
 648       cp = buf;
 649       for(j = 0, np = arr[i]; np != NIL; np = np->a_N_F(next)){
 650          if(++j >= sizeof(buf) - 1 -1){
 651             *cp++ = '@';
 652             break;
 653          }
 654          *cp++ = '*';
 655       }
 656       *cp = '\0';
 657
 658       su_log_write(su_LOG_INFO, "%5lu |%s\n", (ul)i, buf);
 659    }
 660
 661    su_log_write(su_LOG_INFO,
 662       "<<<" a_TYPE_NAME "(%p): statistics\n----------\n",
 663       self);
 664    su_log_unlock();
 665    NYD_OU;
 666 }
 667 #endif /* DVLOR(1, 0) */
 668
 669 struct a_T *
 670 a_T_PUBSYM(create)(struct a_T *self, u16 flags,
 671       struct su_toolbox const *tbox_or_nil){
 672    NYD_IN;
 673    ASSERT(self);
 674
 675    su_mem_set(self, 0, sizeof *self);
 676
 677    ASSERT_NYD(!(flags & a_T_PUBNAME(OWNS)) ||
 678       (tbox_or_nil != NIL && tbox_or_nil->tb_clone != NIL &&
 679        tbox_or_nil->tb_delete != NIL && tbox_or_nil->tb_assign != NIL));
 680
 681    self->a_T_F(flags) = (flags &= a_T_PRINAME(CREATE_MASK));
 682    self->a_T_F(tshift) = 2;
 683    self->a_T_F(tbox) = tbox_or_nil;
 684    NYD_OU;
 685    return self;
 686 }
 687
 688 SHADOW struct a_T *
 689 a_T_PUBSYM(create_copy)(struct a_T *self, struct a_T const *t){
 690    NYD_IN;
 691    ASSERT(self);
 692
 693    su_mem_set(self, 0, sizeof *self);
 694
 695    ASSERT_NYD(t != NIL);
 696    (void)a_FUN(assign)(self, t, TRU1);
 697
 698    NYD_OU;
 699    return self;
 700 }
 701
 702 void
 703 a_T_PUBSYM(gut)(struct a_T *self){ /* XXX inline */
 704    NYD_IN;
 705    ASSERT(self);
 706
 707    if(self->a_T_F(array) != NIL)
 708       self = a_T_PUBSYM(clear)(self);
 709    NYD_OU;
 710 }
 711
 712 s32
 713 a_T_PUBSYM(assign)(struct a_T *self, struct a_T const *t){ /* XXX inline */
 714    s32 rv;
 715    NYD_IN;
 716    ASSERT(self);
 717
 718    rv = a_FUN(assign)(self, t, TRU1);
 719    NYD_OU;
 720    return rv;
 721 }
 722
 723 s32
 724 a_T_PUBSYM(assign_elems)(struct a_T *self, struct a_T const *t){/* XXX inline*/
 725    s32 rv;
 726    NYD_IN;
 727    ASSERT(self);
 728
 729    rv = a_FUN(assign)(self, t, FAL0);
 730    NYD_OU;
 731    return rv;
 732 }
 733
 734 struct a_T *
 735 a_T_PUBSYM(clear)(struct a_T *self){
 736    NYD_IN;
 737    ASSERT(self);
 738
 739    if(self->a_T_F(array) != NIL){
 740       if(self->a_T_F(count) > 0)
 741          self = a_T_PUBSYM(clear_elems)(self);
 742
 743       su_FREE(self->a_T_F(array));
 744       self->a_T_F(array) = NIL;
 745       self->a_T_F(size) = 0;
 746    }
 747
 748    NYD_OU;
 749    return self;
 750 }
 751
 752 struct a_T *
 753 a_T_PUBSYM(clear_elems)(struct a_T *self){
 754    void *vp;
 755    struct a_N **arr, *np, *tmp;
 756    su_delete_fun delfun;
 757    u32 cnt, size;
 758    NYD_IN;
 759    ASSERT(self);
 760
 761    cnt = self->a_T_F(count);
 762    self->a_T_F(count) = 0;
 763    size = self->a_T_F(size);
 764    delfun = (self->a_T_F(flags) & a_T_PUBNAME(OWNS))
 765          ? self->a_T_F(tbox)->tb_delete : S(su_delete_fun,NIL);
 766    arr = self->a_T_F(array);
 767
 768    while(cnt > 0){
 769       ASSERT(size != 0);
 770       if((np = arr[--size]) != NIL){
 771          arr[size] = NIL;
 772
 773          do{
 774             tmp = np;
 775             np = np->a_N_F(next);
 776             --cnt;
 777
 778             if(delfun != NIL && (vp = tmp->a_N_F(data)) != NIL)
 779                (*delfun)(vp);
 780             a_N_FREE(self, tmp);
 781          }while(np != NIL);
 782       }
 783    }
 784
 785    NYD_OU;
 786    return self;
 787 }
 788
 789 struct a_T *
 790 a_T_PUBSYM(swap)(struct a_T *self, struct a_T *t){
 791    struct a_T tmp;
 792    NYD_IN;
 793    ASSERT(self);
 794    ASSERT(t != NIL);
 795
 796    tmp = *self;
 797    *self = *t;
 798    *t = tmp;
 799
 800    NYD_OU;
 801    return self;
 802 }
 803
 804 struct a_T *
 805 a_T_PUBSYM(balance)(struct a_T *self){
 806    NYD_IN;
 807    ASSERT(self);
 808
 809    self->a_T_F(flags) &= ~a_T_PUBNAME(FROZEN);
 810    (void)a_FUN(check_resize)(self, TRU1, self->a_T_F(count));
 811
 812    NYD_OU;
 813    return self;
 814 }
 815
 816 boole
 817 a_T_PUBSYM(remove)(struct a_T *self, a_TK const *key){
 818    struct a_LA la;
 819    struct a_N *np;
 820    NYD_IN;
 821    ASSERT(self);
 822    ASSERT_NYD_EXEC(key != NIL, np = NIL);
 823
 824    np = a_T_PRISYM(lookup)(self, key, &la);
 825    if(LIKELY(np != NIL))
 826       self = a_FUN(remove)(self, np, &la);
 827
 828    NYD_OU;
 829    return (np != NIL);
 830 }
 831
 832 struct a_V *
 833 a_V_PRISYM(move)(struct a_V *self, u8 type){
 834    u32 size, idx;
 835    struct a_N **arr, *np;
 836    struct a_T *parent;
 837    NYD_IN;
 838    ASSERT(self);
 839
 840    parent = self->a_V_F(parent);
 841    arr = parent->a_T_F(array);
 842    size = parent->a_T_F(size);
 843
 844    if(type == a_V_PRINAME(MOVE_BEGIN)){
 845       for(np = NIL, idx = 0; idx < size; ++idx)
 846          if((np = arr[idx]) != NIL)
 847             break;
 848       goto jset;
 849    }else{
 850       idx = self->a_V_F(index);
 851       if(UNLIKELY((np = self->a_V_F(node)->a_N_F(next)) == NIL)){
 852          while(++idx < size)
 853             if((np = arr[idx]) != NIL)
 854                break;
 855       }
 856
 857       if(LIKELY(type != a_V_PRINAME(MOVE_HAS_NEXT))){
 858 jset:
 859          if((self->a_V_F(node) = np) != NIL){
 860             self->a_V_F(index) = idx;
 861             self->a_V_F(next_node) = NIL;
 862          }
 863       }else{
 864          self->a_V_F(next_index) = idx;
 865          self->a_V_F(next_node) = np;
 866       }
 867    }
 868
 869    NYD_OU;
 870    return self;
 871 }
 872
 873 s32
 874 a_V_PUBSYM(set_data)(struct a_V *self, void *value){
 875    s32 rv;
 876    struct a_T *parent;
 877    NYD_IN;
 878    ASSERT(self);
 879    ASSERT_NYD_EXEC(a_V_PUBSYM(is_valid)(self), rv = su_ERR_INVAL);
 880
 881    parent = self->a_V_F(parent);
 882
 883    if(value == NIL){
 884       u16 flags;
 885
 886       flags = parent->a_T_F(flags);
 887
 888       if((flags & a_T_PUBNAME(OWNS)) && !(flags & a_T_PUBNAME(NILISVALO))){
 889          rv = su_ERR_INVAL;
 890          goto jleave;
 891       }
 892    }
 893
 894    rv = a_FUN(replace)(parent, self->a_V_F(node), value);
 895 jleave:
 896    NYD_OU;
 897    return rv;
 898 }
 899
 900 boole
 901 a_V_PUBSYM(find)(struct a_V *self, a_TK const *key){
 902    struct a_LA la;
 903    struct a_N *np;
 904    NYD_IN;
 905    ASSERT(self);
 906
 907    self->a_V_F(node) =
 908    np = a_T_PRISYM(lookup)(self->a_V_F(parent), key, &la);
 909    if(np != NIL){
 910       self->a_V_F(index) = la.la_slotidx;
 911       self->a_V_F(next_node) = NIL;
 912    }
 913
 914    NYD_OU;
 915    return (np != NIL);
 916 }
 917
 918 struct a_V *
 919 a_V_PUBSYM(remove)(struct a_V *self){
 920    struct a_LA la;
 921    struct a_N *np, *mynp;
 922    u32 idx;
 923    struct a_T *parent;
 924    NYD_IN;
 925    ASSERT(self);
 926    ASSERT_NYD(a_V_PUBSYM(is_valid)(self));
 927
 928    parent = self->a_V_F(parent);
 929
 930    /* Setup the look arg for our position */
 931    np = *(la.la_slot = &parent->a_T_F(array)[idx = self->a_V_F(index)]);
 932    mynp = self->a_V_F(node);
 933    if(np == mynp)
 934       la.la_last = NIL;
 935    else{
 936       while(np->a_N_F(next) != mynp)
 937          np = np->a_N_F(next);
 938       la.la_last = np;
 939    }
 940
 941    /* Remove our position */
 942    np = mynp;
 943    mynp = mynp->a_N_F(next);
 944    parent = a_FUN(remove)(parent, np, &la);
 945
 946    /* Move to the next valid position, if any */
 947    if(mynp != NIL)
 948       self->a_V_F(node) = mynp;
 949    else{
 950       while(++idx < parent->a_T_F(size))
 951          if((mynp = parent->a_T_F(array)[idx]) != NIL)
 952             break;
 953       self->a_V_F(node) = mynp;
 954       self->a_V_F(index) = idx;
 955    }
 956    self->a_V_F(next_node) = NIL;
 957
 958    NYD_OU;
 959    return self;
 960 }
 961
 962 # undef a_TYPE_CSDICT
 963 # undef a_TYPE
 964 # undef a_TYPE_IS_DICT
 965 # undef a_TYPE_NAME
 966 # undef a_T
 967 # undef a_T_F
 968 # undef a_T_PRINAME
 969 # undef a_T_PUBNAME
 970 # undef a_T_PUBSYM
 971 # undef a_T_PRISYM
 972 # undef a_FUN
 973 # undef a_TK
 974 # undef a_N
 975 # undef a_N_F
 976 # undef a_N_ALLOC
 977 # undef a_N_FREE
 978 # undef a_V
 979 # undef a_V_F
 980 # undef a_V_PRINAME
 981 # undef a_V_PUBNAME
 982 # undef a_V_PRISYM
 983 # undef a_V_PUBSYM
 984 # undef a_LA
 985 # undef a_LA_F
 986 #endif /* a_ASSOC_MAP_H */
 987
 988 /* s-it-mode */