From a7a058d0ef15c07ef1b976f1f67e9a4e57881e9e Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Tue, 9 Jun 2020 15:38:32 -0500 Subject: [PATCH] Even more bug fixes for bh_hash --- docs/new_hash_plan | 6 +++--- include/bh.h | 24 +++++++++++++++++++++--- onyx | Bin 103288 -> 103328 bytes 3 files changed, 24 insertions(+), 6 deletions(-) diff --git a/docs/new_hash_plan b/docs/new_hash_plan index d12fc1d1..117ae146 100644 --- a/docs/new_hash_plan +++ b/docs/new_hash_plan @@ -27,9 +27,9 @@ Attempt 1 to fix these issues: table ----> | allocator | hash size | ptr | ptr | ptr | ptr | ptr | ... +-------------------------||-------------------------------- \/ - +--------------+---------------------------------------------------------------------------- - | Array header | value | key_length | key (null terminated) | v | kl | k | v | kl | k | ... - +--------------+---------------------------------------------------------------------------- + +--------------+------------------------------------------------------------------------ + | Array header | length | value | key_length | key (null terminated) | v | kl | k | ... + +--------------+------------------------------------------------------------------------ GOOD: * This implementation would allow for any size of key. diff --git a/include/bh.h b/include/bh.h index 57c04f28..8d3f6a23 100644 --- a/include/bh.h +++ b/include/bh.h @@ -546,7 +546,7 @@ typedef struct bh__hash { #define bh_hash_iter_setup(T, tab) (assert(sizeof(T) == sizeof(*(tab))), bh__hash_iter_setup((bh__hash *) tab, sizeof(T))) #define bh_hash_iter_key(it) ((char *)(bh_pointer_add(it.entry, it.elemsize + sizeof(u16)))) - #define bh_hash_iter_value(T, it) (assert(sizeof(T) == it.elemsize), *(T *)it.entry) + #define bh_hash_iter_value(T, it) (*(T *)it.entry) #else #define bh_hash_init(allocator_, tab, hs) bh__hash_init(allocator_, (bh__hash **)&(tab), hs) #define bh_hash_free(tab) bh__hash_free((bh__hash **)&(tab)) @@ -1614,10 +1614,16 @@ b32 bh__hash_free(bh__hash **table) { // Assumes NULL terminated string for key ptr bh__hash_put(bh__hash *table, i32 elemsize, char *key) { + elemsize += (elemsize & 1); + u64 index = bh__hash_function(key, 0, table->hash_size); + u8 arr_was_new = 0; ptr arrptr = table->arrs[index]; - if (arrptr == NULL) goto add_new_element; + if (arrptr == NULL) { + arr_was_new = 1; + goto add_new_element; + } u64 len = *(u64 *) arrptr; arrptr = bh_pointer_add(arrptr, sizeof(u64)); @@ -1645,7 +1651,11 @@ add_new_element: bh__arrhead(arrptr)->length = byte_len + elemsize + sizeof(u16) + key_length; table->arrs[index] = arrptr; - (*(u64 *) arrptr)++; + if (arr_was_new) { + *(u64 *) arrptr = 1; + } else { + (*(u64 *) arrptr)++; + } arrptr = bh_pointer_add(arrptr, byte_len + elemsize); *(u16 *) arrptr = key_length; @@ -1657,6 +1667,8 @@ found_matching: } b32 bh__hash_has(bh__hash *table, i32 elemsize, char *key) { + elemsize += (elemsize & 1); + u64 index = bh__hash_function(key, 0, table->hash_size); ptr arrptr = table->arrs[index]; @@ -1678,6 +1690,8 @@ b32 bh__hash_has(bh__hash *table, i32 elemsize, char *key) { } ptr bh__hash_get(bh__hash *table, i32 elemsize, char *key) { + elemsize += (elemsize & 1); + u64 index = bh__hash_function(key, 0, table->hash_size); ptr arrptr = table->arrs[index]; @@ -1701,6 +1715,8 @@ ptr bh__hash_get(bh__hash *table, i32 elemsize, char *key) { } void bh__hash_delete(bh__hash *table, i32 elemsize, char *key) { + elemsize += (elemsize & 1); + u64 index = bh__hash_function(key, 0, table->hash_size); ptr arrptr = table->arrs[index], walker; @@ -1736,6 +1752,8 @@ found_matching: } bh_hash_iterator bh__hash_iter_setup(bh__hash *table, i32 elemsize) { + elemsize += (elemsize & 1); + bh_hash_iterator it = { .tab = table->arrs, .endtab = table->arrs + table->hash_size, diff --git a/onyx b/onyx index 07abf01edf8a8635341611f0f918a97748de66a3..89915f0778d2b5e529900446753f71b9bda5a197 100755 GIT binary patch delta 7093 zcmZ8lcYIXk(mr!qHYC~IB%87u(nuhMO?GJ^e6+;CWeKPtprIxRp(s*=^lT^zgeJ=o zU&N^350#>V>^0%ixim$+l+Q*J#BvjbD<}ahuy^LXyL*xI$DX&$JTvpmyk*bbx73Yq zt7|ghiYM!GX!Artf116Ka0D#b9qW%at~xmWo#@^59j{#as-gJx_1;Eta+0ZLf*`n7 zMVRzg_xHW!sZT}0^V{)7EuNheB;n$Lq4ApCD*CoowD?ovw#LmF6uR z3jgs&Jdz@dN*Ax=Zzm$4n|5bVGJNNa8+qy1!=H`1hg{?>@Y#Qzu;+z)J9k4MOQ62CsahZR`kB&Iw1gt@{>_xl>_1b zw5G}&=&!}O9pWSBG;>v|HqqT57HIYE5}2!*s;0p%ZDG}HctQKUs)pJNv*8o%orRO2 z*lS&sCBk!B(ULZ{Igx^}n;2@W_}=H+O%|GV%Gj;Z7B6XMZvMvSbFHct?&GWWMB{nw z=#n(^xNZ8N)5ixFXm^%4%v-#2DSY&@ z&!>&<8B>(Xe7=v4jLS78FCi8MQ*tjs_|=s3d*M_4S9O23qaYMM*|+wK!XbTYn+pdQ z*8VxfwJK)>4iD;|bs|W4&1$zKuwlgeesYjpiD$C_w=hYueHWc6!@w{aJ=aZ|ZyB zgot~cTA>*0wbj1>a7^3QkN{roctdB?F`FQW4PdIE0ylfT;k&ni@nF0lNJZvC3CE0H z@6mruL?v(T-p>FIdZqoFsQ2c96G6cnyW=7mXRD2B5RHT~;J3Ul14 zBPzy{{RPFc`irUf>-*v`P8|MnlNey=2C)|I)ux``gI=_~U`37I7s#WHdV7!Fj=9KV zko_@)6BBY(#0sR%5PneGd=WLgzKew-Di&Tw5byBI_rzds#`D~0cle?i_Z5l?9&z=vT84Ww*gTc-;*nSzvmRowd(p{3gqPxrvoYYo?Ny5P=UXze;|!5 zKaeZZzbBC^Q=7<@=3$$35M@ohFc81T_l)gP!Q6l& zf_bO~Wy~9peo=@eApnpfa6YaIE%`MhFis9r&Dxh4Q-*xXflZrRN{Q>U~~hbAmS+$i$A9gy_xm+ zITDTo=>TDNMr(eTtYA#QyqMc#jDmR)DViJ6K0=ZdB!bk8D)9yQlL^USo`TZ0W7?UU zv~66!*%^<`*1u%w1q!%%=t;79wUNJMxlbZm3PgzJLPZd)6{DXPz$k`LN3hK!OGYt* zdInnqv1bz1&XiS~nS3>gX6jjNV~KsUsAn-=Pz;p$Sb~N~QM!iS#J>@OKM*aNS0R{< zwlT1XrZBJa>p{LRDMjYfDq6L8y=QOf`_hliw3Z*c{Vvw_pSP*pWAD%cn0ANSEA;jc zcW5yTze^)C@6zn)yR^5={Vj>_Eg{=NlF=F2LW?+LyYVyh!(ch+_5R_Yo%P#4tBbl~ zC}OxmiLfrgAADRCKR!@*6;Fb+%|v#%kt8Hf-Mq9<^}cP6-d{5>y;9qLk2d&^@8v>) z_B*yGYqtBzkufBf8%7I6^4wUEepM^J?}#i$Uc|}p$1<`Y2YbWogN2QalD}-2=Jb#}jWTdS1rDfb%%Aua-FJT8d zoj#k4kBY3<0T0a+GM8$_z7)5PFwW@Eha2Y!Le^Ybx))WY3_C$CF6FmiX zy{yivU3p0R+&N_H|5ZJ3(K7&{>kuvXds;g?RP}rn#~T%Na5yeeyN}GfNv*mLLz}m4|%otA+Huc?9~!= zl%HPBI9>@loJg!XPdvjhJJb(b>r zgsK>H%KCCf1_w+JXuF;=Tdu;s1ss(#G&BI?9tPw({$nv_O%3Ykvbh_wIi>X0=tE&GNgv; z^&Y2&f54nF#ALomUP-FDjyS*{zgHy zSGv$ePx8D|X{Yl52YS0uOY&^2%z1j|H~~5+A#2$w16W}fYcfD;S^|mXD=HlllIOEZ zp~Z6u`vxw_ut%`r7M#s2Cls$D{aL?INRQI(LE0utI2eY9&|Ajj^> zMt7nhgi0Gfr)crf-CKiW9mqYONpP-W31O)IZ`LIY^0UKei@PT4WLYQaDnbc=Az7tK zSRF{iH94u2y%GjVk=&e%vvVEIv6ErY8VcAA1P%Y#FaNEaP|B>~&~0!l+N>^d{7cVp z;E_T6q-4T>4o|vEa=M6=;(3$({AlX7)r9c1+@cY0b#xFqN3yNq7{E++A{_GJ z$Co0o^C3%$fQ0z`@UPo9zBP1qgqy|>W3vzc_ zB~~sQ)Q{Dh6IjD#fU%C<*B;=~4o;#JXGPUh~pI96{t zi(?h=Qs^yrr>_fmsdn>P=q>l7Y|{4wdm@!yZ+Rra(Y-Nedif0e!XO)XzRMg#Si2~Q zg^SD;1&I?LX&tcI;~`Rd1WDmmd&qgbgk0Qc54jhIEU=%Xt*3|lB)7TSZ?k8><^&~0ifKtGle4T-V81*a0_>_B#wu|d(`w0}hmT4fXc^Zj%*CqE;Y zgYIntAz0pA7hai0eIN=8D#h3+^`Yo}Q9-`C4Y1`^{wCtJEoq2%ByWkT+1 zRu%)+I3+VM*+pvQ#}jgk*czP7D-TXO1Cu3o{riSf%J-l2_Gic$r__fhb$}y|U5{MI3MUjg+m5rPv5*O!*v?pp zvG1d;;jU;T7i|7L0f+Pl>ZXuo{XTM6Z0le*W1-c!gTb*TF^Pkg@Pqe9F}9Q6$SwSW z3qJ+=6NFrq>|7Mp>mxY!=Aez_?0}7nK|K3PHYW~KoW!=pVTwN>5k1BG0t8TsFU5hQ zqfP)0|24%p5KOV2(*6890-ZjcMzDf-T=c70X*}LVqS%~xNP~gw)p$JnD%jq5yfDmS zU&liVJkNYIc$_6#p;go@V)9MV;ZKj?JjVuFaXOw&u|kLB<+Maz74^Sen}+fD3W8w{ zV~4Gf)^R8Cuu{~Ir9OTk{|mSC_v{$xTU;b=JnGV3wVlP=(3f9X7aQJTZjwkH8)1X) zP{=mepdEb9KEavT898+O6kwj1R-vm-5}a}z^Vy(f%$xqXSz>BnF6%AkOn^k!m;R|4 zV$0yvNeX3(sNYhZLwO92U?`#Zk&g^b5t9NMd1A|kbqS!QgdC)A075-W$p%Y9Q8#!t z%!>Ch#nxX@4N*!&KSe24OhXl^pAs>Q9q0pHAeG(g1EaethW?5?UWqPNl(mXntXR4! zVY8G_Lovxl6)RygmC!|s*iY#!jWsM%LZ##s1rWKLVHo?y1@R4ATyPS=(=ekL#>9r< z-<8r?qi2*(E}zx#c^T9g8b(ZnZUBu9FFym1hrpGFrfF~oU_bk21|I(R*>5x8ZJgay z0Ve>?H%xpUmWnWy-JFfH`3<3SaG!)ptleD55Uoqtu(|Lb$ZP034^BnFo6Ncz9HEW1 zoTA2tfvcg9Br4d;@$P&!6uVe)p0&^uCa^Q~ P`iezr_^M?CHOTlc%_5(s delta 7109 zcmZ8ld3+RA^6%;^lWS&j-xmqwV3HXEgzzyyvJeRo0hMTw!*Jw45D){3KqiRdlR6O9pInWq#xT`BXu_K6i(}9tdxLsqRR2dyiR91<$me?Yy~7d#G%#`=U4_(Na|- z2qnvcuT;}*0CQKSJQfP$w2yixgQT7A-42Vi*ZQPEy0)WFmmKkcAZXcrW8M4ub_GI} z<}Mlo$K1hxNtVS+`EL9D2ZEuS_Uj`_aM&F+`dWr&Sr{)_7A?_wFC6E;f1StEw9B$+ zoVIdds&oljXjMD0&;~O#rEU^LYc+Lw+WU16!Dvl#W+QqpryZG0bj|>#9d(w&t6FCL z)9`QYul3Kt+gfJzwaPN4=6~wNXvk zuvM#TO0iDiOM+LvQG2iHzR3@MqRY?nPM+99U`=Ok>$8Pk6zKqkqBa~U_@;*K_jo#w zikO6@y7W#WPuy}*787&X;&W(~_Tb{=&@o5#=>x`ejpkhZguTWX-#M$Btnixro3^B$o?a?JE_D-|UR3%|7Z8}KomkO5lLfO*3t9d_S95Q5zw2ey! z_i-BIU(S$l@d@<$DC%8GLjZbMD(H&UhTvf>;l)9LDaN>7tA4RMXnU~FxcQ9s)r$!u zUq7Pz;Y+~UWBSk+^c8&Q3-|I}`l>I5Wo`O!jW-6>-*`OQ#6b}Q?qeR$p*>ZWq(u~E z;TKEdt)j<qVoBn*S&(S(d#3rym)fdAsC=%chG?_gl@A zR4rLb{zuDI|Nd((dOYi~*lIdGp1pV<@`K0o9p2Yn@_6J>K}f&s@ucDXg)Wb02;PtV z?D0&&`w(~Ls&9i6AI6LeMP}<_ad5CIJtzkGnS^+px`tu6c3jKalnAZbuuVx&u1&?? z*R|$NN#gHcYMXJPpLPhRYP8NxL!rgp>+LHt9CW9=d)7}}>(GkCNOx@eD*)TI%^h*j zrtR^xuyUM0#X`24OYl+ae}o{Tnb?0zS%Ge!`UT6GyN%jS2`0cB3`HAFR;-P+Di9_Q=L zcdx%>toPpYICN^u_tbJJ=iO5EhE&2{l6r3M+eoR~z6y~GZ}z*(m3!%-*>Wg(3im@;ZUB1h+Uo4q>9+jmQF62D$Q~7a$vRHHEI&RAe?7-{w}kK*i1ogZT(5q zaC=S`iKtlg4T8AGesfzia#PK7qg9{lhhDBecK{;18S2Y36p7@Am_F1RcExC~ezyuy z?B|Kfu=6~`aeEor7KpJ28?b*pIFSrN;@v8`xntmZNdJ*1A9F zx&cKeu_*lH`)~rDH9JtyYQiD}A#8t?AUNPvs}twK>nSs@SpxA{2wzSDudCBB5Z3U= zw4bk}k0oJPDUp8IFZgVQRaQ4Cejb4ff7NA$@PViSt)@x@F$pG;gEu9Ld)O6ZkpXR1 zz*ul&o4m#Xwc4xcPFjb}(#I%k$wx=LjBlHBQNg+eX9Vk*aFnqw$MB0nBnbh46pZUp zwP?w!A%Xd6QW=e#7_1k=P}o|C&$6`+y)s$HqN5fek~AOyq(P+a7dObz4+8Ug($7O< zf;F1Fvo1kfXwr{Nq6c-j9$A7kAQXZhL$T=3v@t(rj{J;-qd?k8m_5;&mr@Lv<1jDQ z9_XWBolA<=lV~3yNeU7`x{fN*h4_;JNno9c(y`mM|Nca6qwA-Buu<#&bEaOPfXzcs zQf!+x{^v~RPDD$FV9{En2trKl#7P2}ML!w{u`|h%Sq!F;DYk>6XA#wYl+{?7xLQOj zjlyHgDf(7X&tkNom?-m+1PvjgbQ#%1uk*tn2otT#5GM*#{=aK_U;5!X?d1_S-oe`b;|7&`Z&Gi0 z{-^N+`Z#u;K5m(xHe1_rI|)10r?+#Uk9G^6Cuy;Fl0y7RE+>#S zh~&DuFzvWjddD6z5aS}wfU_@>1wlv~r@eG1Ddk*QYPe7lh0iv~`cEN(F-ct&u~F!)LmnwFkcHvZmIOL?%6B@91fzQutPd zQg660qg@(N$tk#MX%8R4Qgf%K5-03cVP%6iD2|mBu@+S!8{awk>`Ct; zv|cq_YfCc1`j$6C~W+^=n3zg#{ZHQX=F>zC72&WXP66R6-s-{3?= z*Q0_Xn6~qLUJ>zLRtF7MP3Sid`22fV&A*4${Cim~P$zi9?WI-c3%8e5!#%7P-NmYs zN?;U^)!_x4j(+;WM`#^^yV&N>28)pE)HD0g|Dg2DKH@Vqs^`npye6vfuZ0|iN2JWB z;7wh*&vvPvIe1ouD|KAKUO)|OvM=|;1xGD~YzPk-lO+f>uhR)p4Gd8e*ReDSatbmj z-FaMU2JSt&cJmv$5Rbw(y*1{k$<(B=>Uf~@)Vy_Uxdizc?-HO@Rr8+bYWY|NbV2KC zT*;a^dp0d6tY$w-5EY^a!m9S+wNhv^u}B$G{PlQ5sX-f9p$rijFA^(BRbQiqhSyqt zL(Dkb5*$+^%!M*UmFbw04|9~wgpCTd2XPz2dAZ4I;0EMF2MtFI?W^mGUnRnR`W(kT zY?xS!tF|iEDMPPZo!1S;t6GsgdEzVqZYn{8^->>gA4)`TDf;<9bd?K^BW$<=3F+qz znpcz-2|mc zBPcGpir;ADIByo`8;>{UfmHu?ZlU#qVv(cLXCyGl@OLDEL%bql+ zN`T&qUnBd*1TnCY{bqucR11maD=NJnB-gPzA>b*5U4ff1@Gtn_6davwfIl8W3fNeG zNDI~Ng!t@yh<2FEAEM(LQA2W_spEY$Tru&6b)wF`k?r+|ZfNg&gi+tZda_lrfB+Z= z5v)1@%HbKdD*z45WTyilE|AH$g&Tkm3k%?Fx7>3Jo;z+h75E4VUxe^|oE;Pr!3WV;^ z=k*{+2>QS){;eE0l4S-#!RScpQl~ilsV6z^cmv*?MDS1HEAEt>CSpYKMUypmA`N?S zLxuKvgm798xQNF&dILHhV%yOcRI)FEARkUMYcP(sv7BIt%m0(ok-L;?F-owH^Eisf zeY#HY8@g#>4Z(<&$aWxB;oxKpc?p_>x8-aa(7shnbc}SoNrk>v4yD04N*P}7^Bdx9 zP1bjBlo{)H9_vrH4mQ>d2}w~YzFqQ)Jb-oyRlH62?G^dKk&Kxk%a%aBW3jAI3C^hE zsACN9X#}BbET-^wnelL(#S{zV{ZQ|0cl9Ap#+ zeey2Qv23#y8|2_rpTm>oZroungDH0j_hmn#u#*|W<8c${(J8mxro+y7Ipa^3Cj3vi z&;3-jWpWU;iEEQN?=pjaKpNHk6q4w{UlijwWSN}fg|t~XLTEAlf5Lp(^bnQF4+pT; z5J&_&`yd1ornVszuZm(hiPJ0LSjBQC$13EdP%ICi?+SRFcJf*%mLH&O(w75U2$f#3 zJf7g_#F#z1@)`WLAe(r;E9}EqQ7A;hQC1!b2{pOheO3qF6O@5QP`K5Bavm?C5^i*$ zJcL6Q+IG?*VW9jdx4F%0bCAzwjgUEjokDBoCc|33oHmk~!XO<6F-I6AM0OfW338S% zI}6z4FmTxZO%aTdE%cxFvxz+T=|&E+d-z<4k-Lv%ABRCStY9Y)G{3=E3X{`)pyx1D z5GMEMZEBQ#12xVF*+PGhMb~s8^I8PU4u|;2^M>|KDch%=%bo}a2fq1Q!jbh-q+!$l z-Iqwf57gzh>1|CWn$Z2G=A|NK}y0O?_>gL50a{93~xR_U#;nQ^Z7Rzn= zmko!M?|swTCJ-5iG?XWGls%ALiGZBQq)eZO9?|Pz33}K&5_FK7B{AQPH^R8`#Wf zJd22|IT})-n7tE?@4hMQ(`Y;}Ok+PrLoz(cEHOCQ&az{mTj(_MVS{M*rblpm#wOCT zi8*7ScTyc~kvB#C57*kqxqpR*o2Bf(F_7A4J;nQFQGYEB^$K}!*v{Xwp`)v~NK`fI zQmGX;JuEf+@U3I$PxEaYT zaS$Kzns@D4F~zr*xr!CWK|;v^@6t13ys@;CT$w5Ar&Pxn?t|TMLy-DK1$7Q?*iHdYs)Uf#{BXC2$zvjgFR5 zm>k*RsemR^#|u+2AaJl__meQv4|a8g%!Xef=H8DEX^J3(3cw`wAEYh3q%F UZDsv6RGHY!WgcP;FGJG*1L7K^YXATM -- 2.25.1