From f506773cac2d21c74befdd9e614cd7d147495fb4 Mon Sep 17 00:00:00 2001 From: dgp Date: Fri, 8 Sep 2017 11:45:18 +0000 Subject: WIP --- generic/tclHAMT.c | 168 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 122 insertions(+), 46 deletions(-) diff --git a/generic/tclHAMT.c b/generic/tclHAMT.c index 72f1ce8..fd57c00 100644 --- a/generic/tclHAMT.c +++ b/generic/tclHAMT.c @@ -375,7 +375,7 @@ typedef struct ArrayMap { void * children; } ArrayMap; - +/* * * We will use a size_t value to hold the bitmap directing internal nodes. * This means our branching factor can be no bigger than our pointer size. @@ -430,10 +430,6 @@ typedef struct ArrayMap { #define AM_SIZE(numChildren) \ (sizeof(ArrayMap) + ((numChildren) - 1) * sizeof(void *)) -static ArrayMap * MakeLeafMap(const size_t hash, - const TclHAMTKeyType *ktPtr, const ClientData key, - const TclHAMTValType *vtPtr, - const ClientData value); static inline int NumBits(size_t value); static ArrayMap * GetSet(ArrayMap *amPtr, const size_t *hashPtr, const TclHAMTKeyType *ktPtr, const ClientData key, @@ -753,41 +749,6 @@ size_t Hash( /* *---------------------------------------------------------------------- * - * TclHAMTRemove-- - * - * Results: - * New revised TclHAMT. - * - * Side effects: - * None. - * - *---------------------------------------------------------------------- - */ - -TclHAMT -TclHAMTRemove( - TclHAMT hamt, - ClientData key, - ClientData *valuePtr) -{ - HAMT *hamtPtr = hamt; - ClientData value; - - hamtPtr->amPtr = GetSet(hamtPtr->amPtr, NULL, - hamtPtr->keyTypePtr, key, - hamtPtr->valTypePtr, NULL, &value); - hamtPtr->amPtr = GetSet(hamtPtr->amPtr, NULL, - hamtPtr->keyTypePtr, key, - hamtPtr->valTypePtr, NULL, NULL); - if (valuePtr) { - *valuePtr = value; - } - return hamtPtr; -} - -/* - *---------------------------------------------------------------------- - * * TclHAMTCreate -- * * Create and return a new empty TclHAMT, with key operations @@ -809,7 +770,7 @@ TclHAMTCreate( { HAMT *hPtr = ckalloc(sizeof(HAMT)); - hPtr->claim = 1; /* Don't make original creator claim us. (??) */ + hPtr->claim = 0; hPtr->kt = kt; hPtr->vt = vt; hPtr->kvl = NULL; @@ -955,6 +916,7 @@ TclHAMTInsert( { HAMT *new, *hPtr = hamt; KVList l; + ArrayMap *am; if (hPtr->kvl) { /* Map holds a single KVList. Is it for the same hash? */ @@ -973,6 +935,7 @@ TclHAMTInsert( new->claim = 0; new->kt = hPtr->kt; new->vt = hPtr->vt; + KVLClaim(l); new->kvl = l; new->x.am = NULL; @@ -987,8 +950,11 @@ TclHAMTInsert( new->claim = 0; new->kt = hPtr->kt; new->vt = hPtr->vt; - new->kvl = l; - new->x.am = AMInsert(...) ; + new->kvl = NULL; + am = AMInsert(...) ; + AMClaim(am); + new->x.am = am; +/* TODO TODO TODO */ return new; } @@ -1000,21 +966,131 @@ TclHAMTInsert( new->claim = 0; new->kt = hPtr->kt; new->vt = hPtr->vt; - new->kvl = KVLInsert(NULL, hPtr->kt, key, hPtr->vt, value, valuePtr); + l = KVLInsert(NULL, hPtr->kt, key, hPtr->vt, value, valuePtr); + KVLClaim(l); + new->kvl = l; new->x.hash = Hash(hPtr, key); return new; } /* Map has a tree. Insert into it. */ + new = ckalloc(sizeof(HAMT)); + new->claim = 0; + new->kt = hPtr->kt; + new->vt = hPtr->vt; + new->kvl = NULL; + am = AMInsert(hPtr->x.am, ..., /* hashPtr */ NULL, + hPtr->kt, key, vt, value, valuePtr); + AMClaim(am); + new->x.am = am; + + return new; +} + +/* + *---------------------------------------------------------------------- + * + * TclHAMTRemove-- + * + * Remove the key, value pair from hamt that contains the + * given key, if any. + * + * Results: + * The new revised TclHAMT. + * + * Side effects: + * If valuePtr is not NULL, write to *valuePtr the + * value of the removed key, value pair, or NULL if + * no pair was removed. + * + *---------------------------------------------------------------------- + */ + +TclHAMT +TclHAMTRemove( + TclHAMT hamt, + ClientData key, + ClientData *valuePtr) +{ + HAMT *new, *hPtr = hamt; + KVList l; + ArrayMap *am; + + if (hPtr->kvl) { + /* Map holds a single KVList. Is it for the same hash? */ + if (hPtr->x.hash == Hash(hPtr, key)) { + /* Yes. Indeed we have a hash collision! This is the right + * KVList to remove our pair from. */ + +KVList KVLRemove( + KVList l, + TclHAMTKeyType *kt, + ClientData key, + TclHAMTValueType *vt) + + l = KVLRemove(hPtr->kvl, hPtr->kt, key, hPtr->vt, value, valuePtr); + + if (l == hPtr->kvl) { + /* list unchanged -> HAMT unchanged. */ + return hamt; + } + + /* Construct a new HAMT with a new kvl */ + new = ckalloc(sizeof(HAMT)); + new->claim = 0; + new->kt = hPtr->kt; + new->vt = hPtr->vt; + KVLClaim(l); + new->kvl = l; + new->x.am = NULL; + + return new; + } + /* No. Insertion should not be into the singleton KVList. + * We get to build a tree out of the singleton KVList and + * a new list holding our new pair. */ + +/* TODO TODO TODO */ new = ckalloc(sizeof(HAMT)); new->claim = 0; new->kt = hPtr->kt; new->vt = hPtr->vt; new->kvl = NULL; - new->x.am = AMInsert(hPtr->x.am, ..., /* hashPtr */ NULL, - hPtr->kt, key, vt, value, valuePtr); + am = AMInsert(...) ; + AMClaim(am); + new->x.am = am; +/* TODO TODO TODO */ + + return new; + } + if (hPtr->x.am == NULL) { + /* Map is empty. No key is in it. Create singleton KVList + * out of new pair. */ + + new = ckalloc(sizeof(HAMT)); + new->claim = 0; + new->kt = hPtr->kt; + new->vt = hPtr->vt; + l = KVLInsert(NULL, hPtr->kt, key, hPtr->vt, value, valuePtr); + KVLClaim(l); + new->kvl = l; + new->x.hash = Hash(hPtr, key); return new; + } + /* Map has a tree. Insert into it. */ + new = ckalloc(sizeof(HAMT)); + new->claim = 0; + new->kt = hPtr->kt; + new->vt = hPtr->vt; + new->kvl = NULL; + am = AMInsert(hPtr->x.am, ..., /* hashPtr */ NULL, + hPtr->kt, key, vt, value, valuePtr); + AMClaim(am); + new->x.am = am; + + return new; + } /* -- cgit v0.12