diff options
-rw-r--r-- | generic/tclHAMT.c | 93 |
1 files changed, 88 insertions, 5 deletions
diff --git a/generic/tclHAMT.c b/generic/tclHAMT.c index 5cf9547..5f4a4a6 100644 --- a/generic/tclHAMT.c +++ b/generic/tclHAMT.c @@ -682,7 +682,7 @@ ArrayMap AMMergeList( const int branchMask = (branchFactor - 1); size_t tally; - int numList, numSubnode, loffset, i; + int numList, numSubnode, loffset, soffset, i; ClientData *src, *dst; ArrayMap new, sub; @@ -697,14 +697,99 @@ ArrayMap AMMergeList( numList = NumBits(am->kvMap); numSubnode = NumBits(am->amMap); + loffset = NumBits(am->kvMap & (tally - 1)); + soffset = NumBits(am->amMap & (tally - 1)); + src = am->slot; if (tally & am->kvMap) { /* Hash consistent with existing list child */ + if (am->slot[loffset] == (ClientData)hash) { + /* Hash of list child matches. Merge to it. */ + KVList l; + + if (listIsFirst) { + l = KVLMerge(kt, vt, kvl, am->slot[loffset + numList], NULL); + } else { + l = KVLMerge(kt, vt, am->slot[loffset + numList], kvl, NULL); + } + if (l == am->slot[loffset + numList]) { + return am; + } + + new = AMNew(numList, numSubnode, am->mask, am->id); + + new->kvMap = am->kvMap; + new->amMap = am->amMap; + dst = new->slot; + + /* Copy all hashes */ + for (i = 0; i < numList; i++) { + *dst++ = *src++; + } + + /* Copy all lists and insert one */ + for (i = 0; i < loffset; i++) { + KVLClaim((KVList) *src); + *dst++ = *src++; + } + KVLClaim(l); + *dst++ = l; + for (i = loffset + 1; i < numList; i++) { + KVLClaim((KVList) *src); + *dst++ = *src++; + } + + /* Copy all subnodes */ + for (i = 0; i < numSubnode; i++) { + AMClaim((ArrayMap) *src); + *dst++ = *src++; + } + return new; + } + /* Hashes do not match. Create Leaf to hold both. */ + sub = AMNewLeaf((size_t)am->slot[loffset], + (KVList)am->slot[loffset + numList], hash, kvl); + + /* Remove the list, Insert the leaf subnode */ + new = AMNew(numList - 1, numSubnode + 1, am->mask, am->id); + + new->kvMap = am->kvMap & ~tally; + new->amMap = am->amMap | tally; + dst = new->slot; + /* hashes */ + for (i = 0; i < loffset; i++) { + *dst++ = *src++; + } + src++; + for (i = loffset + 1; i < numList; i++) { + *dst++ = *src++; + } + /* lists */ + for (i = 0; i < loffset; i++) { + KVLClaim((KVList) *src); + *dst++ = *src++; + } + src++; + for (i = loffset + 1; i < numList; i++) { + KVLClaim((KVList) *src); + *dst++ = *src++; + } + /* subnodes */ + for (i = 0; i < soffset; i++) { + AMClaim((ArrayMap) *src); + *dst++ = *src++; + } + AMClaim(sub); + *dst++ = sub; + for (i = soffset; i < numSubnode; i++) { + AMClaim((ArrayMap) *src); + *dst++ = *src++; + } + return new; } if (tally & am->kvMap) { /* Hash consistent with existing subnode child */ - soffset = NumBits(am->amMap & (tally - 1)); /* Merge the list into that subnode child... */ sub = AMMergeList(kt, vt, (ArrayMap)am->slot[2*numList + soffset], @@ -719,6 +804,7 @@ ArrayMap AMMergeList( new->kvMap = am->kvMap; new->amMap = am->amMap; + dst = new->slot; /* Copy all hashes */ for (i = 0; i < numList; i++) { @@ -751,11 +837,8 @@ ArrayMap AMMergeList( new->kvMap = am->kvMap | tally; new->amMap = am->amMap; - - src = am->slot; dst = new->slot; - loffset = NumBits(am->kvMap & (tally - 1)); /* Copy all hashes and insert one */ for (i = 0; i < loffset; i++) { *dst++ = *src++; |