From b078ed132c74b0b169d4036ed2f5301ea82e594c Mon Sep 17 00:00:00 2001 From: dgp Date: Thu, 5 Oct 2017 10:38:42 +0000 Subject: Refactor code common to merge and insert. --- generic/tclHAMT.c | 211 ------------------------------------------------------ 1 file changed, 211 deletions(-) diff --git a/generic/tclHAMT.c b/generic/tclHAMT.c index 0de245b..91306c0 100644 --- a/generic/tclHAMT.c +++ b/generic/tclHAMT.c @@ -1330,7 +1330,6 @@ ArrayMap AMInsert( ClientData value, ClientData *valuePtr) { -#if 1 KVList new = KVLInsert(kt, vt, NULL, key, value, valuePtr); ArrayMap result = AMMergeList(kt, vt, am, hash, new, valuePtr, 0); @@ -1340,216 +1339,6 @@ ArrayMap AMInsert( KVLDisclaim(kt, vt, new); } return result; -#else - /* Mask used to carve out branch index. */ - const int branchMask = (branchFactor - 1); - - size_t tally; - int numList, numSubnode, loffset, soffset, i; - ClientData *src, *dst; - ArrayMap new, sub; - - if ((am->mask & hash) != am->id) { - /* Hash indicates key is not in this subtree */ - - /* Caller sent us here, because prefix+index said so, - * but we do not belong here. We need to create a - * missing node between to hold reference to us and - * reference to the new (key, value). - */ - - return AMNewBranch(am, hash, - KVLInsert(kt, vt, NULL, key, value, valuePtr)); - } - - /* Hash indicates key should be descendant of am */ - tally = (size_t)1 << ((hash >> LSB(am->mask + 1)) & branchMask); - - 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 is consistent with one of our KVList children... */ - - if (am->slot[loffset] == (ClientData)hash) { - - /* Found the right KVList. Now Insert the pair into it. */ - KVList l = KVLInsert(kt, vt, am->slot[loffset + numList], - key, value, valuePtr); - - if (l == am->slot[loffset + numList]) { - /* List unchanged (overwrite same value) */ - /* Map unchanged, just return */ - return am; - } - - /* Modified copy of am, list replaced. */ - 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 list (except one we're replacing) */ - for (i = 0; i < loffset; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - 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; - } - /* ...but does not actually match. - * Need a new KVList to join with this one. */ - - sub = AMNewLeaf((size_t)am->slot[loffset], - am->slot[loffset + numList], hash, - KVLInsert(kt, vt, NULL, key, value, valuePtr)); - - /* Modified copy of am, - list + sub */ - new = AMNew(numList-1, numSubnode+1, am->mask, am->id); - - new->kvMap = am->kvMap & ~tally; - new->amMap = am->amMap | tally; - - dst = new->slot; - /* Copy hashes (except one we're deleting) */ - for (i = 0; i < loffset; i++) { - *dst++ = *src++; - } - src++; - for (i = loffset + 1; i < numList; i++) { - *dst++ = *src++; - } - - /* Copy list (except one we're deleting) */ - for (i = 0; i < loffset; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - src++; - for (i = loffset + 1; i < numList; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - - /* Copy subnodes and add the new one */ - 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->amMap) { - /* Hash is consistent with one of our subnode children... */ - sub = AMInsert(kt, vt, (ArrayMap)am->slot[2*numList + soffset], - hash, key, value, valuePtr); - - if (sub == am->slot[2*numList + soffset]) { - /* Submap unchanged (overwrite same value) */ - /* Map unchanged, just return */ - return am; - } - - /* Modified copy of am, subnode replaced. */ - 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 */ - for (i = 0; i < numList; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - - /* Copy subnodes (except the one we're replacing) */ - for (i = 0; i < soffset; i++) { - AMClaim((ArrayMap) *src); - *dst++ = *src++; - } - src++; - AMClaim(sub); - *dst++ = sub; - for (i = soffset + 1; i < numSubnode; i++) { - AMClaim((ArrayMap) *src); - *dst++ = *src++; - } - - return new; - } - - /* Modified copy of am, list inserted. */ - new = AMNew(numList + 1, numSubnode, am->mask, am->id); - - new->kvMap = am->kvMap | tally; - new->amMap = am->amMap; - - dst = new->slot; - - /* Copy all hashes and insert one */ - for (i = 0; i < loffset; i++) { - *dst++ = *src++; - } - *dst++ = (ClientData)hash; - for (i = loffset; i < numList; i++) { - *dst++ = *src++; - } - - /* Copy all list and insert one */ - for (i = 0; i < loffset; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - *dst = KVLInsert(kt, vt, NULL, key, value, valuePtr); - KVLClaim(*dst); - dst++; - for (i = loffset; i < numList; i++) { - KVLClaim((KVList) *src); - *dst++ = *src++; - } - - /* Copy all subnodes */ - for (i = 0; i < numSubnode; i++) { - AMClaim((ArrayMap) *src); - *dst++ = *src++; - } - - return new; -#endif } /* -- cgit v0.12