Skip to content

Instantly share code, notes, and snippets.

@jlouis

jlouis/erl_map.c.gcov

Created April 5, 2015 20:23
Show Gist options
  • Save jlouis/7ed6e3c83077dd842519 to your computer and use it in GitHub Desktop.
Save jlouis/7ed6e3c83077dd842519 to your computer and use it in GitHub Desktop.
Download ZIP
Coverage of erl_map.c with 1000 tests run.
Raw
erl_map.c.gcov
-: 0:Source:beam/erl_map.c
-: 0:Graph:obj/x86_64-unknown-linux-gnu/gcov/smp/erl_map.gcno
-: 0:Data:obj/x86_64-unknown-linux-gnu/gcov/smp/erl_map.gcda
-: 0:Runs:4
-: 0:Programs:1
-: 1:/*
-: 2: * %CopyrightBegin%
-: 3: *
-: 4: * Copyright Ericsson AB 2014. All Rights Reserved.
-: 5: *
-: 6: * The contents of this file are subject to the Erlang Public License,
-: 7: * Version 1.1, (the "License"); you may not use this file except in
-: 8: * compliance with the License. You should have received a copy of the
-: 9: * Erlang Public License along with this software. If not, it can be
-: 10: * retrieved online at http://www.erlang.org/.
-: 11: *
-: 12: * Software distributed under the License is distributed on an "AS IS"
-: 13: * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
-: 14: * the License for the specific language governing rights and limitations
-: 15: * under the License.
-: 16: *
-: 17: * %CopyrightEnd%
-: 18: *
-: 19: * hashmaps are an adaption of Rich Hickeys Persistent HashMaps
-: 20: * which were an adaption of Phil Bagwells - Hash Array Mapped Tries
-: 21: *
-: 22: * Author: Björn-Egil Dahlberg
-: 23: */
-: 24:
-: 25:#ifdef HAVE_CONFIG_H
-: 26:# include "config.h"
-: 27:#endif
-: 28:
-: 29:#include "sys.h"
-: 30:#include "erl_vm.h"
-: 31:#include "global.h"
-: 32:#include "erl_process.h"
-: 33:#include "error.h"
-: 34:#include "bif.h"
-: 35:
-: 36:#include "erl_map.h"
-: 37:
-: 38:/* BIFs
-: 39: *
-: 40: * DONE:
-: 41: * - erlang:is_map/1
-: 42: * - erlang:map_size/1
-: 43: *
-: 44: * - maps:find/2
-: 45: * - maps:from_list/1
-: 46: * - maps:get/2
-: 47: * - maps:is_key/2
-: 48: * - maps:keys/1
-: 49: * - maps:merge/2
-: 50: * - maps:new/0
-: 51: * - maps:put/3
-: 52: * - maps:remove/2
-: 53: * - maps:to_list/1
-: 54: * - maps:update/3
-: 55: * - maps:values/1
-: 56: *
-: 57: * TODO:
-: 58: * - maps:foldl/3
-: 59: * - maps:foldr/3
-: 60: * - maps:map/3
-: 61: * - maps:size/1
-: 62: * - maps:without/2
-: 63: *
-: 64: * DEBUG: for sharing calculation
-: 65: * - erts_internal:map_to_tuple_keys/1
-: 66: */
-: 67:
-: 68:#ifndef DECL_AM
-: 69:#define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1)
-: 70:#endif
-: 71:
-: 72:/* for hashmap_from_list/1 */
-: 73:typedef struct {
-: 74: Uint32 hx;
-: 75: Uint32 skip;
-: 76: Uint i;
-: 77: Eterm val;
-: 78:} hxnode_t;
-: 79:
-: 80:
-: 81:static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
-: 82:static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args);
-: 83:static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
-: 84:static Eterm hashmap_to_list(Process *p, Eterm map);
-: 85:static Eterm hashmap_keys(Process *p, Eterm map);
-: 86:static Eterm hashmap_values(Process *p, Eterm map);
-: 87:static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
-: 88:static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size);
-: 89:static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size);
-: 90:static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys);
-: 91:static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
-: 92:static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, int is_root);
-: 93:static Eterm hashmap_info(Process *p, Eterm node);
-: 94:static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
-: 95:static int hxnodecmp(hxnode_t* a, hxnode_t* b);
-: 96:static int hxnodecmpkey(hxnode_t* a, hxnode_t* b);
-: 97:
-: 98:/* erlang:map_size/1
-: 99: * the corresponding instruction is implemented in:
-: 100: * beam/erl_bif_guard.c
-: 101: */
-: 102:
#####: 103:BIF_RETTYPE map_size_1(BIF_ALIST_1) {
#####: 104: if (is_flatmap(BIF_ARG_1)) {
-: 105: Eterm *hp;
#####: 106: Uint hsz = 0;
#####: 107: flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
#####: 108: Uint n = flatmap_get_size(mp);
-: 109:
#####: 110: erts_bld_uint(NULL, &hsz, n);
#####: 111: hp = HAlloc(BIF_P, hsz);
#####: 112: BIF_RET(erts_bld_uint(&hp, NULL, n));
#####: 113: } else if (is_hashmap(BIF_ARG_1)) {
-: 114: Eterm *head, *hp, res;
#####: 115: Uint size, hsz=0;
-: 116:
#####: 117: head = hashmap_val(BIF_ARG_1);
#####: 118: size = head[1];
#####: 119: (void) erts_bld_uint(NULL, &hsz, size);
#####: 120: hp = HAlloc(BIF_P, hsz);
#####: 121: res = erts_bld_uint(&hp, NULL, size);
#####: 122: BIF_RET(res);
-: 123: }
-: 124:
#####: 125: BIF_ERROR(BIF_P, BADARG);
-: 126:}
-: 127:
-: 128:/* maps:to_list/1 */
-: 129:
853583: 130:BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
853583: 131: if (is_flatmap(BIF_ARG_1)) {
-: 132: Uint n;
-: 133: Eterm* hp;
-: 134: Eterm *ks,*vs, res, tup;
851565: 135: flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
-: 136:
851565: 137: ks = flatmap_get_keys(mp);
851565: 138: vs = flatmap_get_values(mp);
851565: 139: n = flatmap_get_size(mp);
851565: 140: hp = HAlloc(BIF_P, (2 + 3) * n);
851565: 141: res = NIL;
-: 142:
7121251: 143: while(n--) {
5418121: 144: tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
5418121: 145: res = CONS(hp, tup, res); hp += 2;
-: 146: }
-: 147:
851565: 148: BIF_RET(res);
2018: 149: } else if (is_hashmap(BIF_ARG_1)) {
2018: 150: return hashmap_to_list(BIF_P, BIF_ARG_1);
-: 151: }
-: 152:
#####: 153: BIF_ERROR(BIF_P, BADARG);
-: 154:}
-: 155:
-: 156:/* maps:find/2
-: 157: * return value if key *matches* a key in the map
-: 158: */
-: 159:
-: 160:const Eterm *
-: 161:#if HALFWORD_HEAP
-: 162:erts_maps_get_rel(Eterm key, Eterm map, Eterm *map_base)
-: 163:#else
6703: 164:erts_maps_get(Eterm key, Eterm map)
-: 165:#endif
-: 166:{
-: 167: Uint32 hx;
6703: 168: if (is_flatmap_rel(map, map_base)) {
-: 169: Eterm *ks, *vs;
-: 170: flatmap_t *mp;
-: 171: Uint n, i;
-: 172:
4101: 173: mp = (flatmap_t *)flatmap_val_rel(map, map_base);
4101: 174: n = flatmap_get_size(mp);
-: 175:
4101: 176: if (n == 0) {
184: 177: return NULL;
-: 178: }
-: 179:
3917: 180: ks = (Eterm *)tuple_val_rel(mp->keys, map_base) + 1;
3917: 181: vs = flatmap_get_values(mp);
-: 182:
3917: 183: if (is_immed(key)) {
15482: 184: for (i = 0; i < n; i++) {
15241: 185: if (ks[i] == key) {
3230: 186: return &vs[i];
-: 187: }
-: 188: }
-: 189: }
-: 190:
7764: 191: for (i = 0; i < n; i++) {
7451: 192: if (eq_rel(ks[i], map_base, key, NULL)) {
374: 193: return &vs[i];
-: 194: }
-: 195: }
313: 196: return NULL;
-: 197: }
-: 198: ASSERT(is_hashmap_rel(map, map_base));
2602: 199: hx = hashmap_make_hash(key);
-: 200:
2602: 201: return erts_hashmap_get_rel(hx, key, map, map_base);
-: 202:}
-: 203:
4358: 204:BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
4358: 205: if (is_map(BIF_ARG_2)) {
-: 206: Eterm *hp, res;
-: 207: const Eterm *value;
-: 208:
4358: 209: value = erts_maps_get(BIF_ARG_1, BIF_ARG_2);
4358: 210: if (value) {
3861: 211: hp = HAlloc(BIF_P, 3);
3861: 212: res = make_tuple(hp);
3861: 213: *hp++ = make_arityval(2);
3861: 214: *hp++ = am_ok;
3861: 215: *hp++ = *value;
3861: 216: BIF_RET(res);
-: 217: }
497: 218: BIF_RET(am_error);
-: 219: }
#####: 220: BIF_ERROR(BIF_P, BADARG);
-: 221:}
-: 222:
-: 223:/* maps:get/2
-: 224: * return value if key *matches* a key in the map
-: 225: * exception bad_key if none matches
-: 226: */
-: 227:
1187: 228:BIF_RETTYPE maps_get_2(BIF_ALIST_2) {
1187: 229: if (is_map(BIF_ARG_2)) {
-: 230: Eterm *hp;
-: 231: Eterm error;
-: 232: const Eterm *value;
-: 233: char *s_error;
-: 234:
1187: 235: value = erts_maps_get(BIF_ARG_1, BIF_ARG_2);
1187: 236: if (value) {
960: 237: BIF_RET(*value);
-: 238: }
-: 239:
227: 240: s_error = "bad_key";
227: 241: error = am_atom_put(s_error, sys_strlen(s_error));
-: 242:
227: 243: hp = HAlloc(BIF_P, 3);
227: 244: BIF_P->fvalue = TUPLE2(hp, error, BIF_ARG_1);
227: 245: BIF_ERROR(BIF_P, EXC_ERROR_2);
-: 246: }
#####: 247: BIF_ERROR(BIF_P, BADARG);
-: 248:}
-: 249:
-: 250:/* maps:from_list/1
-: 251: * List may be unsorted [{K,V}]
-: 252: */
-: 253:
163969: 254:BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) {
163969: 255: Eterm item = BIF_ARG_1, res, *kv;
163969: 256: Uint size = 0;
163969: 257: if (is_list(item) || is_nil(item)) {
-: 258:
-: 259: /* Calculate size and check validity */
-: 260:
1711551: 261: while(is_list(item)) {
1383613: 262: res = CAR(list_val(item));
1383613: 263: if (is_not_tuple(res))
-: 264: goto error;
-: 265:
1383613: 266: kv = tuple_val(res);
1383613: 267: if (*kv != make_arityval(2))
#####: 268: goto error;
-: 269:
1383613: 270: size++;
1383613: 271: item = CDR(list_val(item));
-: 272: }
-: 273:
163969: 274: if (is_not_nil(item))
#####: 275: goto error;
-: 276:
163969: 277: if (size > MAP_SMALL_MAP_LIMIT) {
4794: 278: BIF_RET(hashmap_from_validated_list(BIF_P, BIF_ARG_1, size));
-: 279: } else {
159175: 280: BIF_RET(flatmap_from_validated_list(BIF_P, BIF_ARG_1, size));
-: 281: }
-: 282: }
-: 283:
-: 284:error:
-: 285:
#####: 286: BIF_ERROR(BIF_P, BADARG);
-: 287:}
-: 288:
159175: 289:static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size) {
159175: 290: Eterm *kv, item = list;
-: 291: Eterm *hp, *thp,*vs, *ks, keys, res;
-: 292: flatmap_t *mp;
159175: 293: Uint unused_size = 0;
159175: 294: Sint c = 0;
159175: 295: Sint idx = 0;
-: 296:
-: 297:
159175: 298: hp = HAlloc(p, 3 + 1 + (2 * size));
159175: 299: thp = hp;
159175: 300: keys = make_tuple(hp);
159175: 301: *hp++ = make_arityval(size);
159175: 302: ks = hp;
159175: 303: hp += size;
159175: 304: mp = (flatmap_t*)hp;
159175: 305: res = make_flatmap(mp);
159175: 306: hp += MAP_HEADER_FLATMAP_SZ;
159175: 307: vs = hp;
-: 308:
159175: 309: mp->thing_word = MAP_HEADER_FLATMAP;
159175: 310: mp->size = size; /* set later, might shrink*/
159175: 311: mp->keys = keys;
-: 312:
159175: 313: if (size == 0)
13860: 314: return res;
-: 315:
-: 316: /* first entry */
145315: 317: kv = tuple_val(CAR(list_val(item)));
145315: 318: ks[0] = kv[1];
145315: 319: vs[0] = kv[2];
145315: 320: size = 1;
145315: 321: item = CDR(list_val(item));
-: 322:
-: 323: /* insert sort key/value pairs */
1163476: 324: while(is_list(item)) {
-: 325:
872846: 326: kv = tuple_val(CAR(list_val(item)));
-: 327:
-: 328: /* compare ks backwards
-: 329: * idx represent word index to be written (hole position).
-: 330: * We cannot copy the elements when searching since we might
-: 331: * have an equal key. So we search for just the index first =(
-: 332: *
-: 333: * It is perhaps faster to move the values in the first pass.
-: 334: * Check for uniqueness during insert phase and then have a
-: 335: * second phace compacting the map if duplicates are found
-: 336: * during insert. .. or do someother sort .. shell-sort perhaps.
-: 337: */
-: 338:
872846: 339: idx = size;
-: 340:
872846: 341: while(idx > 0 && (c = CMP_TERM(kv[1],ks[idx-1])) < 0) { idx--; }
-: 342:
872846: 343: if (c == 0) {
-: 344: /* last compare was equal,
-: 345: * i.e. we have to release memory
-: 346: * and overwrite that key/value
-: 347: */
189: 348: ks[idx-1] = kv[1];
189: 349: vs[idx-1] = kv[2];
189: 350: unused_size++;
-: 351: } else {
872657: 352: Uint i = size;
1948147: 353: while(i > idx) {
202833: 354: ks[i] = ks[i-1];
202833: 355: vs[i] = vs[i-1];
202833: 356: i--;
-: 357: }
872657: 358: ks[idx] = kv[1];
872657: 359: vs[idx] = kv[2];
872657: 360: size++;
-: 361: }
872846: 362: item = CDR(list_val(item));
-: 363: }
-: 364:
145315: 365: if (unused_size) {
-: 366: /* the key tuple is embedded in the heap
-: 367: * write a bignum to clear it.
-: 368: */
-: 369: /* release values as normal since they are on the top of the heap */
-: 370:
77: 371: ks[size] = make_pos_bignum_header(unused_size - 1);
77: 372: HRelease(p, vs + size + unused_size, vs + size);
-: 373: }
-: 374:
145315: 375: *thp = make_arityval(size);
145315: 376: mp->size = size;
145315: 377: return res;
-: 378:}
-: 379:
-: 380:#define swizzle32(D,S) \
-: 381: do { \
-: 382: (D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20 \
-: 383: | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4 \
-: 384: | ((S) & 0x000f0000) >> 4 | ((S) & 0x00f00000) >> 12 \
-: 385: | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \
-: 386: } while(0)
-: 387:
-: 388:#define maskval(V,L) (((V) >> ((7 - (L))*4)) & 0xf)
-: 389:#define cdepth(V1,V2) (hashmap_clz((V1) ^ (V2)) >> 2)
-: 390:
4794: 391:static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
4794: 392: Eterm item = list;
-: 393: Eterm *hp;
-: 394: Eterm *kv, res;
-: 395: Eterm tmp[2];
-: 396: Uint32 sw, hx;
4794: 397: Uint ix = 0;
-: 398: hxnode_t *hxns;
-: 399: ErtsHeapFactory factory;
-: 400:
-: 401: ASSERT(size > 0);
-: 402:
4794: 403: hp = HAlloc(p, (2 * size));
-: 404:
-: 405: /* create tmp hx values and leaf ptrs */
4794: 406: hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, size * sizeof(hxnode_t));
-: 407:
375040: 408: while(is_list(item)) {
365452: 409: res = CAR(list_val(item));
365452: 410: kv = tuple_val(res);
365452: 411: hx = hashmap_restore_hash(tmp,0,kv[1]);
365452: 412: swizzle32(sw,hx);
365452: 413: hxns[ix].hx = sw;
365452: 414: hxns[ix].val = CONS(hp, kv[1], kv[2]); hp += 2;
365452: 415: hxns[ix].skip = 1; /* will be reassigned in from_array */
365452: 416: hxns[ix].i = ix;
365452: 417: ix++;
365452: 418: item = CDR(list_val(item));
-: 419: }
-: 420:
4794: 421: factory.p = p;
4794: 422: res = hashmap_from_unsorted_array(&factory, hxns, size, 0);
-: 423:
4794: 424: erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-: 425: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 426:
4794: 427: if (hashmap_size(res) <= MAP_SMALL_MAP_LIMIT) {
20: 428: DECLARE_WSTACK(wstack);
-: 429: Eterm *kv, *ks, *vs;
-: 430: flatmap_t *mp;
-: 431: Eterm keys;
20: 432: Uint n = hashmap_size(res);
-: 433:
-: 434: /* build flat structure */
20: 435: hp = HAlloc(p, 3 + 1 + (2 * n));
20: 436: keys = make_tuple(hp);
20: 437: *hp++ = make_arityval(n);
20: 438: ks = hp;
20: 439: hp += n;
20: 440: mp = (flatmap_t*)hp;
20: 441: hp += MAP_HEADER_FLATMAP_SZ;
20: 442: vs = hp;
-: 443:
20: 444: mp->thing_word = MAP_HEADER_FLATMAP;
20: 445: mp->size = n;
20: 446: mp->keys = keys;
-: 447:
20: 448: hashmap_iterator_init(&wstack, res, 0);
-: 449:
614: 450: while ((kv=hashmap_iterator_next(&wstack)) != NULL) {
574: 451: *ks++ = CAR(kv);
574: 452: *vs++ = CDR(kv);
-: 453: }
-: 454:
-: 455: /* it cannot have multiple keys */
20: 456: erts_validate_and_sort_flatmap(mp);
-: 457:
20: 458: DESTROY_WSTACK(wstack);
20: 459: return make_flatmap(mp);
-: 460: }
-: 461:
4774: 462: return res;
-: 463:}
-: 464:
#####: 465:Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n,
-: 466: int reject_dupkeys) {
-: 467: Uint32 sw, hx;
-: 468: Uint ix;
-: 469: hxnode_t *hxns;
-: 470: Eterm res;
-: 471:
-: 472: /* create tmp hx values and leaf ptrs */
#####: 473: hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
-: 474:
#####: 475: for (ix = 0; ix < n; ix++) {
#####: 476: hx = hashmap_make_hash(*leafs);
#####: 477: swizzle32(sw,hx);
#####: 478: hxns[ix].hx = sw;
#####: 479: hxns[ix].val = make_list(leafs);
#####: 480: hxns[ix].skip = 1;
#####: 481: hxns[ix].i = ix;
#####: 482: leafs += 2;
-: 483: }
-: 484:
#####: 485: res = hashmap_from_unsorted_array(factory, hxns, n, reject_dupkeys);
-: 486:
#####: 487: erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-: 488:
#####: 489: return res;
-: 490:}
-: 491:
-: 492:
267: 493:Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n,
-: 494: Eterm key, Eterm value) {
-: 495: Uint32 sw, hx;
-: 496: Uint i,sz;
-: 497: hxnode_t *hxns;
-: 498: ErtsHeapFactory factory;
-: 499: Eterm *hp, res;
-: 500:
267: 501: sz = (key == THE_NON_VALUE) ? n : (n + 1);
-: 502: ASSERT(sz > MAP_SMALL_MAP_LIMIT);
267: 503: hp = HAlloc(p, 2 * sz);
-: 504:
-: 505: /* create tmp hx values and leaf ptrs */
267: 506: hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, sz * sizeof(hxnode_t));
-: 507:
8811: 508: for(i = 0; i < n; i++) {
8544: 509: hx = hashmap_make_hash(ks[i]);
8544: 510: swizzle32(sw,hx);
8544: 511: hxns[i].hx = sw;
8544: 512: hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2;
8544: 513: hxns[i].skip = 1; /* will be reassigned in from_array */
8544: 514: hxns[i].i = i;
-: 515: }
-: 516:
267: 517: if (key != THE_NON_VALUE) {
267: 518: hx = hashmap_make_hash(key);
267: 519: swizzle32(sw,hx);
267: 520: hxns[i].hx = sw;
267: 521: hxns[i].val = CONS(hp, key, value); hp += 2;
267: 522: hxns[i].skip = 1;
267: 523: hxns[i].i = i;
-: 524: }
-: 525:
267: 526: factory.p = p;
267: 527: res = hashmap_from_unsorted_array(&factory, hxns, sz, 0);
-: 528:
267: 529: erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-: 530: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 531:
267: 532: return res;
-: 533:}
-: 534:
5061: 535:static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory,
-: 536: hxnode_t *hxns, Uint n,
-: 537: int reject_dupkeys) {
5061: 538: Uint jx = 0, ix = 0, lx, cx;
-: 539: Eterm res;
-: 540:
5061: 541: if (n == 0) {
-: 542: Eterm *hp;
#####: 543: hp = erts_produce_heap(factory, 2, 0);
#####: 544: hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0);
#####: 545: hp[1] = 0;
-: 546:
#####: 547: return make_hashmap(hp);
-: 548: }
-: 549:
-: 550: /* sort and compact array (remove non-unique entries) */
5061: 551: qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
-: 552:
5061: 553: ix = 0, cx = 0;
337101: 554: while(ix < n - 1) {
326979: 555: if (hxns[ix].hx == hxns[ix+1].hx) {
-: 556:
-: 557: /* find region of equal hash values */
39034: 558: jx = ix + 1;
39034: 559: while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
-: 560: /* find all correct keys from region
-: 561: * (last in list but now hash sorted so we check highest id instead) */
-: 562:
-: 563: /* resort with keys instead of hash value within region */
-: 564:
39034: 565: qsort(&hxns[ix], jx - ix, sizeof(hxnode_t),
-: 566: (int (*)(const void *, const void *)) hxnodecmpkey);
-: 567:
154644: 568: while(ix < jx) {
76576: 569: lx = ix;
234842: 570: while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
81690: 571: if (reject_dupkeys)
#####: 572: return THE_NON_VALUE;
-: 573:
81690: 574: if (hxns[ix].i > hxns[lx].i) {
5114: 575: lx = ix;
-: 576: }
81690: 577: ix++;
-: 578: }
76576: 579: hxns[cx].hx = hxns[lx].hx;
76576: 580: hxns[cx].val = hxns[lx].val;
76576: 581: cx++;
-: 582: }
39034: 583: ix = jx;
39034: 584: continue;
-: 585: }
287945: 586: if (ix > cx) {
10370: 587: hxns[cx].hx = hxns[ix].hx;
10370: 588: hxns[cx].val = hxns[ix].val;
-: 589: }
287945: 590: cx++;
287945: 591: ix++;
-: 592: }
-: 593:
5061: 594: if (ix < n) {
4628: 595: hxns[cx].hx = hxns[ix].hx;
4628: 596: hxns[cx].val = hxns[ix].val;
4628: 597: cx++;
-: 598: }
-: 599:
5061: 600: if (cx > 1) {
-: 601: /* recursive decompose array */
5061: 602: res = hashmap_from_sorted_unique_array(factory, hxns, cx, 0);
-: 603: } else {
-: 604: Eterm *hp;
-: 605:
-: 606: /* we only have one item, either because n was 1 or
-: 607: * because we hade multiples of the same key.
-: 608: *
-: 609: * hash value has been swizzled, need to drag it down to get the
-: 610: * correct slot. */
-: 611:
#####: 612: hp = erts_produce_heap(factory, HAMT_HEAD_BITMAP_SZ(1), 0);
#####: 613: hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
#####: 614: hp[1] = 1;
#####: 615: hp[2] = hxns[0].val;
#####: 616: res = make_hashmap(hp);
-: 617: }
-: 618:
5061: 619: return res;
-: 620:}
-: 621:
42603: 622:static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
-: 623: hxnode_t *hxns, Uint n, int lvl) {
42603: 624: Eterm res = NIL;
-: 625: Uint i,ix,jx,elems;
-: 626: Uint32 sw, hx;
-: 627: Eterm val;
-: 628: Eterm th[2];
-: 629: hxnode_t *tmp;
-: 630:
-: 631: ASSERT(lvl < 32);
42603: 632: ix = 0;
42603: 633: elems = 1;
449717: 634: while (ix < n - 1) {
364511: 635: if (hxns[ix].hx == hxns[ix+1].hx) {
37542: 636: jx = ix + 1;
37542: 637: while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
37542: 638: tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t));
-: 639:
112626: 640: for(i = 0; i < jx - ix; i++) {
75084: 641: val = hxns[i + ix].val;
75084: 642: hx = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
75084: 643: swizzle32(sw,hx);
75084: 644: tmp[i].hx = sw;
75084: 645: tmp[i].val = val;
75084: 646: tmp[i].i = i;
75084: 647: tmp[i].skip = 1;
-: 648: }
-: 649:
37542: 650: qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
-: 651:
37542: 652: hxns[ix].skip = jx - ix;
37542: 653: hxns[ix].val = hashmap_from_sorted_unique_array(factory, tmp, jx - ix, lvl + 8);
37542: 654: erts_free(ERTS_ALC_T_TMP, (void *) tmp);
37542: 655: ix = jx;
37542: 656: if (ix < n) { elems++; }
37542: 657: continue;
-: 658: }
326969: 659: hxns[ix].skip = 1;
326969: 660: elems++;
326969: 661: ix++;
-: 662: }
-: 663:
42603: 664: res = hashmap_from_chunked_array(factory, hxns, elems, n, !lvl);
-: 665:
-: 666: ERTS_FACTORY_HOLE_CHECK(factory);
-: 667:
42603: 668: return res;
-: 669:}
-: 670:
-: 671:#define HALLOC_EXTRA 200
42603: 672:static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns, Uint n,
-: 673: Uint size, int is_root) {
-: 674: Uint ix, d, dn, dc, slot, elems;
-: 675: Uint32 v, vp, vn, hdr;
-: 676: Uint bp, sz;
42603: 677: DECLARE_ESTACK(stack);
42603: 678: Eterm res = NIL, *hp = NULL, *nhp;
-: 679:
-: 680: ASSERT(n > 1);
-: 681:
-: 682: /* push initial nodes on the stack,
-: 683: * this is the starting depth */
-: 684:
42603: 685: ix = 0;
42603: 686: d = 0;
42603: 687: vp = hxns[ix].hx;
42603: 688: v = hxns[ix + hxns[ix].skip].hx;
-: 689:
-: 690: ASSERT(vp > v);
42603: 691: slot = maskval(vp,d);
-: 692:
95019: 693: while(slot == maskval(v,d)) {
9813: 694: ESTACK_PUSH(stack, 1 << slot);
9813: 695: d++;
9813: 696: slot = maskval(vp,d);
-: 697: }
-: 698:
42603: 699: res = hxns[ix].val;
-: 700:
42603: 701: if (hxns[ix].skip > 1) {
412: 702: dc = 7;
-: 703: /* build collision nodes */
3222: 704: while (dc > d) {
2398: 705: hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
2398: 706: hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc));
2398: 707: hp[1] = res;
2398: 708: res = make_hashmap(hp);
2398: 709: dc--;
-: 710: }
-: 711: }
-: 712:
42603: 713: ESTACK_PUSH2(stack,res,1 << slot);
-: 714:
-: 715: /* all of the other nodes .. */
42603: 716: elems = n - 2; /* remove first and last elements */
406691: 717: while(elems--) {
321485: 718: hdr = ESTACK_POP(stack);
321485: 719: ix = ix + hxns[ix].skip;
-: 720:
-: 721: /* determine if node or subtree should be built by looking
-: 722: * at the next value. */
-: 723:
321485: 724: vn = hxns[ix + hxns[ix].skip].hx;
321485: 725: dn = cdepth(v,vn);
-: 726: ASSERT(v > vn);
-: 727:
321485: 728: res = hxns[ix].val;
-: 729:
321485: 730: if (hxns[ix].skip > 1) {
36707: 731: int wat = (d > dn) ? d : dn;
36707: 732: dc = 7;
-: 733: /* build collision nodes */
281627: 734: while (dc > wat) {
208213: 735: hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
208213: 736: hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
208213: 737: hp[1] = res;
208213: 738: res = make_hashmap(hp);
208213: 739: dc--;
-: 740: }
-: 741: }
-: 742:
-: 743: /* next depth is higher (implies collision) */
321485: 744: if (d < dn) {
-: 745: /* hdr is the popped one initially */
300143: 746: while(d < dn) {
106983: 747: slot = maskval(v, d);
106983: 748: bp = 1 << slot;
106983: 749: ESTACK_PUSH(stack, hdr | bp);
106983: 750: d++;
106983: 751: hdr = 0; /* clear hdr for all other collisions */
-: 752: }
-: 753:
96580: 754: slot = maskval(v, d);
96580: 755: bp = 1 << slot;
-: 756: /* no more collisions */
96580: 757: ESTACK_PUSH2(stack,res,bp);
224905: 758: } else if (d == dn) {
-: 759: /* no collisions at all */
130871: 760: slot = maskval(v, d);
130871: 761: bp = 1 << slot;
130871: 762: ESTACK_PUSH2(stack,res,hdr | bp);
-: 763: } else {
-: 764: /* dn < n, we have a drop and we are done
-: 765: * build nodes and subtree */
295769: 766: while (dn != d) {
107701: 767: slot = maskval(v, d);
107701: 768: bp = 1 << slot;
-: 769: /* OR bitposition before sz calculation to handle
-: 770: * redundant collisions */
107701: 771: hdr |= bp;
107701: 772: sz = hashmap_bitcount(hdr);
107701: 773: hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
107701: 774: nhp = hp;
107701: 775: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
107701: 776: *hp++ = res; sz--;
107701: 777: while (sz--) { *hp++ = ESTACK_POP(stack); }
-: 778: ASSERT((hp - nhp) < 18);
107701: 779: res = make_hashmap(nhp);
-: 780:
-: 781: /* we need to pop the next hdr and push if we don't need it */
-: 782:
107701: 783: hdr = ESTACK_POP(stack);
107701: 784: d--;
-: 785: }
94034: 786: ESTACK_PUSH2(stack,res,hdr);
-: 787: }
-: 788:
321485: 789: vp = v;
321485: 790: v = vn;
321485: 791: d = dn;
-: 792: ERTS_FACTORY_HOLE_CHECK(factory);
-: 793: }
-: 794:
-: 795: /* v and vp are reused from above */
42603: 796: dn = cdepth(vp,v);
42603: 797: ix = ix + hxns[ix].skip;
42603: 798: res = hxns[ix].val;
-: 799:
42603: 800: if (hxns[ix].skip > 1) {
423: 801: dc = 7;
-: 802: /* build collision nodes */
3344: 803: while (dc > dn) {
2498: 804: hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
2498: 805: hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
2498: 806: hp[1] = res;
2498: 807: res = make_hashmap(hp);
2498: 808: dc--;
-: 809: }
-: 810: }
-: 811:
42603: 812: hdr = ESTACK_POP(stack);
-: 813: /* pop remaining subtree if any */
94301: 814: while (dn) {
9095: 815: slot = maskval(v, dn);
9095: 816: bp = 1 << slot;
-: 817: /* OR bitposition before sz calculation to handle
-: 818: * redundant collisions */
9095: 819: hdr |= bp;
9095: 820: sz = hashmap_bitcount(hdr);
9095: 821: hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
9095: 822: nhp = hp;
9095: 823: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
9095: 824: *hp++ = res; sz--;
-: 825:
9095: 826: while (sz--) { *hp++ = ESTACK_POP(stack); }
9095: 827: res = make_hashmap(nhp);
9095: 828: hdr = ESTACK_POP(stack);
9095: 829: dn--;
-: 830: }
-: 831:
-: 832: /* and finally the root .. */
-: 833:
42603: 834: slot = maskval(v, dn);
42603: 835: bp = 1 << slot;
42603: 836: hdr |= bp;
42603: 837: sz = hashmap_bitcount(hdr);
42603: 838: hp = erts_produce_heap(factory, sz + /* hdr + item */ (is_root ? 2 : 1), 0);
42603: 839: nhp = hp;
-: 840:
42603: 841: if (is_root) {
5061: 842: *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
5061: 843: *hp++ = size;
-: 844: } else {
37542: 845: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
-: 846: }
-: 847:
42603: 848: *hp++ = res; sz--;
42603: 849: while (sz--) { *hp++ = ESTACK_POP(stack); }
-: 850:
42603: 851: res = make_hashmap(nhp);
-: 852:
-: 853: ASSERT(ESTACK_COUNT(stack) == 0);
42603: 854: DESTROY_ESTACK(stack);
-: 855: ERTS_FACTORY_HOLE_CHECK(factory);
42603: 856: return res;
-: 857:}
-: 858:#undef HALLOC_EXTRA
-: 859:
46116: 860:static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
46116: 861: return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
-: 862:}
-: 863:
1895662: 864:static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
1895662: 865: if (a->hx < b->hx)
932429: 866: return 1;
963233: 867: else if (a->hx == b->hx)
45641: 868: return 0;
-: 869: else
917592: 870: return -1;
-: 871:}
-: 872:
-: 873:/* maps:is_key/2 */
-: 874:
1158: 875:BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) {
1158: 876: if (is_map(BIF_ARG_2)) {
1158: 877: BIF_RET(erts_maps_get(BIF_ARG_1, BIF_ARG_2) ? am_true : am_false);
-: 878: }
#####: 879: BIF_ERROR(BIF_P, BADARG);
-: 880:}
-: 881:
-: 882:/* maps:keys/1 */
-: 883:
1174: 884:BIF_RETTYPE maps_keys_1(BIF_ALIST_1) {
1174: 885: if (is_flatmap(BIF_ARG_1)) {
565: 886: Eterm *hp, *ks, res = NIL;
-: 887: flatmap_t *mp;
-: 888: Uint n;
-: 889:
565: 890: mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
565: 891: n = flatmap_get_size(mp);
-: 892:
565: 893: if (n == 0)
50: 894: BIF_RET(res);
-: 895:
515: 896: hp = HAlloc(BIF_P, (2 * n));
515: 897: ks = flatmap_get_keys(mp);
-: 898:
6930: 899: while(n--) {
5900: 900: res = CONS(hp, ks[n], res); hp += 2;
-: 901: }
-: 902:
515: 903: BIF_RET(res);
609: 904: } else if (is_hashmap(BIF_ARG_1)) {
609: 905: BIF_RET(hashmap_keys(BIF_P, BIF_ARG_1));
-: 906: }
#####: 907: BIF_ERROR(BIF_P, BADARG);
-: 908:}
-: 909:/* maps:merge/2 */
-: 910:
74: 911:BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
74: 912: if (is_flatmap(BIF_ARG_1)) {
74: 913: if (is_flatmap(BIF_ARG_2)) {
74: 914: BIF_RET(flatmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
#####: 915: } else if (is_hashmap(BIF_ARG_2)) {
-: 916: /* Will always become a tree */
#####: 917: BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0));
-: 918: }
#####: 919: } else if (is_hashmap(BIF_ARG_1)) {
#####: 920: if (is_hashmap(BIF_ARG_2)) {
#####: 921: BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
#####: 922: } else if (is_flatmap(BIF_ARG_2)) {
-: 923: /* Will always become a tree */
#####: 924: BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1));
-: 925: }
-: 926: }
#####: 927: BIF_ERROR(BIF_P, BADARG);
-: 928:}
-: 929:
74: 930:static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
-: 931: Eterm *hp,*thp;
-: 932: Eterm tup;
-: 933: Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
-: 934: flatmap_t *mp1,*mp2,*mp_new;
74: 935: Uint n,n1,n2,i1,i2,need,unused_size=0;
74: 936: Sint c = 0;
-: 937:
74: 938: mp1 = (flatmap_t*)flatmap_val(nodeA);
74: 939: mp2 = (flatmap_t*)flatmap_val(nodeB);
74: 940: n1 = flatmap_get_size(mp1);
74: 941: n2 = flatmap_get_size(mp2);
-: 942:
74: 943: need = MAP_HEADER_FLATMAP_SZ + 1 + 2 * (n1 + n2);
-: 944:
74: 945: hp = HAlloc(p, need);
74: 946: thp = hp;
74: 947: tup = make_tuple(thp);
74: 948: ks = hp + 1; hp += 1 + n1 + n2;
74: 949: mp_new = (flatmap_t*)hp; hp += MAP_HEADER_FLATMAP_SZ;
74: 950: vs = hp; hp += n1 + n2;
-: 951:
74: 952: mp_new->thing_word = MAP_HEADER_FLATMAP;
74: 953: mp_new->size = 0;
74: 954: mp_new->keys = tup;
-: 955:
74: 956: i1 = 0; i2 = 0;
74: 957: ks1 = flatmap_get_keys(mp1);
74: 958: vs1 = flatmap_get_values(mp1);
74: 959: ks2 = flatmap_get_keys(mp2);
74: 960: vs2 = flatmap_get_values(mp2);
-: 961:
544: 962: while(i1 < n1 && i2 < n2) {
396: 963: c = CMP_TERM(ks1[i1],ks2[i2]);
396: 964: if (c == 0) {
-: 965: /* use righthand side arguments map value,
-: 966: * but advance both maps */
164: 967: *ks++ = ks2[i2];
164: 968: *vs++ = vs2[i2];
164: 969: i1++, i2++, unused_size++;
232: 970: } else if (c < 0) {
#####: 971: *ks++ = ks1[i1];
#####: 972: *vs++ = vs1[i1];
#####: 973: i1++;
-: 974: } else {
232: 975: *ks++ = ks2[i2];
232: 976: *vs++ = vs2[i2];
232: 977: i2++;
-: 978: }
-: 979: }
-: 980:
-: 981: /* copy remaining */
148: 982: while (i1 < n1) {
#####: 983: *ks++ = ks1[i1];
#####: 984: *vs++ = vs1[i1];
#####: 985: i1++;
-: 986: }
-: 987:
148: 988: while (i2 < n2) {
#####: 989: *ks++ = ks2[i2];
#####: 990: *vs++ = vs2[i2];
#####: 991: i2++;
-: 992: }
-: 993:
74: 994: if (unused_size) {
-: 995: /* the key tuple is embedded in the heap, write a bignum to clear it.
-: 996: *
-: 997: * release values as normal since they are on the top of the heap
-: 998: * size = n1 + n1 - unused_size
-: 999: */
-: 1000:
74: 1001: *ks = make_pos_bignum_header(unused_size - 1);
74: 1002: HRelease(p, vs + unused_size, vs);
-: 1003: }
-: 1004:
74: 1005: n = n1 + n2 - unused_size;
74: 1006: *thp = make_arityval(n);
74: 1007: mp_new->size = n;
-: 1008:
-: 1009: /* Reshape map to a hashmap if the map exceeds the limit */
-: 1010:
74: 1011: if (n > MAP_SMALL_MAP_LIMIT) {
-: 1012: Uint32 hx,sw;
-: 1013: Uint i;
-: 1014: Eterm res;
-: 1015: hxnode_t *hxns;
-: 1016: ErtsHeapFactory factory;
-: 1017:
#####: 1018: ks = flatmap_get_keys(mp_new);
#####: 1019: vs = flatmap_get_values(mp_new);
-: 1020:
#####: 1021: hp = HAlloc(p, 2 * n);
-: 1022:
#####: 1023: hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP,n * sizeof(hxnode_t));
-: 1024:
#####: 1025: for (i = 0; i < n; i++) {
#####: 1026: hx = hashmap_make_hash(ks[i]);
#####: 1027: swizzle32(sw,hx);
#####: 1028: hxns[i].hx = sw;
#####: 1029: hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2;
#####: 1030: hxns[i].skip = 1;
#####: 1031: hxns[i].i = i;
-: 1032: }
-: 1033:
#####: 1034: factory.p = p;
#####: 1035: res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
-: 1036:
#####: 1037: erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-: 1038: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 1039:
#####: 1040: return res;
-: 1041: }
-: 1042:
74: 1043: return make_flatmap(mp_new);
-: 1044:}
-: 1045:
#####: 1046:static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args) {
-: 1047: Eterm *ks, *vs, *hp, res;
-: 1048: flatmap_t *mp;
-: 1049: Uint n, i;
-: 1050: hxnode_t *hxns;
-: 1051: Uint32 sw, hx;
-: 1052: ErtsHeapFactory factory;
-: 1053:
-: 1054: /* convert flat to tree */
-: 1055:
-: 1056: ASSERT(is_flatmap(flat));
-: 1057: ASSERT(is_hashmap(tree));
-: 1058:
#####: 1059: mp = (flatmap_t*)flatmap_val(flat);
#####: 1060: n = flatmap_get_size(mp);
-: 1061:
#####: 1062: ks = flatmap_get_keys(mp);
#####: 1063: vs = flatmap_get_values(mp);
-: 1064:
#####: 1065: hp = HAlloc(p, 2 * n);
-: 1066:
#####: 1067: hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
-: 1068:
#####: 1069: for (i = 0; i < n; i++) {
#####: 1070: hx = hashmap_make_hash(ks[i]);
#####: 1071: swizzle32(sw,hx);
#####: 1072: hxns[i].hx = sw;
#####: 1073: hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2;
#####: 1074: hxns[i].skip = 1;
#####: 1075: hxns[i].i = i;
-: 1076: }
-: 1077:
#####: 1078: factory.p = p;
#####: 1079: res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
-: 1080:
#####: 1081: erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-: 1082: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 1083:
#####: 1084: return swap_args ? hashmap_merge(p, tree, res) : hashmap_merge(p, res, tree);
-: 1085:}
-: 1086:
-: 1087:#define HALLOC_EXTRA 200
-: 1088:
#####: 1089:static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
-: 1090:#define PSTACK_TYPE struct HashmapMergePStackType
-: 1091: struct HashmapMergePStackType {
-: 1092: Eterm *srcA, *srcB;
-: 1093: Uint32 abm, bbm, rbm; /* node bitmaps */
-: 1094: int keepA;
-: 1095: int ix;
-: 1096: Eterm array[16];
-: 1097: };
#####: 1098: PSTACK_DECLARE(s, 4);
#####: 1099: struct HashmapMergePStackType* sp = PSTACK_PUSH(s);
-: 1100: Eterm *hp, *nhp;
-: 1101: Eterm hdrA, hdrB;
-: 1102: Eterm th[2];
-: 1103: Uint32 ahx, bhx;
-: 1104: Uint size; /* total key-value counter */
#####: 1105: int keepA = 0;
#####: 1106: unsigned lvl = 0;
#####: 1107: Eterm res = THE_NON_VALUE;
-: 1108:
-: 1109: /*
-: 1110: * Strategy: Do depth-first traversal of both trees (at the same time)
-: 1111: * and merge each pair of nodes.
-: 1112: */
-: 1113:
-: 1114: {
#####: 1115: hashmap_head_t* a = (hashmap_head_t*) hashmap_val(nodeA);
#####: 1116: hashmap_head_t* b = (hashmap_head_t*) hashmap_val(nodeB);
#####: 1117: size = a->size + b->size;
-: 1118: }
-: 1119:
-: 1120:recurse:
-: 1121:
#####: 1122: if (primary_tag(nodeA) == TAG_PRIMARY_BOXED &&
#####: 1123: primary_tag(nodeB) == TAG_PRIMARY_LIST) {
-: 1124: /* Avoid implementing this combination by switching places */
#####: 1125: Eterm tmp = nodeA;
#####: 1126: nodeA = nodeB;
#####: 1127: nodeB = tmp;
#####: 1128: keepA = !keepA;
-: 1129: }
-: 1130:
#####: 1131: switch (primary_tag(nodeA)) {
-: 1132: case TAG_PRIMARY_LIST: {
#####: 1133: sp->srcA = list_val(nodeA);
#####: 1134: switch (primary_tag(nodeB)) {
-: 1135: case TAG_PRIMARY_LIST: { /* LEAF + LEAF */
#####: 1136: sp->srcB = list_val(nodeB);
-: 1137:
#####: 1138: if (EQ(CAR(sp->srcA), CAR(sp->srcB))) {
#####: 1139: --size;
#####: 1140: res = keepA ? nodeA : nodeB;
-: 1141: } else {
#####: 1142: ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA));
#####: 1143: bhx = hashmap_restore_hash(th, lvl, CAR(sp->srcB));
#####: 1144: sp->abm = 1 << hashmap_index(ahx);
#####: 1145: sp->bbm = 1 << hashmap_index(bhx);
-: 1146:
#####: 1147: sp->srcA = &nodeA;
#####: 1148: sp->srcB = &nodeB;
-: 1149: }
#####: 1150: break;
-: 1151: }
-: 1152: case TAG_PRIMARY_BOXED: { /* LEAF + NODE */
#####: 1153: sp->srcB = boxed_val(nodeB);
-: 1154: ASSERT(is_header(*sp->srcB));
#####: 1155: hdrB = *sp->srcB++;
-: 1156:
#####: 1157: ahx = hashmap_restore_hash(th, lvl, CAR(sp->srcA));
#####: 1158: sp->abm = 1 << hashmap_index(ahx);
#####: 1159: sp->srcA = &nodeA;
#####: 1160: switch(hdrB & _HEADER_MAP_SUBTAG_MASK) {
-: 1161: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 1162: sp->srcB++;
#####: 1163: sp->bbm = 0xffff;
#####: 1164: break;
-: 1165:
#####: 1166: case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
-: 1167: case HAMT_SUBTAG_NODE_BITMAP:
#####: 1168: sp->bbm = MAP_HEADER_VAL(hdrB);
#####: 1169: break;
-: 1170:
-: 1171: default:
#####: 1172: erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
-: 1173: break;
-: 1174: }
#####: 1175: break;
-: 1176: }
-: 1177: default:
#####: 1178: erl_exit(1, "bad primary tag %ld\r\n", nodeB);
-: 1179: }
#####: 1180: break;
-: 1181: }
-: 1182: case TAG_PRIMARY_BOXED: { /* NODE + NODE */
#####: 1183: sp->srcA = boxed_val(nodeA);
#####: 1184: hdrA = *sp->srcA++;
-: 1185: ASSERT(is_header(hdrA));
#####: 1186: switch (hdrA & _HEADER_MAP_SUBTAG_MASK) {
-: 1187: case HAMT_SUBTAG_HEAD_ARRAY: {
#####: 1188: sp->srcA++;
-: 1189: ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED);
#####: 1190: sp->abm = 0xffff;
#####: 1191: sp->srcB = boxed_val(nodeB);
#####: 1192: hdrB = *sp->srcB++;
-: 1193: ASSERT(is_header(hdrB));
#####: 1194: switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
-: 1195: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 1196: sp->srcB++;
#####: 1197: sp->bbm = 0xffff;
#####: 1198: break;
#####: 1199: case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
-: 1200: case HAMT_SUBTAG_NODE_BITMAP:
#####: 1201: sp->bbm = MAP_HEADER_VAL(hdrB);
#####: 1202: break;
-: 1203: default:
#####: 1204: erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
-: 1205: }
#####: 1206: break;
-: 1207: }
#####: 1208: case HAMT_SUBTAG_HEAD_BITMAP: sp->srcA++;
-: 1209: case HAMT_SUBTAG_NODE_BITMAP: {
-: 1210: ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED);
#####: 1211: sp->abm = MAP_HEADER_VAL(hdrA);
#####: 1212: sp->srcB = boxed_val(nodeB);
#####: 1213: hdrB = *sp->srcB++;
-: 1214: ASSERT(is_header(hdrB));
#####: 1215: switch (hdrB & _HEADER_MAP_SUBTAG_MASK) {
-: 1216: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 1217: sp->srcB++;
#####: 1218: sp->bbm = 0xffff;
#####: 1219: break;
#####: 1220: case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++;
-: 1221: case HAMT_SUBTAG_NODE_BITMAP:
#####: 1222: sp->bbm = MAP_HEADER_VAL(hdrB);
#####: 1223: break;
-: 1224:
-: 1225: default:
#####: 1226: erl_exit(1, "bad header tag %ld\r\n", *sp->srcB & _HEADER_MAP_SUBTAG_MASK);
-: 1227: }
#####: 1228: break;
-: 1229: }
-: 1230: default:
#####: 1231: erl_exit(1, "bad primary tag %ld\r\n", nodeA);
-: 1232: }
#####: 1233: break;
-: 1234: }
-: 1235: default:
#####: 1236: erl_exit(1, "bad primary tag %ld\r\n", nodeA);
-: 1237: }
-: 1238:
-: 1239: for (;;) {
#####: 1240: if (is_value(res)) { /* We have a complete (sub-)tree or leaf */
#####: 1241: if (lvl == 0)
#####: 1242: break;
-: 1243:
-: 1244: /* Pop from stack and continue build parent node */
#####: 1245: lvl--;
#####: 1246: sp = PSTACK_POP(s);
#####: 1247: sp->array[sp->ix++] = res;
#####: 1248: res = THE_NON_VALUE;
#####: 1249: if (sp->rbm) {
#####: 1250: sp->srcA++;
#####: 1251: sp->srcB++;
#####: 1252: keepA = sp->keepA;
-: 1253: }
-: 1254: } else { /* Start build a node */
#####: 1255: sp->ix = 0;
#####: 1256: sp->rbm = sp->abm | sp->bbm;
-: 1257: ASSERT(!(sp->rbm == 0 && lvl > 0));
-: 1258: }
-: 1259:
#####: 1260: while (sp->rbm) {
#####: 1261: Uint32 next = sp->rbm & (sp->rbm-1);
#####: 1262: Uint32 bit = sp->rbm ^ next;
#####: 1263: sp->rbm = next;
#####: 1264: if (sp->abm & bit) {
#####: 1265: if (sp->bbm & bit) {
-: 1266: /* Bit clash. Push and resolve by recursive merge */
#####: 1267: if (sp->rbm) {
#####: 1268: sp->keepA = keepA;
-: 1269: }
#####: 1270: nodeA = *sp->srcA;
#####: 1271: nodeB = *sp->srcB;
#####: 1272: lvl++;
#####: 1273: sp = PSTACK_PUSH(s);
#####: 1274: goto recurse;
-: 1275: } else {
#####: 1276: sp->array[sp->ix++] = *sp->srcA++;
-: 1277: }
-: 1278: } else {
-: 1279: ASSERT(sp->bbm & bit);
#####: 1280: sp->array[sp->ix++] = *sp->srcB++;
-: 1281: }
-: 1282: }
-: 1283:
-: 1284: ASSERT(sp->ix == hashmap_bitcount(sp->abm | sp->bbm));
#####: 1285: if (lvl == 0) {
#####: 1286: nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(sp->ix), HALLOC_EXTRA);
#####: 1287: hp = nhp;
#####: 1288: *hp++ = (sp->ix == 16 ? MAP_HEADER_HAMT_HEAD_ARRAY
#####: 1289: : MAP_HEADER_HAMT_HEAD_BITMAP(sp->abm | sp->bbm));
#####: 1290: *hp++ = size;
-: 1291: } else {
#####: 1292: nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sp->ix), HALLOC_EXTRA);
#####: 1293: hp = nhp;
#####: 1294: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm);
-: 1295: }
#####: 1296: memcpy(hp, sp->array, sp->ix * sizeof(Eterm));
#####: 1297: res = make_boxed(nhp);
#####: 1298: }
#####: 1299: PSTACK_DESTROY(s);
#####: 1300: return res;
-: 1301:}
-: 1302:
#####: 1303:static int hash_cmp(Uint32 ha, Uint32 hb)
-: 1304:{
-: 1305: int i;
#####: 1306: for (i=0; i<8; i++) {
#####: 1307: int cmp = (int)(ha & 0xF) - (int)(hb & 0xF);
#####: 1308: if (cmp)
#####: 1309: return cmp;
#####: 1310: ha >>= 4;
#####: 1311: hb >>= 4;
-: 1312: }
#####: 1313: return 0;
-: 1314:}
-: 1315:
#####: 1316:int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp)
-: 1317:{
-: 1318: Eterm th[2];
#####: 1319: unsigned lvl = 0;
-: 1320:
#####: 1321: if (ap && bp) {
-: 1322: ASSERT(CMP_TERM(CAR(ap), CAR(bp)) != 0);
-: 1323: for (;;) {
#####: 1324: Uint32 ha = hashmap_restore_hash(th, lvl, CAR(ap));
#####: 1325: Uint32 hb = hashmap_restore_hash(th, lvl, CAR(bp));
#####: 1326: int cmp = hash_cmp(ha, hb);
#####: 1327: if (cmp)
#####: 1328: return cmp;
#####: 1329: lvl += 8;
#####: 1330: }
-: 1331: }
#####: 1332: return ap ? -1 : 1;
-: 1333:}
-: 1334:
-: 1335:/* maps:new/0 */
-: 1336:
#####: 1337:BIF_RETTYPE maps_new_0(BIF_ALIST_0) {
-: 1338: Eterm* hp;
-: 1339: Eterm tup;
-: 1340: flatmap_t *mp;
-: 1341:
#####: 1342: hp = HAlloc(BIF_P, (MAP_HEADER_FLATMAP_SZ + 1));
#####: 1343: tup = make_tuple(hp);
#####: 1344: *hp++ = make_arityval(0);
-: 1345:
#####: 1346: mp = (flatmap_t*)hp;
#####: 1347: mp->thing_word = MAP_HEADER_FLATMAP;
#####: 1348: mp->size = 0;
#####: 1349: mp->keys = tup;
-: 1350:
#####: 1351: BIF_RET(make_flatmap(mp));
-: 1352:}
-: 1353:
-: 1354:/* maps:put/3 */
-: 1355:
32216: 1356:BIF_RETTYPE maps_put_3(BIF_ALIST_3) {
32216: 1357: if (is_map(BIF_ARG_3)) {
32216: 1358: BIF_RET(erts_maps_put(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3));
-: 1359: }
#####: 1360: BIF_ERROR(BIF_P, BADARG);
-: 1361:}
-: 1362:
-: 1363:/* maps:remove/3 */
-: 1364:
808: 1365:int erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res) {
-: 1366: Uint32 hx;
808: 1367: if (is_flatmap(map)) {
-: 1368: Sint n;
-: 1369: Uint need;
-: 1370: Eterm *hp_start;
-: 1371: Eterm *thp, *mhp;
-: 1372: Eterm *ks, *vs, tup;
375: 1373: flatmap_t *mp = (flatmap_t*)flatmap_val(map);
-: 1374:
375: 1375: n = flatmap_get_size(mp);
-: 1376:
375: 1377: if (n == 0) {
34: 1378: *res = map;
34: 1379: return 1;
-: 1380: }
-: 1381:
341: 1382: ks = flatmap_get_keys(mp);
341: 1383: vs = flatmap_get_values(mp);
-: 1384:
-: 1385: /* Assume key exists.
-: 1386: * Release allocated if it didn't.
-: 1387: * Allocate key tuple first.
-: 1388: */
-: 1389:
341: 1390: need = n + 1 - 1 + 3 + n - 1; /* tuple - 1 + map - 1 */
341: 1391: hp_start = HAlloc(p, need);
341: 1392: thp = hp_start;
341: 1393: mhp = thp + n; /* offset with tuple heap size */
-: 1394:
341: 1395: tup = make_tuple(thp);
341: 1396: *thp++ = make_arityval(n - 1);
-: 1397:
341: 1398: *res = make_flatmap(mhp);
341: 1399: *mhp++ = MAP_HEADER_FLATMAP;
341: 1400: *mhp++ = n - 1;
341: 1401: *mhp++ = tup;
-: 1402:
341: 1403: if (is_immed(key)) {
-: 1404: while (1) {
1399: 1405: if (*ks == key) {
205: 1406: goto found_key;
1194: 1407: } else if (--n) {
1153: 1408: *mhp++ = *vs++;
1153: 1409: *thp++ = *ks++;
-: 1410: } else
41: 1411: break;
1153: 1412: }
-: 1413: } else {
-: 1414: while(1) {
1058: 1415: if (EQ(*ks, key)) {
-: 1416: goto found_key;
979: 1417: } else if (--n) {
963: 1418: *mhp++ = *vs++;
963: 1419: *thp++ = *ks++;
-: 1420: } else
16: 1421: break;
963: 1422: }
-: 1423: }
-: 1424:
-: 1425: /* Not found, remove allocated memory
-: 1426: * and return previous map.
-: 1427: */
57: 1428: HRelease(p, hp_start + need, hp_start);
-: 1429:
57: 1430: *res = map;
57: 1431: return 1;
-: 1432:
-: 1433:found_key:
-: 1434: /* Copy rest of keys and values */
284: 1435: if (--n) {
220: 1436: sys_memcpy(mhp, vs+1, n*sizeof(Eterm));
220: 1437: sys_memcpy(thp, ks+1, n*sizeof(Eterm));
-: 1438: }
284: 1439: return 1;
-: 1440: }
-: 1441: ASSERT(is_hashmap(map));
433: 1442: hx = hashmap_make_hash(key);
433: 1443: *res = hashmap_delete(p, hx, key, map);
433: 1444: return 1;
-: 1445:}
-: 1446:
808: 1447:BIF_RETTYPE maps_remove_2(BIF_ALIST_2) {
808: 1448: if (is_map(BIF_ARG_2)) {
-: 1449: Eterm res;
808: 1450: if (erts_maps_remove(BIF_P, BIF_ARG_1, BIF_ARG_2, &res)) {
808: 1451: BIF_RET(res);
-: 1452: }
-: 1453: }
#####: 1454: BIF_ERROR(BIF_P, BADARG);
-: 1455:}
-: 1456:
2324: 1457:int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res) {
-: 1458: Uint32 hx;
2324: 1459: if (is_flatmap(map)) {
-: 1460: Sint n,i;
-: 1461: Eterm* hp,*shp;
-: 1462: Eterm *ks,*vs;
1069: 1463: flatmap_t *mp = (flatmap_t*)flatmap_val(map);
-: 1464:
1069: 1465: if ((n = flatmap_get_size(mp)) == 0) {
91: 1466: return 0;
-: 1467: }
-: 1468:
978: 1469: ks = flatmap_get_keys(mp);
978: 1470: vs = flatmap_get_values(mp);
-: 1471:
-: 1472: /* only allocate for values,
-: 1473: * assume key-tuple will be intact
-: 1474: */
-: 1475:
978: 1476: hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + n);
978: 1477: shp = hp;
978: 1478: *hp++ = MAP_HEADER_FLATMAP;
978: 1479: *hp++ = n;
978: 1480: *hp++ = mp->keys;
-: 1481:
978: 1482: if (is_immed(key)) {
4714: 1483: for( i = 0; i < n; i ++) {
4590: 1484: if (ks[i] == key) {
611: 1485: goto found_key;
-: 1486: } else {
3979: 1487: *hp++ = *vs++;
-: 1488: }
-: 1489: }
-: 1490: } else {
2845: 1491: for( i = 0; i < n; i ++) {
2810: 1492: if (EQ(ks[i], key)) {
-: 1493: goto found_key;
-: 1494: } else {
2602: 1495: *hp++ = *vs++;
-: 1496: }
-: 1497: }
-: 1498: }
-: 1499:
159: 1500: HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
159: 1501: return 0;
-: 1502:
-: 1503:found_key:
819: 1504: *hp++ = value;
819: 1505: vs++;
819: 1506: if (++i < n)
607: 1507: sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
819: 1508: *res = make_flatmap(shp);
819: 1509: return 1;
-: 1510: }
-: 1511:
-: 1512: ASSERT(is_hashmap(map));
1255: 1513: hx = hashmap_make_hash(key);
1255: 1514: *res = erts_hashmap_insert(p, hx, key, value, map, 1);
1255: 1515: if (is_value(*res))
1044: 1516: return 1;
-: 1517:
211: 1518: return 0;
-: 1519:}
-: 1520:
32216: 1521:Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
-: 1522: Uint32 hx;
-: 1523: Eterm res;
32216: 1524: if (is_flatmap(map)) {
-: 1525: Sint n,i;
15909: 1526: Sint c = 0;
-: 1527: Eterm* hp, *shp;
-: 1528: Eterm *ks, *vs, tup;
15909: 1529: flatmap_t *mp = (flatmap_t*)flatmap_val(map);
-: 1530:
15909: 1531: n = flatmap_get_size(mp);
-: 1532:
15909: 1533: if (n == 0) {
550: 1534: hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + 1 + 2);
550: 1535: tup = make_tuple(hp);
550: 1536: *hp++ = make_arityval(1);
550: 1537: *hp++ = key;
550: 1538: res = make_flatmap(hp);
550: 1539: *hp++ = MAP_HEADER_FLATMAP;
550: 1540: *hp++ = 1;
550: 1541: *hp++ = tup;
550: 1542: *hp++ = value;
-: 1543:
550: 1544: return res;
-: 1545: }
-: 1546:
15359: 1547: ks = flatmap_get_keys(mp);
15359: 1548: vs = flatmap_get_values(mp);
-: 1549:
-: 1550: /* only allocate for values,
-: 1551: * assume key-tuple will be intact
-: 1552: */
-: 1553:
15359: 1554: hp = HAlloc(p, MAP_HEADER_FLATMAP_SZ + n);
15359: 1555: shp = hp; /* save hp, used if optimistic update fails */
15359: 1556: res = make_flatmap(hp);
15359: 1557: *hp++ = MAP_HEADER_FLATMAP;
15359: 1558: *hp++ = n;
15359: 1559: *hp++ = mp->keys;
-: 1560:
15359: 1561: if (is_immed(key)) {
173931: 1562: for( i = 0; i < n; i ++) {
161947: 1563: if (ks[i] == key) {
4058: 1564: *hp++ = value;
4058: 1565: vs++;
4058: 1566: c = 1;
-: 1567: } else {
157889: 1568: *hp++ = *vs++;
-: 1569: }
-: 1570: }
-: 1571: } else {
55715: 1572: for( i = 0; i < n; i ++) {
52340: 1573: if (EQ(ks[i], key)) {
13: 1574: *hp++ = value;
13: 1575: vs++;
13: 1576: c = 1;
-: 1577: } else {
52327: 1578: *hp++ = *vs++;
-: 1579: }
-: 1580: }
-: 1581: }
-: 1582:
15359: 1583: if (c)
4071: 1584: return res;
-: 1585:
-: 1586: /* the map will grow */
-: 1587:
11288: 1588: if (n >= MAP_SMALL_MAP_LIMIT) {
267: 1589: HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
267: 1590: ks = flatmap_get_keys(mp);
267: 1591: vs = flatmap_get_values(mp);
-: 1592:
267: 1593: res = erts_hashmap_from_ks_and_vs_extra(p,ks,vs,n,key,value);
-: 1594:
267: 1595: return res;
-: 1596: }
-: 1597:
-: 1598: /* still a small map. need to make a new tuple,
-: 1599: * use old hp since it needs to be recreated anyway. */
-: 1600:
11021: 1601: tup = make_tuple(shp);
11021: 1602: *shp++ = make_arityval(n+1);
-: 1603:
11021: 1604: hp = HAlloc(p, 3 + n + 1);
11021: 1605: res = make_flatmap(hp);
11021: 1606: *hp++ = MAP_HEADER_FLATMAP;
11021: 1607: *hp++ = n + 1;
11021: 1608: *hp++ = tup;
-: 1609:
11021: 1610: ks = flatmap_get_keys(mp);
11021: 1611: vs = flatmap_get_values(mp);
-: 1612:
-: 1613: ASSERT(n >= 0);
-: 1614:
-: 1615: /* copy map in order */
102783: 1616: while (n && ((c = CMP_TERM(*ks, key)) < 0)) {
80741: 1617: *shp++ = *ks++;
80741: 1618: *hp++ = *vs++;
80741: 1619: n--;
-: 1620: }
-: 1621:
11021: 1622: *shp++ = key;
11021: 1623: *hp++ = value;
-: 1624:
-: 1625: ASSERT(n >= 0);
-: 1626:
100320: 1627: while(n--) {
78278: 1628: *shp++ = *ks++;
78278: 1629: *hp++ = *vs++;
-: 1630: }
-: 1631: /* we have one word remaining
-: 1632: * this will work out fine once we get the size word
-: 1633: * in the header.
-: 1634: */
11021: 1635: *shp = make_pos_bignum_header(0);
11021: 1636: return res;
-: 1637: }
-: 1638: ASSERT(is_hashmap(map));
-: 1639:
16307: 1640: hx = hashmap_make_hash(key);
16307: 1641: res = erts_hashmap_insert(p, hx, key, value, map, 0);
-: 1642: ASSERT(is_hashmap(res));
-: 1643:
16307: 1644: return res;
-: 1645:}
-: 1646:
-: 1647:/* maps:update/3 */
-: 1648:
2324: 1649:BIF_RETTYPE maps_update_3(BIF_ALIST_3) {
2324: 1650: if (is_map(BIF_ARG_3)) {
-: 1651: Eterm res;
2324: 1652: if (erts_maps_update(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, &res)) {
1863: 1653: BIF_RET(res);
-: 1654: }
-: 1655: }
461: 1656: BIF_ERROR(BIF_P, BADARG);
-: 1657:}
-: 1658:
-: 1659:
-: 1660:/* maps:values/1 */
-: 1661:
1151: 1662:BIF_RETTYPE maps_values_1(BIF_ALIST_1) {
1151: 1663: if (is_flatmap(BIF_ARG_1)) {
546: 1664: Eterm *hp, *vs, res = NIL;
-: 1665: flatmap_t *mp;
-: 1666: Uint n;
-: 1667:
546: 1668: mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
546: 1669: n = flatmap_get_size(mp);
-: 1670:
546: 1671: if (n == 0)
45: 1672: BIF_RET(res);
-: 1673:
501: 1674: hp = HAlloc(BIF_P, (2 * n));
501: 1675: vs = flatmap_get_values(mp);
-: 1676:
6607: 1677: while(n--) {
5605: 1678: res = CONS(hp, vs[n], res); hp += 2;
-: 1679: }
-: 1680:
501: 1681: BIF_RET(res);
605: 1682: } else if (is_hashmap(BIF_ARG_1)) {
605: 1683: BIF_RET(hashmap_values(BIF_P, BIF_ARG_1));
-: 1684: }
#####: 1685: BIF_ERROR(BIF_P, BADARG);
-: 1686:}
-: 1687:
2018: 1688:static Eterm hashmap_to_list(Process *p, Eterm node) {
2018: 1689: DECLARE_WSTACK(stack);
-: 1690: Eterm *hp, *kv;
2018: 1691: Eterm res = NIL;
-: 1692:
2018: 1693: hp = HAlloc(p, hashmap_size(node) * (2 + 3));
2018: 1694: hashmap_iterator_init(&stack, node, 0);
159369: 1695: while ((kv=hashmap_iterator_next(&stack)) != NULL) {
155333: 1696: Eterm tup = TUPLE2(hp, CAR(kv), CDR(kv));
155333: 1697: hp += 3;
155333: 1698: res = CONS(hp, tup, res);
155333: 1699: hp += 2;
-: 1700: }
2018: 1701: DESTROY_WSTACK(stack);
2018: 1702: return res;
-: 1703:}
-: 1704:
3258: 1705:void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) {
3258: 1706: Eterm hdr = *hashmap_val(node);
-: 1707: Uint sz;
-: 1708:
3258: 1709: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 1710: case HAMT_SUBTAG_HEAD_ARRAY:
2218: 1711: sz = 16;
2218: 1712: break;
-: 1713: case HAMT_SUBTAG_HEAD_BITMAP:
1040: 1714: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
1040: 1715: break;
-: 1716: default:
#####: 1717: erl_exit(1, "bad header");
-: 1718: }
-: 1719:
3258: 1720: WSTACK_PUSH3((*s), (UWord)THE_NON_VALUE, /* end marker */
-: 1721: (UWord)(!reverse ? 0 : sz+1),
-: 1722: (UWord)node);
3258: 1723:}
-: 1724:
512497: 1725:Eterm* hashmap_iterator_next(ErtsWStack* s) {
-: 1726: Eterm node, *ptr, hdr;
-: 1727: Uint32 sz;
-: 1728: Uint idx;
-: 1729:
-: 1730: for (;;) {
-: 1731: ASSERT(!WSTACK_ISEMPTY((*s)));
512497: 1732: node = (Eterm) WSTACK_POP((*s));
512497: 1733: if (is_non_value(node)) {
3258: 1734: return NULL;
-: 1735: }
509239: 1736: idx = (Uint) WSTACK_POP((*s));
-: 1737: for (;;) {
-: 1738: ASSERT(is_boxed(node));
765740: 1739: ptr = boxed_val(node);
765740: 1740: hdr = *ptr;
-: 1741: ASSERT(is_header(hdr));
765740: 1742: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 1743: case HAMT_SUBTAG_HEAD_ARRAY:
37706: 1744: ptr++;
37706: 1745: sz = 16;
37706: 1746: break;
-: 1747: case HAMT_SUBTAG_HEAD_BITMAP:
15805: 1748: ptr++;
-: 1749: case HAMT_SUBTAG_NODE_BITMAP:
728034: 1750: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-: 1751: ASSERT(sz < 17);
728034: 1752: break;
-: 1753: default:
#####: 1754: erl_exit(1, "bad header");
-: 1755: }
-: 1756:
765740: 1757: idx++;
-: 1758:
765740: 1759: if (idx <= sz) {
505981: 1760: WSTACK_PUSH2((*s), (UWord)idx, (UWord)node);
-: 1761:
505981: 1762: if (is_list(ptr[idx])) {
249480: 1763: return list_val(ptr[idx]);
-: 1764: }
-: 1765: ASSERT(is_boxed(ptr[idx]));
256501: 1766: node = ptr[idx];
256501: 1767: idx = 0;
-: 1768: }
-: 1769: else
259759: 1770: break; /* and pop parent node */
256501: 1771: }
259759: 1772: }
-: 1773:}
-: 1774:
#####: 1775:Eterm* hashmap_iterator_prev(ErtsWStack* s) {
-: 1776: Eterm node, *ptr, hdr;
-: 1777: Uint32 sz;
-: 1778: Uint idx;
-: 1779:
-: 1780: for (;;) {
-: 1781: ASSERT(!WSTACK_ISEMPTY((*s)));
#####: 1782: node = (Eterm) WSTACK_POP((*s));
#####: 1783: if (is_non_value(node)) {
#####: 1784: return NULL;
-: 1785: }
#####: 1786: idx = (Uint) WSTACK_POP((*s));
-: 1787: for (;;) {
-: 1788: ASSERT(is_boxed(node));
#####: 1789: ptr = boxed_val(node);
#####: 1790: hdr = *ptr;
-: 1791: ASSERT(is_header(hdr));
#####: 1792: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 1793: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 1794: ptr++;
#####: 1795: sz = 16;
#####: 1796: break;
-: 1797: case HAMT_SUBTAG_HEAD_BITMAP:
#####: 1798: ptr++;
-: 1799: case HAMT_SUBTAG_NODE_BITMAP:
#####: 1800: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-: 1801: ASSERT(sz < 17);
#####: 1802: break;
-: 1803: default:
#####: 1804: erl_exit(1, "bad header");
-: 1805: }
-: 1806:
#####: 1807: if (idx > sz)
#####: 1808: idx = sz;
-: 1809: else
#####: 1810: idx--;
-: 1811:
#####: 1812: if (idx >= 1) {
#####: 1813: WSTACK_PUSH2((*s), (UWord)idx, (UWord)node);
-: 1814:
#####: 1815: if (is_list(ptr[idx])) {
#####: 1816: return list_val(ptr[idx]);
-: 1817: }
-: 1818: ASSERT(is_boxed(ptr[idx]));
#####: 1819: node = ptr[idx];
#####: 1820: idx = 17;
-: 1821: }
-: 1822: else
#####: 1823: break; /* and pop parent node */
#####: 1824: }
#####: 1825: }
-: 1826:}
-: 1827:
-: 1828:const Eterm *
-: 1829:#if HALFWORD_HEAP
-: 1830:erts_hashmap_get_rel(Uint32 hx, Eterm key, Eterm node, Eterm *map_base)
-: 1831:#else
2602: 1832:erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
-: 1833:#endif
-: 1834:{
-: 1835: Eterm *ptr, hdr, *res;
2602: 1836: Uint ix, lvl = 0;
-: 1837: Uint32 hval,bp;
-: 1838: DeclareTmpHeapNoproc(th,2);
-: 1839: UseTmpHeapNoproc(2);
-: 1840:
-: 1841: ASSERT(is_boxed(node));
2602: 1842: ptr = boxed_val(node);
2602: 1843: hdr = *ptr;
-: 1844: ASSERT(is_header(hdr));
-: 1845: ASSERT(is_hashmap_header_head(hdr));
2602: 1846: ptr++;
-: 1847:
-: 1848: for (;;) {
8837: 1849: hval = MAP_HEADER_VAL(hdr);
8837: 1850: ix = hashmap_index(hx);
8837: 1851: if (hval != 0xffff) {
7082: 1852: bp = 1 << ix;
7082: 1853: if (!(bp & hval)) {
-: 1854: /* not occupied */
200: 1855: res = NULL;
200: 1856: break;
-: 1857: }
6882: 1858: ix = hashmap_bitcount(hval & (bp - 1));
-: 1859: }
8637: 1860: node = ptr[ix+1];
-: 1861:
8637: 1862: if (is_list(node)) { /* LEAF NODE [K|V] */
2402: 1863: ptr = list_val(node);
-: 1864:
2402: 1865: res = eq_rel(CAR(ptr), map_base, key, NULL) ? &(CDR(ptr)) : NULL;
2402: 1866: break;
-: 1867: }
-: 1868:
6235: 1869: hx = hashmap_shift_hash(th,hx,lvl,key);
-: 1870:
-: 1871: ASSERT(is_boxed(node));
6235: 1872: ptr = boxed_val(node);
6235: 1873: hdr = *ptr;
-: 1874: ASSERT(is_header(hdr));
-: 1875: ASSERT(!is_hashmap_header_head(hdr));
6235: 1876: }
-: 1877:
-: 1878: UnUseTmpHeapNoproc(2);
2602: 1879: return res;
-: 1880:}
-: 1881:
17562: 1882:Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,
-: 1883: Eterm map, int is_update) {
-: 1884: Uint size, upsz;
17562: 1885: Eterm *hp, res = THE_NON_VALUE;
17562: 1886: DECLARE_ESTACK(stack);
17562: 1887: if (erts_hashmap_insert_down(hx, key, map, &size, &upsz, &stack, is_update)) {
17351: 1888: hp = HAlloc(p, size);
17351: 1889: res = erts_hashmap_insert_up(hp, key, value, &upsz, &stack);
-: 1890: }
-: 1891:
17562: 1892: DESTROY_ESTACK(stack);
-: 1893: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 1894: ERTS_HOLE_CHECK(p);
-: 1895:
17562: 1896: return res;
-: 1897:}
-: 1898:
-: 1899:
17562: 1900:int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
-: 1901: Uint *update_size, ErtsEStack *sp, int is_update) {
-: 1902: Eterm *ptr;
-: 1903: Eterm hdr, ckey;
-: 1904: Eterm th[2];
-: 1905: Uint32 ix, cix, bp, hval, chx;
17562: 1906: Uint slot, lvl = 0, clvl;
17562: 1907: Uint size = 0, n = 0;
-: 1908:
17562: 1909: *update_size = 1;
-: 1910:
-: 1911: for (;;) {
70165: 1912: switch(primary_tag(node)) {
-: 1913: case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
10777: 1914: ptr = list_val(node);
10777: 1915: ckey = CAR(ptr);
10777: 1916: if (EQ(ckey, key)) {
6748: 1917: *update_size = 0;
6748: 1918: goto unroll;
-: 1919: }
4029: 1920: if (is_update) {
104: 1921: return 0;
-: 1922: }
3925: 1923: goto insert_subnodes;
-: 1924: case TAG_PRIMARY_BOXED:
59388: 1925: ptr = boxed_val(node);
59388: 1926: hdr = *ptr;
-: 1927: ASSERT(is_header(hdr));
-: 1928:
59388: 1929: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 1930: case HAMT_SUBTAG_HEAD_ARRAY:
10187: 1931: ix = hashmap_index(hx);
10187: 1932: hx = hashmap_shift_hash(th,hx,lvl,key);
10187: 1933: size += HAMT_HEAD_ARRAY_SZ;
10187: 1934: ESTACK_PUSH2(*sp, ix, node);
10187: 1935: node = ptr[ix+2];
10187: 1936: break;
-: 1937: case HAMT_SUBTAG_NODE_BITMAP:
41826: 1938: hval = MAP_HEADER_VAL(hdr);
41826: 1939: ix = hashmap_index(hx);
41826: 1940: bp = 1 << ix;
41826: 1941: slot = hashmap_bitcount(hval & (bp - 1));
41826: 1942: n = hashmap_bitcount(hval);
-: 1943:
41826: 1944: ESTACK_PUSH4(*sp, n, bp, slot, node);
-: 1945:
-: 1946: /* occupied */
41826: 1947: if (bp & hval) {
35476: 1948: hx = hashmap_shift_hash(th,hx,lvl,key);
35476: 1949: node = ptr[slot+1];
-: 1950: ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17);
35476: 1951: size += HAMT_NODE_BITMAP_SZ(n);
35476: 1952: break;
-: 1953: }
-: 1954: /* not occupied */
6350: 1955: if (is_update) {
102: 1956: return 0;
-: 1957: }
6248: 1958: size += HAMT_NODE_BITMAP_SZ(n+1);
6248: 1959: goto unroll;
-: 1960: case HAMT_SUBTAG_HEAD_BITMAP:
7375: 1961: hval = MAP_HEADER_VAL(hdr);
7375: 1962: ix = hashmap_index(hx);
7375: 1963: bp = 1 << ix;
7375: 1964: slot = hashmap_bitcount(hval & (bp - 1));
7375: 1965: n = hashmap_bitcount(hval);
-: 1966:
7375: 1967: ESTACK_PUSH4(*sp, n, bp, slot, node);
-: 1968:
-: 1969: /* occupied */
7375: 1970: if (bp & hval) {
6940: 1971: hx = hashmap_shift_hash(th,hx,lvl,key);
6940: 1972: node = ptr[slot+2];
-: 1973: ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18);
6940: 1974: size += HAMT_HEAD_BITMAP_SZ(n);
6940: 1975: break;
-: 1976: }
-: 1977: /* not occupied */
435: 1978: if (is_update) {
5: 1979: return 0;
-: 1980: }
430: 1981: size += HAMT_HEAD_BITMAP_SZ(n+1);
430: 1982: goto unroll;
-: 1983: default:
#####: 1984: erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-: 1985: break;
-: 1986: }
52603: 1987: break;
-: 1988: default:
#####: 1989: erl_exit(1, "bad primary tag %p\r\n", node);
-: 1990: break;
-: 1991: }
52603: 1992: }
-: 1993:insert_subnodes:
3925: 1994: clvl = lvl;
3925: 1995: chx = hashmap_restore_hash(th,clvl,ckey);
3925: 1996: size += HAMT_NODE_BITMAP_SZ(2);
3925: 1997: ix = hashmap_index(hx);
3925: 1998: cix = hashmap_index(chx);
-: 1999:
16889: 2000: while (cix == ix) {
9039: 2001: ESTACK_PUSH4(*sp, 0, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0));
9039: 2002: size += HAMT_NODE_BITMAP_SZ(1);
9039: 2003: hx = hashmap_shift_hash(th,hx,lvl,key);
9039: 2004: chx = hashmap_shift_hash(th,chx,clvl,ckey);
9039: 2005: ix = hashmap_index(hx);
9039: 2006: cix = hashmap_index(chx);
-: 2007: }
3925: 2008: ESTACK_PUSH3(*sp, cix, ix, node);
-: 2009:
-: 2010:unroll:
17351: 2011: *sz = size + /* res cons */ 2;
17351: 2012: return 1;
-: 2013:}
-: 2014:
17351: 2015:Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
-: 2016: Uint *update_size, ErtsEStack *sp) {
-: 2017: Eterm node, *ptr, hdr;
-: 2018: Eterm res;
17351: 2019: Eterm *nhp = NULL;
-: 2020: Uint32 ix, cix, bp, hval;
-: 2021: Uint slot, n;
-: 2022: /* Needed for halfword */
-: 2023: DeclareTmpHeapNoproc(fake,1);
-: 2024: UseTmpHeapNoproc(1);
-: 2025:
17351: 2026: res = CONS(hp, key, value); hp += 2;
-: 2027:
-: 2028: do {
71928: 2029: node = ESTACK_POP(*sp);
71928: 2030: switch(primary_tag(node)) {
-: 2031: case TAG_PRIMARY_LIST:
3925: 2032: ix = (Uint32) ESTACK_POP(*sp);
3925: 2033: cix = (Uint32) ESTACK_POP(*sp);
-: 2034:
3925: 2035: nhp = hp;
3925: 2036: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix));
3925: 2037: if (ix < cix) {
1952: 2038: *hp++ = res;
1952: 2039: *hp++ = node;
-: 2040: } else {
1973: 2041: *hp++ = node;
1973: 2042: *hp++ = res;
-: 2043: }
3925: 2044: res = make_hashmap(nhp);
3925: 2045: break;
-: 2046: case TAG_PRIMARY_HEADER:
-: 2047: /* subnodes, fake it */
9039: 2048: *fake = node;
9039: 2049: node = make_boxed(fake);
-: 2050: case TAG_PRIMARY_BOXED:
68003: 2051: ptr = boxed_val(node);
68003: 2052: hdr = *ptr;
-: 2053: ASSERT(is_header(hdr));
-: 2054:
68003: 2055: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2056: case HAMT_SUBTAG_HEAD_ARRAY:
10048: 2057: slot = (Uint) ESTACK_POP(*sp);
10048: 2058: nhp = hp;
10048: 2059: n = HAMT_HEAD_ARRAY_SZ - 2;
10048: 2060: *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
10048: 2061: *hp++ = (*ptr++) + *update_size;
10048: 2062: while(n--) { *hp++ = *ptr++; }
10048: 2063: nhp[slot+2] = res;
10048: 2064: res = make_hashmap(nhp);
10048: 2065: break;
-: 2066: case HAMT_SUBTAG_NODE_BITMAP:
50652: 2067: slot = (Uint) ESTACK_POP(*sp);
50652: 2068: bp = (Uint32) ESTACK_POP(*sp);
50652: 2069: n = (Uint32) ESTACK_POP(*sp);
50652: 2070: hval = MAP_HEADER_VAL(hdr);
50652: 2071: nhp = hp;
50652: 2072: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++;
-: 2073:
50652: 2074: n -= slot;
50652: 2075: while(slot--) { *hp++ = *ptr++; }
50652: 2076: *hp++ = res;
50652: 2077: if (hval & bp) { ptr++; n--; }
50652: 2078: while(n--) { *hp++ = *ptr++; }
-: 2079:
50652: 2080: res = make_hashmap(nhp);
50652: 2081: break;
-: 2082: case HAMT_SUBTAG_HEAD_BITMAP:
7303: 2083: slot = (Uint) ESTACK_POP(*sp);
7303: 2084: bp = (Uint32) ESTACK_POP(*sp);
7303: 2085: n = (Uint32) ESTACK_POP(*sp);
7303: 2086: hval = MAP_HEADER_VAL(hdr);
7303: 2087: nhp = hp;
7303: 2088: *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++;
7303: 2089: *hp++ = (*ptr++) + *update_size;
-: 2090:
7303: 2091: n -= slot;
7303: 2092: while(slot--) { *hp++ = *ptr++; }
7303: 2093: *hp++ = res;
7303: 2094: if (hval & bp) { ptr++; n--; }
7303: 2095: while(n--) { *hp++ = *ptr++; }
-: 2096:
7303: 2097: if ((hval | bp) == 0xffff) {
155: 2098: *nhp = MAP_HEADER_HAMT_HEAD_ARRAY;
-: 2099: }
7303: 2100: res = make_hashmap(nhp);
7303: 2101: break;
-: 2102: default:
#####: 2103: erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-: 2104: break;
-: 2105: }
68003: 2106: break;
-: 2107: default:
#####: 2108: erl_exit(1, "bad primary tag %x\r\n", primary_tag(node));
-: 2109: break;
-: 2110: }
-: 2111:
71928: 2112: } while(!ESTACK_ISEMPTY(*sp));
-: 2113:
-: 2114: UnUseTmpHeapNoproc(1);
17351: 2115: return res;
-: 2116:}
-: 2117:
609: 2118:static Eterm hashmap_keys(Process* p, Eterm node) {
609: 2119: DECLARE_WSTACK(stack);
-: 2120: hashmap_head_t* root;
-: 2121: Eterm *hp, *kv;
609: 2122: Eterm res = NIL;
-: 2123:
609: 2124: root = (hashmap_head_t*) boxed_val(node);
609: 2125: hp = HAlloc(p, root->size * 2);
609: 2126: hashmap_iterator_init(&stack, node, 0);
49154: 2127: while ((kv=hashmap_iterator_next(&stack)) != NULL) {
47936: 2128: res = CONS(hp, CAR(kv), res);
47936: 2129: hp += 2;
-: 2130: }
609: 2131: DESTROY_WSTACK(stack);
609: 2132: return res;
-: 2133:}
-: 2134:
605: 2135:static Eterm hashmap_values(Process* p, Eterm node) {
605: 2136: DECLARE_WSTACK(stack);
-: 2137: hashmap_head_t* root;
-: 2138: Eterm *hp, *kv;
605: 2139: Eterm res = NIL;
-: 2140:
605: 2141: root = (hashmap_head_t*) boxed_val(node);
605: 2142: hp = HAlloc(p, root->size * 2);
605: 2143: hashmap_iterator_init(&stack, node, 0);
46649: 2144: while ((kv=hashmap_iterator_next(&stack)) != NULL) {
45439: 2145: res = CONS(hp, CDR(kv), res);
45439: 2146: hp += 2;
-: 2147: }
605: 2148: DESTROY_WSTACK(stack);
605: 2149: return res;
-: 2150:}
-: 2151:
433: 2152:static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm map) {
433: 2153: Eterm *hp = NULL, *nhp = NULL, *hp_end = NULL;
-: 2154: Eterm th[2];
-: 2155: Eterm *ptr;
433: 2156: Eterm hdr, res = map, node = map;
-: 2157: Uint32 ix, bp, hval;
433: 2158: Uint slot, lvl = 0;
433: 2159: Uint size = 0, n = 0;
433: 2160: DECLARE_ESTACK(stack);
-: 2161:
-: 2162: for (;;) {
1858: 2163: switch(primary_tag(node)) {
-: 2164: case TAG_PRIMARY_LIST:
399: 2165: if (EQ(CAR(list_val(node)), key)) {
-: 2166: goto unroll;
-: 2167: }
44: 2168: goto not_found;
-: 2169: case TAG_PRIMARY_BOXED:
1459: 2170: ptr = boxed_val(node);
1459: 2171: hdr = *ptr;
-: 2172: ASSERT(is_header(hdr));
-: 2173:
1459: 2174: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2175: case HAMT_SUBTAG_HEAD_ARRAY:
284: 2176: ix = hashmap_index(hx);
284: 2177: hx = hashmap_shift_hash(th,hx,lvl,key);
284: 2178: size += HAMT_HEAD_ARRAY_SZ;
284: 2179: ESTACK_PUSH2(stack, ix, node);
284: 2180: node = ptr[ix+2];
284: 2181: break;
-: 2182: case HAMT_SUBTAG_NODE_BITMAP:
1026: 2183: hval = MAP_HEADER_VAL(hdr);
1026: 2184: ix = hashmap_index(hx);
1026: 2185: bp = 1 << ix;
1026: 2186: slot = hashmap_bitcount(hval & (bp - 1));
1026: 2187: n = hashmap_bitcount(hval);
-: 2188:
1026: 2189: ESTACK_PUSH4(stack, n, bp, slot, node);
-: 2190:
-: 2191: /* occupied */
1026: 2192: if (bp & hval) {
993: 2193: hx = hashmap_shift_hash(th,hx,lvl,key);
993: 2194: node = ptr[slot+1];
-: 2195: ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17);
993: 2196: size += HAMT_NODE_BITMAP_SZ(n);
993: 2197: break;
-: 2198: }
-: 2199: /* not occupied */
33: 2200: goto not_found;
-: 2201: case HAMT_SUBTAG_HEAD_BITMAP:
149: 2202: hval = MAP_HEADER_VAL(hdr);
149: 2203: ix = hashmap_index(hx);
149: 2204: bp = 1 << ix;
149: 2205: slot = hashmap_bitcount(hval & (bp - 1));
149: 2206: n = hashmap_bitcount(hval);
-: 2207:
149: 2208: ESTACK_PUSH4(stack, n, bp, slot, node);
-: 2209:
-: 2210: /* occupied */
149: 2211: if (bp & hval) {
148: 2212: hx = hashmap_shift_hash(th,hx,lvl,key);
148: 2213: node = ptr[slot+2];
-: 2214: ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18);
148: 2215: size += HAMT_HEAD_BITMAP_SZ(n);
148: 2216: break;
-: 2217: }
-: 2218: /* not occupied */
1: 2219: goto not_found;
-: 2220: default:
#####: 2221: erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-: 2222: break;
-: 2223: }
1425: 2224: break;
-: 2225: default:
#####: 2226: erl_exit(1, "bad primary tag %p\r\n", node);
-: 2227: break;
-: 2228: }
1425: 2229: }
-: 2230:
-: 2231:unroll:
-: 2232: /* the size is bounded and atleast one less than the previous size */
355: 2233: size -= 1;
355: 2234: n = hashmap_size(map) - 1;
-: 2235:
355: 2236: if (n <= MAP_SMALL_MAP_LIMIT) {
6: 2237: DECLARE_WSTACK(wstack);
-: 2238: Eterm *kv, *ks, *vs;
-: 2239: flatmap_t *mp;
-: 2240: Eterm keys;
-: 2241:
6: 2242: DESTROY_ESTACK(stack);
-: 2243:
-: 2244: /* build flat structure */
6: 2245: hp = HAlloc(p, 3 + 1 + (2 * n));
6: 2246: keys = make_tuple(hp);
6: 2247: *hp++ = make_arityval(n);
6: 2248: ks = hp;
6: 2249: hp += n;
6: 2250: mp = (flatmap_t*)hp;
6: 2251: hp += MAP_HEADER_FLATMAP_SZ;
6: 2252: vs = hp;
-: 2253:
6: 2254: mp->thing_word = MAP_HEADER_FLATMAP;
6: 2255: mp->size = n;
6: 2256: mp->keys = keys;
-: 2257:
6: 2258: hashmap_iterator_init(&wstack, map, 0);
-: 2259:
210: 2260: while ((kv=hashmap_iterator_next(&wstack)) != NULL) {
198: 2261: if (EQ(CAR(kv),key))
6: 2262: continue;
192: 2263: *ks++ = CAR(kv);
192: 2264: *vs++ = CDR(kv);
-: 2265: }
-: 2266:
-: 2267: /* it cannot have multiple keys */
6: 2268: erts_validate_and_sort_flatmap(mp);
-: 2269:
6: 2270: DESTROY_WSTACK(wstack);
6: 2271: return make_flatmap(mp);
-: 2272: }
-: 2273:
349: 2274: hp = HAlloc(p, size);
349: 2275: hp_end = hp + size;
349: 2276: res = THE_NON_VALUE;
-: 2277:
-: 2278: do {
1278: 2279: node = ESTACK_POP(stack);
-: 2280:
-: 2281: /* all nodes are things */
1278: 2282: ptr = boxed_val(node);
1278: 2283: hdr = *ptr;
-: 2284: ASSERT(is_header(hdr));
-: 2285:
1278: 2286: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2287: case HAMT_SUBTAG_HEAD_ARRAY:
233: 2288: ix = (Uint) ESTACK_POP(stack);
233: 2289: nhp = hp;
233: 2290: if (res == THE_NON_VALUE) {
2: 2291: n = 16;
2: 2292: n -= ix;
2: 2293: *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(0xffff ^ (1 << ix)); ptr++;
2: 2294: *hp++ = (*ptr++) - 1;
2: 2295: while(ix--) { *hp++ = *ptr++; }
2: 2296: ptr++; n--;
2: 2297: while(n--) { *hp++ = *ptr++; }
2: 2298: res = make_hashmap(nhp);
-: 2299: } else {
231: 2300: n = 16;
231: 2301: *hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
231: 2302: *hp++ = (*ptr++) - 1;
231: 2303: while(n--) { *hp++ = *ptr++; }
231: 2304: nhp[ix+2] = res;
231: 2305: res = make_hashmap(nhp);
-: 2306: }
233: 2307: break;
-: 2308: case HAMT_SUBTAG_NODE_BITMAP:
929: 2309: slot = (Uint) ESTACK_POP(stack);
929: 2310: bp = (Uint32) ESTACK_POP(stack);
929: 2311: n = (Uint32) ESTACK_POP(stack);
929: 2312: nhp = hp;
-: 2313:
-: 2314: /* bitmap change matrix
-: 2315: * res | none leaf bitmap
-: 2316: * ----------------------------
-: 2317: * n=1 | remove remove keep
-: 2318: * n=2 | other keep keep
-: 2319: * n>2 | shrink keep keep
-: 2320: *
-: 2321: * other: (remember, n is 2)
-: 2322: * shrink if the other bitmap value is a bitmap node
-: 2323: * remove if the other bitmap value is a leaf
-: 2324: *
-: 2325: * remove:
-: 2326: * this bitmap node is removed, res is moved up in tree (could be none)
-: 2327: * this is a special case of shrink
-: 2328: *
-: 2329: * keep:
-: 2330: * the current path index is still used down in the tree, need to keep it
-: 2331: * copy as usual with the updated res
-: 2332: *
-: 2333: * shrink:
-: 2334: * the current path index is no longer used down in the tree, remove it (shrink)
-: 2335: */
929: 2336: if (res == THE_NON_VALUE) {
336: 2337: if (n == 1) {
#####: 2338: break;
336: 2339: } else if (n == 2) {
158: 2340: if (slot == 0) {
73: 2341: ix = 2; /* off by one 'cause hdr */
-: 2342: } else {
85: 2343: ix = 1; /* off by one 'cause hdr */
-: 2344: }
158: 2345: if (primary_tag(ptr[ix]) == TAG_PRIMARY_LIST) {
142: 2346: res = ptr[ix];
-: 2347: } else {
16: 2348: hval = MAP_HEADER_VAL(hdr);
16: 2349: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp);
16: 2350: *hp++ = ptr[ix];
16: 2351: res = make_hashmap(nhp);
-: 2352: }
-: 2353: } else {
-: 2354: /* n > 2 */
178: 2355: hval = MAP_HEADER_VAL(hdr);
178: 2356: *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval ^ bp); ptr++;
178: 2357: n -= slot;
178: 2358: while(slot--) { *hp++ = *ptr++; }
178: 2359: ptr++; n--;
178: 2360: while(n--) { *hp++ = *ptr++; }
178: 2361: res = make_hashmap(nhp);
-: 2362: }
593: 2363: } else if (primary_tag(res) == TAG_PRIMARY_LIST && n == 1) {
-: 2364: break;
-: 2365: } else {
-: 2366: /* res is bitmap or leaf && n > 1, keep */
155: 2367: n -= slot;
155: 2368: *hp++ = *ptr++;
155: 2369: while(slot--) { *hp++ = *ptr++; }
155: 2370: *hp++ = res;
155: 2371: ptr++; n--;
155: 2372: while(n--) { *hp++ = *ptr++; }
155: 2373: res = make_hashmap(nhp);
-: 2374: }
491: 2375: break;
-: 2376: case HAMT_SUBTAG_HEAD_BITMAP:
116: 2377: slot = (Uint) ESTACK_POP(stack);
116: 2378: bp = (Uint32) ESTACK_POP(stack);
116: 2379: n = (Uint32) ESTACK_POP(stack);
116: 2380: nhp = hp;
-: 2381:
116: 2382: if (res != THE_NON_VALUE) {
105: 2383: *hp++ = *ptr++;
105: 2384: *hp++ = (*ptr++) - 1;
105: 2385: n -= slot;
105: 2386: while(slot--) { *hp++ = *ptr++; }
105: 2387: *hp++ = res;
105: 2388: ptr++; n--;
105: 2389: while(n--) { *hp++ = *ptr++; }
-: 2390: } else {
11: 2391: hval = MAP_HEADER_VAL(hdr);
11: 2392: *hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval ^ bp); ptr++;
11: 2393: *hp++ = (*ptr++) - 1;
11: 2394: n -= slot;
11: 2395: while(slot--) { *hp++ = *ptr++; }
11: 2396: ptr++; n--;
11: 2397: while(n--) { *hp++ = *ptr++; }
-: 2398: }
116: 2399: res = make_hashmap(nhp);
116: 2400: break;
-: 2401: default:
#####: 2402: erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
-: 2403: break;
-: 2404: }
1278: 2405: } while(!ESTACK_ISEMPTY(stack));
349: 2406: HRelease(p, hp_end, hp);
-: 2407:not_found:
427: 2408: DESTROY_ESTACK(stack);
-: 2409: ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-: 2410: ERTS_HOLE_CHECK(p);
427: 2411: return res;
-: 2412:}
-: 2413:
-: 2414:
49: 2415:int erts_validate_and_sort_flatmap(flatmap_t* mp)
-: 2416:{
49: 2417: Eterm *ks = flatmap_get_keys(mp);
49: 2418: Eterm *vs = flatmap_get_values(mp);
49: 2419: Uint sz = flatmap_get_size(mp);
-: 2420: Uint ix,jx;
-: 2421: Eterm tmp;
-: 2422: Sint c;
-: 2423:
-: 2424: /* sort */
-: 2425:
801: 2426: for (ix = 1; ix < sz; ix++) {
752: 2427: jx = ix;
6797: 2428: while( jx > 0 && (c = CMP_TERM(ks[jx],ks[jx-1])) <= 0 ) {
-: 2429: /* identical key -> error */
5293: 2430: if (c == 0) return 0;
-: 2431:
5293: 2432: tmp = ks[jx];
5293: 2433: ks[jx] = ks[jx - 1];
5293: 2434: ks[jx - 1] = tmp;
-: 2435:
5293: 2436: tmp = vs[jx];
5293: 2437: vs[jx] = vs[jx - 1];
5293: 2438: vs[jx - 1] = tmp;
-: 2439:
5293: 2440: jx--;
-: 2441: }
-: 2442: }
49: 2443: return 1;
-: 2444:}
-: 2445:
-: 2446:/* Really rough estimate of sqrt(x)
-: 2447: * Guaranteed not to be less than sqrt(x)
-: 2448: */
#####: 2449:static int int_sqrt_ceiling(Uint x)
-: 2450:{
-: 2451: int n;
-: 2452:
#####: 2453: if (x <= 2)
#####: 2454: return x;
-: 2455:
#####: 2456: n = erts_fit_in_bits_uint(x-1);
#####: 2457: if (n & 1) {
-: 2458: /* Calc: sqrt(2^n) = 2^(n/2) * sqrt(2) ~= 2^(n/2) * 3 / 2 */
#####: 2459: return (1 << (n/2 - 1)) * 3;
-: 2460: }
-: 2461: else {
-: 2462: /* Calc: sqrt(2^n) = 2^(n/2) */
#####: 2463: return 1 << (n / 2);
-: 2464: }
-: 2465:}
-: 2466:
#####: 2467:Uint hashmap_over_estimated_heap_size(Uint k)
-: 2468:{
-: 2469: /* k is nr of key-value pairs.
-: 2470: N(k) is expected nr of nodes in hamt.
-: 2471:
-: 2472: Observation:
-: 2473: For uniformly distributed hash values, average of N varies between
-: 2474: 0.3*k and 0.4*k (with a beautiful sine curve)
-: 2475: and standard deviation of N is about sqrt(k)/3.
-: 2476:
-: 2477: Assuming normal probability distribution, we overestimate nr of nodes
-: 2478: by 15 std.devs above the average, which gives a probability for overrun
-: 2479: less than 1.0e-49 (same magnitude as a git SHA1 collision).
-: 2480: */
#####: 2481: Uint max_nodes = 2*k/5 + (15/3)*int_sqrt_ceiling(k);
#####: 2482: return (k*2 + /* leaf cons cells */
-: 2483: k + /* leaf list terms */
#####: 2484: max_nodes*2); /* headers + parent boxed terms */
-: 2485:}
-: 2486:
-: 2487:
#####: 2488:BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) {
#####: 2489: if (is_hashmap(BIF_ARG_1)) {
#####: 2490: BIF_RET(hashmap_info(BIF_P,BIF_ARG_1));
-: 2491: }
#####: 2492: BIF_ERROR(BIF_P, BADARG);
-: 2493:}
-: 2494:
-: 2495:/*
-: 2496: * erts_internal:map_to_tuple_keys/1
-: 2497: *
-: 2498: * Used in erts_debug:size/1
-: 2499: */
-: 2500:
#####: 2501:BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) {
#####: 2502: if (is_flatmap(BIF_ARG_1)) {
#####: 2503: flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
#####: 2504: BIF_RET(mp->keys);
-: 2505: }
#####: 2506: BIF_ERROR(BIF_P, BADARG);
-: 2507:}
-: 2508:
-: 2509:/*
-: 2510: * erts_internal:map_type/1
-: 2511: *
-: 2512: * Used in erts_debug:size/1
-: 2513: */
-: 2514:
#####: 2515:BIF_RETTYPE erts_internal_map_type_1(BIF_ALIST_1) {
#####: 2516: DECL_AM(hashmap);
#####: 2517: DECL_AM(hashmap_node);
#####: 2518: DECL_AM(flatmap);
#####: 2519: if (is_flatmap(BIF_ARG_1)) {
#####: 2520: BIF_RET(AM_flatmap);
#####: 2521: } else if (is_hashmap(BIF_ARG_1)) {
#####: 2522: Eterm hdr = *(boxed_val(BIF_ARG_1));
-: 2523: ASSERT(is_header(hdr));
#####: 2524: switch (hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2525: case HAMT_SUBTAG_HEAD_ARRAY:
-: 2526: case HAMT_SUBTAG_HEAD_BITMAP:
#####: 2527: BIF_RET(AM_hashmap);
-: 2528: case HAMT_SUBTAG_NODE_BITMAP:
#####: 2529: BIF_RET(AM_hashmap_node);
-: 2530: default:
#####: 2531: erl_exit(1, "bad header");
-: 2532: }
-: 2533: }
#####: 2534: BIF_ERROR(BIF_P, BADARG);
-: 2535:}
-: 2536:
-: 2537:/*
-: 2538: * erts_internal:map_hashmap_children/1
-: 2539: *
-: 2540: * Used in erts_debug:size/1
-: 2541: */
-: 2542:
#####: 2543:BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) {
#####: 2544: if (is_hashmap(BIF_ARG_1)) {
#####: 2545: Eterm node = BIF_ARG_1;
#####: 2546: Eterm *ptr, hdr, *hp, res = NIL;
#####: 2547: Uint sz = 0;
#####: 2548: ptr = boxed_val(node);
#####: 2549: hdr = *ptr;
-: 2550:
-: 2551: ASSERT(is_header(hdr));
-: 2552:
#####: 2553: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2554: case HAMT_SUBTAG_NODE_BITMAP:
#####: 2555: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
#####: 2556: ptr += 1;
#####: 2557: break;
-: 2558: case HAMT_SUBTAG_HEAD_BITMAP:
#####: 2559: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
#####: 2560: ptr += 2;
#####: 2561: break;
-: 2562: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 2563: sz = 16;
#####: 2564: ptr += 2;
#####: 2565: break;
-: 2566: default:
#####: 2567: erl_exit(1, "bad header\r\n");
-: 2568: break;
-: 2569: }
-: 2570: ASSERT(sz < 17);
#####: 2571: hp = HAlloc(BIF_P, 2*sz);
#####: 2572: while(sz--) { res = CONS(hp, *ptr++, res); hp += 2; }
#####: 2573: BIF_RET(res);
-: 2574: }
#####: 2575: BIF_ERROR(BIF_P, BADARG);
-: 2576:}
-: 2577:
-: 2578:
#####: 2579:static Eterm hashmap_info(Process *p, Eterm node) {
-: 2580: Eterm *hp;
#####: 2581: Eterm res = NIL, info = NIL;
-: 2582: Eterm *ptr, tup, hdr;
-: 2583: Uint sz;
#####: 2584: DECL_AM(depth);
#####: 2585: DECL_AM(leafs);
#####: 2586: DECL_AM(bitmaps);
#####: 2587: DECL_AM(arrays);
#####: 2588: Uint nleaf=0, nbitmap=0, narray=0;
-: 2589: Uint bitmap_usage[16], leaf_usage[16];
#####: 2590: Uint lvl = 0, clvl;
#####: 2591: DECLARE_ESTACK(stack);
-: 2592:
#####: 2593: for (sz = 0; sz < 16; sz++) {
#####: 2594: bitmap_usage[sz] = 0;
#####: 2595: leaf_usage[sz] = 0;
-: 2596: }
-: 2597:
#####: 2598: ptr = boxed_val(node);
#####: 2599: ESTACK_PUSH(stack, 0);
#####: 2600: ESTACK_PUSH(stack, node);
-: 2601: do {
#####: 2602: node = ESTACK_POP(stack);
#####: 2603: clvl = ESTACK_POP(stack);
#####: 2604: if (lvl < clvl)
#####: 2605: lvl = clvl;
#####: 2606: switch(primary_tag(node)) {
-: 2607: case TAG_PRIMARY_LIST:
#####: 2608: nleaf++;
#####: 2609: leaf_usage[clvl] += 1;
#####: 2610: break;
-: 2611: case TAG_PRIMARY_BOXED:
#####: 2612: ptr = boxed_val(node);
#####: 2613: hdr = *ptr;
-: 2614: ASSERT(is_header(hdr));
#####: 2615: switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-: 2616: case HAMT_SUBTAG_NODE_BITMAP:
#####: 2617: nbitmap++;
#####: 2618: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-: 2619: ASSERT(sz < 17);
#####: 2620: bitmap_usage[sz-1] += 1;
#####: 2621: while(sz--) {
#####: 2622: ESTACK_PUSH(stack, clvl + 1);
#####: 2623: ESTACK_PUSH(stack, ptr[sz+1]);
-: 2624: }
#####: 2625: break;
-: 2626: case HAMT_SUBTAG_HEAD_BITMAP:
#####: 2627: nbitmap++;
#####: 2628: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
#####: 2629: bitmap_usage[sz-1] += 1;
#####: 2630: while(sz--) {
#####: 2631: ESTACK_PUSH(stack, clvl + 1);
#####: 2632: ESTACK_PUSH(stack, ptr[sz+2]);
-: 2633: }
#####: 2634: break;
-: 2635: case HAMT_SUBTAG_HEAD_ARRAY:
#####: 2636: narray++;
#####: 2637: sz = 16;
#####: 2638: while(sz--) {
#####: 2639: ESTACK_PUSH(stack, clvl + 1);
#####: 2640: ESTACK_PUSH(stack, ptr[sz+2]);
-: 2641: }
#####: 2642: break;
-: 2643: default:
#####: 2644: erl_exit(1, "bad header\r\n");
-: 2645: break;
-: 2646: }
-: 2647: }
#####: 2648: } while(!ESTACK_ISEMPTY(stack));
-: 2649:
-: 2650:
-: 2651: /* size */
#####: 2652: sz = 0;
#####: 2653: hashmap_bld_tuple_uint(NULL,&sz,16,leaf_usage);
#####: 2654: hashmap_bld_tuple_uint(NULL,&sz,16,bitmap_usage);
-: 2655:
-: 2656: /* alloc */
#####: 2657: hp = HAlloc(p, 2+3 + 3*(2+4) + sz);
-: 2658:
#####: 2659: info = hashmap_bld_tuple_uint(&hp,NULL,16,leaf_usage);
#####: 2660: tup = TUPLE3(hp, AM_leafs, make_small(nleaf),info); hp += 4;
#####: 2661: res = CONS(hp, tup, res); hp += 2;
-: 2662:
#####: 2663: info = hashmap_bld_tuple_uint(&hp,NULL,16,bitmap_usage);
#####: 2664: tup = TUPLE3(hp, AM_bitmaps, make_small(nbitmap), info); hp += 4;
#####: 2665: res = CONS(hp, tup, res); hp += 2;
-: 2666:
#####: 2667: tup = TUPLE3(hp, AM_arrays, make_small(narray),NIL); hp += 4;
#####: 2668: res = CONS(hp, tup, res); hp += 2;
-: 2669:
#####: 2670: tup = TUPLE2(hp, AM_depth, make_small(lvl)); hp += 3;
#####: 2671: res = CONS(hp, tup, res); hp += 2;
-: 2672:
#####: 2673: DESTROY_ESTACK(stack);
-: 2674: ERTS_HOLE_CHECK(p);
#####: 2675: return res;
-: 2676:}
-: 2677:
#####: 2678:static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) {
#####: 2679: Eterm res = THE_NON_VALUE;
#####: 2680: Eterm *ts = (Eterm *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(Eterm));
-: 2681: Uint i;
-: 2682:
#####: 2683: for (i = 0; i < n; i++) {
#####: 2684: ts[i] = erts_bld_uint(hpp, szp, nums[i]);
-: 2685: }
#####: 2686: res = erts_bld_tuplev(hpp, szp, n, ts);
#####: 2687: erts_free(ERTS_ALC_T_TMP, (void *) ts);
#####: 2688: return res;
-: 2689:}
-: 2690:
-: 2691:
-: 2692:/* implementation of builtin emulations */
-: 2693:
-: 2694:#if !ERTS_AT_LEAST_GCC_VSN__(3, 4, 0)
-: 2695:/* Count leading zeros emulation */
-: 2696:Uint32 hashmap_clz(Uint32 x) {
-: 2697: Uint32 y;
-: 2698: int n = 32;
-: 2699: y = x >>16; if (y != 0) {n = n -16; x = y;}
-: 2700: y = x >> 8; if (y != 0) {n = n - 8; x = y;}
-: 2701: y = x >> 4; if (y != 0) {n = n - 4; x = y;}
-: 2702: y = x >> 2; if (y != 0) {n = n - 2; x = y;}
-: 2703: y = x >> 1; if (y != 0) return n - 2;
-: 2704: return n - x;
-: 2705:}
-: 2706:
-: 2707:const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
-: 2708:const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
-: 2709:
-: 2710:/* CTPOP emulation */
-: 2711:Uint32 hashmap_bitcount(Uint32 x) {
-: 2712: x -= ((x >> 1 ) & SK5);
-: 2713: x = (x & SK3 ) + ((x >> 2 ) & SK3 );
-: 2714: x = (x & SKF0) + ((x >> 4 ) & SKF0);
-: 2715: x += x >> 8;
-: 2716: return (x + (x >> 16)) & 0x3F;
-: 2717:}
-: 2718:#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment