From 99b7ce979f72087be74b039aa988a4f25f3b6d27 Mon Sep 17 00:00:00 2001 From: Steve Bennett Date: Sat, 6 Jun 2020 15:06:34 +1000 Subject: [PATCH] core: dicts (and arrays) now preserve insertion order Although the documentation has always stated that, like Tcl, insertion order of dictionaries was preserved, this has never been the case. Instead, dictionaries were implemented as simple hash tables that did not preserve order. Now, a new implementation of dictionaries preserves insertion order and has a number of other benefits. Instead of hashing keys and storing keys and values in the hash table, the keys and values are not stored in a separate table, exactly as lists are stored, with alternating key, value pairs. Iterating over the dictionary is exactly like iterating over a list, where the order is consistent. The hash table uses closed hashing rather than open hashing to avoid allocatation of hash entry structures. Instead a fixed (but expandable) hash table maps the key hash to the offset in the key/value table. This use of offsets means that if the key/value table grows, the offsets remain valid. Likewise, if the hash table needs to grow, the key, value table remains unchanged. In addition to the offset (which indexes to the value, and 0 means the hash table entry is unused), the original hash is stored in the hash table. This reduces the need for object comparisons on hash entry collisions. The collision resolution algorithm is the same as that used by Python: peturb >>= 5; idx = (5 * idx + 1 + peturb) & dict->sizemask; In order to reduce collisions, the hash table is expanded once it reaches half full. This is more conservative that Python where the table is expanded when it is two thirds full. Note that if a hash collision occurs and then the original entry that cased the hash collision is removed, we still need to continue iterating when searching for the new key. Don't stop at the now-empty slot. So these entries are marked with offset=-1 to indicate that they need to be skipped. In addition, the new faster hashing algorithm from Tcl 8.7 is used. This the hash for integers to be calculated efficiently without requiring them to be converted to string form first. This implementation is modelled largely on the Python dict implementation. Overall the performance should be an improvement over the current implementation, whilst preserving order. Dictionary creating and insertion should be faster as hash entries do not need to be allocated and resizing should be slightly faster. Entry lookup should be about the same, except may be faster for pure integer keys. Below are some indicative benchmarks. OLD NEW dict-create-1.1 Create empty dict 97.2ns . dict-create-1.2 Create small dict 440ns -27% dict-create-1.3 Create medium dict 1.54us -57% dict-create-1.4 Create large dict (int keys) 130us -80% dict-create-1.5 Create large dict (string keys) 143us -75% dict-set-1.1 Replace existing item 258ns -34% dict-set-1.2 Replace nonexistent item 365ns -49% dict-exists-1.1 Find existing item 55.7ns -5% dict-exists-1.2 Find nonexistent item 55.0ns -5% Signed-off-by: Steve Bennett --- jim-array.c | 4 +- jim.c | 579 ++++++++++++++++++++++++++++++++++++++----------------- jim.h | 26 ++- jim_tcl.txt | 1 + tests/array.test | 2 +- tests/dict.test | 36 ++++ tests/dict2.test | 2 +- tests/runall.tcl | 4 +- 8 files changed, 473 insertions(+), 181 deletions(-) diff --git a/jim-array.c b/jim-array.c index 4213bc3..a0ccecd 100644 --- a/jim-array.c +++ b/jim-array.c @@ -114,7 +114,8 @@ static int array_cmd_unset(Jim_Interp *interp, int argc, Jim_Obj *const *argv) return JIM_OK; } - if (Jim_DictPairs(interp, objPtr, &dictValuesObj, &len) != JIM_OK) { + dictValuesObj = Jim_DictPairs(interp, objPtr, &len); + if (dictValuesObj == NULL) { /* Variable is not an array - tclsh ignores this and returns nothing - be compatible */ Jim_SetResultString(interp, "", -1); return JIM_OK; @@ -128,7 +129,6 @@ static int array_cmd_unset(Jim_Interp *interp, int argc, Jim_Obj *const *argv) Jim_DictAddElement(interp, resultObj, dictValuesObj[i], dictValuesObj[i + 1]); } } - Jim_Free(dictValuesObj); Jim_SetVariable(interp, argv[0], resultObj); return JIM_OK; diff --git a/jim.c b/jim.c index 8c6cfc8..2ce0a48 100644 --- a/jim.c +++ b/jim.c @@ -119,6 +119,7 @@ static void JimPanicDump(int fail_condition, const char *fmt, ...); #endif #ifdef JIM_OPTIMIZATION +static int JimIsWide(Jim_Obj *objPtr); #define JIM_IF_OPTIM(X) X #else #define JIM_IF_OPTIM(X) @@ -141,7 +142,6 @@ static int ListSetIndex(Jim_Interp *interp, Jim_Obj *listPtr, int listindex, Jim static int JimDeleteLocalProcs(Jim_Interp *interp, Jim_Stack *localCommands); static Jim_Obj *JimExpandDictSugar(Jim_Interp *interp, Jim_Obj *objPtr); static void SetDictSubstFromAny(Jim_Interp *interp, Jim_Obj *objPtr); -static Jim_Obj **JimDictPairs(Jim_Obj *dictPtr, int *len); static void JimSetFailedEnumResult(Jim_Interp *interp, const char *arg, const char *badtype, const char *prefix, const char *const *tablePtr, const char *name); static int JimCallProcedure(Jim_Interp *interp, Jim_Cmd *cmd, int argc, Jim_Obj *const *argv); @@ -152,7 +152,6 @@ static void JimRandomBytes(Jim_Interp *interp, void *dest, unsigned int len); static int JimSetNewVariable(Jim_HashTable *ht, Jim_Obj *nameObjPtr, Jim_Var *var); static Jim_Var *JimFindVariable(Jim_HashTable *ht, Jim_Obj *nameObjPtr); - /* Fast access to the int (wide) value of an object which is known to be of int type */ #define JimWideValue(objPtr) (objPtr)->internalRep.wideValue @@ -721,15 +720,15 @@ unsigned int Jim_IntHashFunction(unsigned int key) return key; } -/* Generic hash function (we are using to multiply by 9 and add the byte - * as Tcl) */ -unsigned int Jim_GenHashFunction(const unsigned char *buf, int len) +/* Generic string hash function */ +unsigned int Jim_GenHashFunction(const unsigned char *string, int length) { - unsigned int h = 0; - - while (len--) - h += (h << 3) + *buf++; - return h; + unsigned result = 0; + string += length; + while (length--) { + result += (result << 3) + (unsigned char)(*--string); + } + return result; } /* ----------------------------- API implementation ------------------------- */ @@ -1025,7 +1024,12 @@ static unsigned int JimHashTableNextPower(unsigned int size) /* Returns the index of a free slot that can be populated with * a hash entry for the given 'key'. - * If the key already exists, -1 is returned. */ + * If the key already exists the result depends upon whether 'replace' is set. + * If replace is false, returns NULL. + * Otherwise returns the existing hash entry. + * Note that existing vs new cases can be distinguished because he->key will be NULL + * if the key is new + */ static Jim_HashEntry *JimInsertHashEntry(Jim_HashTable *ht, const void *key, int replace) { unsigned int h; @@ -3828,9 +3832,37 @@ static void JimVariablesHTValDestructor(void *interp, void *val) static unsigned int JimObjectHTHashFunction(const void *key) { - int len; - const char *str = Jim_GetString((Jim_Obj *)key, &len); - return Jim_GenHashFunction((const unsigned char *)str, len); + Jim_Obj *keyObj = (Jim_Obj *)key; + int length; + const char *string; + +#ifdef JIM_OPTIMIZATION + if (JimIsWide(keyObj) && keyObj->bytes == NULL) { + /* Special case: we can compute the hash of integers numerically. */ + jim_wide objValue = JimWideValue(keyObj); + if (objValue > INT_MIN && objValue < INT_MAX) { + unsigned result = 0; + unsigned value = (unsigned)objValue; + + if (objValue < 0) { /* wrap to positive (remove sign) */ + value = (unsigned)-objValue; + } + + /* important: use do-cycle, because value could be 0 */ + do { + result += (result << 3) + (value % 10 + '0'); + value /= 10; + } while (value); + + if (objValue < 0) { /* negative, sign as char */ + result += (result << 3) + '-'; + } + return result; + } + } +#endif + string = Jim_GetString(keyObj, &length); + return Jim_GenHashFunction((const unsigned char *)string, length); } static int JimObjectHTKeyCompare(void *privdata, const void *key1, const void *key2) @@ -6560,27 +6592,26 @@ static int SetListFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) return JIM_OK; } - /* Optimise dict -> list for object with no string rep. Note that this may only save a little time, but - * it also preserves any source location of the dict elements - * which can be very useful - */ + /* Optimise dict -> list for object with no string rep. */ if (Jim_IsDict(objPtr) && objPtr->bytes == NULL) { - Jim_Obj **listObjPtrPtr; - int len; - int i; - - listObjPtrPtr = JimDictPairs(objPtr, &len); - for (i = 0; i < len; i++) { - Jim_IncrRefCount(listObjPtrPtr[i]); - } + Jim_Dict *dict = objPtr->internalRep.dictValue; + /* To convert to a list we need to: + * 1. Take ownership of the table + * 2. Discard the hash table + * 3. Free the dict structure + */ - /* Now just switch the internal rep */ - Jim_FreeIntRep(interp, objPtr); + /* 1. Switch the internal rep */ objPtr->typePtr = &listObjType; - objPtr->internalRep.listValue.len = len; - objPtr->internalRep.listValue.maxLen = len; - objPtr->internalRep.listValue.ele = listObjPtrPtr; + objPtr->internalRep.listValue.len = dict->len; + objPtr->internalRep.listValue.maxLen = dict->maxLen; + objPtr->internalRep.listValue.ele = dict->table; + + /* 2. Discard the hash table */ + Jim_Free(dict->ht); + /* 3. Free the dict structure */ + Jim_Free(dict); return JIM_OK; } @@ -7158,18 +7189,11 @@ static void DupDictInternalRep(Jim_Interp *interp, Jim_Obj *srcPtr, Jim_Obj *dup static void UpdateStringOfDict(struct Jim_Obj *objPtr); static int SetDictFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr); -/* Dict HashTable Type. +/* Dict Type. * - * Keys and Values are Jim objects. */ - -static const Jim_HashTableType JimDictHashTableType = { - JimObjectHTHashFunction, /* hash function */ - JimObjectHTKeyValDup, /* key dup */ - JimObjectHTKeyValDup, /* val dup */ - JimObjectHTKeyCompare, /* key compare */ - JimObjectHTKeyValDestructor, /* key destructor */ - JimObjectHTKeyValDestructor /* val destructor */ -}; + * Jim dictionaries use a specialised hash table for efficiency. + * See Jim_Dict in jim.h + */ /* Note that while the elements of the dict may contain references, * the list object itself can't. This basically means that the @@ -7183,68 +7207,220 @@ static const Jim_ObjType dictObjType = { JIM_TYPE_NONE, }; -void FreeDictInternalRep(Jim_Interp *interp, Jim_Obj *objPtr) +/** + * Free the entire dict structure, including the key, value table, + * the hash table and the dict structure. + */ +static void JimFreeDict(Jim_Interp *interp, Jim_Dict *dict) { - JIM_NOTUSED(interp); + int i; + for (i = 0; i < dict->len; i++) { + Jim_DecrRefCount(interp, dict->table[i]); + } + Jim_Free(dict->table); + Jim_Free(dict->ht); + Jim_Free(dict); +} + +enum { + DICT_HASH_FIND = -1, + DICT_HASH_REMOVE = -2, + DICT_HASH_ADD = -3, +}; + +/** + * Search for the given key in the dict hash table and perform the given operation. + * + * op_tvoffset is one of: + * + * DICT_HASH_FIND + * - if found, returns the table value offset, otherwise 0 + * DICT_HASH_REMOVE + * - if found, removes the entry and returns the table value offset, otherwise 0 + * DICT_HASH_ADD + * - if found, does nothing and returns the table value offset. + * otherwise adds the entry with a table value offset of dict->len + 1 and returns 0 + * A table value offset (> 0) + * - in this case the entry *must* exist and the table value offset + * for the entry is updated to be op_offset. + */ +static int JimDictHashFind(Jim_Dict *dict, Jim_Obj *keyObjPtr, int op_tvoffset) +{ + unsigned h = (JimObjectHTHashFunction(keyObjPtr) + dict->uniq); + unsigned idx = h & dict->sizemask; + int tvoffset = 0; + unsigned peturb = h; + + if (dict->len) { + while ((tvoffset = dict->ht[idx].offset)) { + if (tvoffset == -1) { + /* An entry with offset=-1 is a removed entry + * we need skip it when searching, but stop when adding. + */ + if (op_tvoffset == DICT_HASH_ADD) { + tvoffset = 0; + break; + } + } + else if (dict->ht[idx].hash == h) { + if (Jim_StringEqObj(keyObjPtr, dict->table[tvoffset - 1])) { + break; + } + } + /* Use the Python algorithm for conflict resolution */ + peturb >>= 5; + idx = (5 * idx + 1 + peturb) & dict->sizemask; + } + } - Jim_FreeHashTable(objPtr->internalRep.ptr); - Jim_Free(objPtr->internalRep.ptr); + switch (op_tvoffset) { + case DICT_HASH_FIND: + /* If found return tvoffset, if not found return 0 */ + break; + case DICT_HASH_REMOVE: + if (tvoffset) { + /* Found, remove with -1 meaning a removed entry */ + dict->ht[idx].offset = -1; + } + /* else if not found, return 0 */ + break; + case DICT_HASH_ADD: + if (tvoffset == 0) { + /* Not found so add it at the end */ + dict->ht[idx].offset = dict->len + 1; + dict->ht[idx].hash = h; + } + /* else if found, return tvoffset */ + break; + default: + assert(tvoffset); + /* Found so replace the tvoffset */ + dict->ht[idx].offset = op_tvoffset; + break; + } + + return tvoffset; } -void DupDictInternalRep(Jim_Interp *interp, Jim_Obj *srcPtr, Jim_Obj *dupPtr) +/* Expand or create the hashtable to at least size 'size' + * The hash table size should have room for twice the number + * of keys to reduce collisions + */ +static void JimDictExpandHashTable(Jim_Dict *dict, unsigned int size) { - Jim_HashTable *ht, *dupHt; - Jim_HashTableIterator htiter; - Jim_HashEntry *he; + int i; + struct JimDictHashEntry *prevht = dict->ht; + int prevsize = dict->size; - /* Create a new hash table */ - ht = srcPtr->internalRep.ptr; - dupHt = Jim_Alloc(sizeof(*dupHt)); - Jim_InitHashTable(dupHt, &JimDictHashTableType, interp); - if (ht->size != 0) - Jim_ExpandHashTable(dupHt, ht->size); - /* Copy every element from the source to the dup hash table */ - JimInitHashTableIterator(ht, &htiter); - while ((he = Jim_NextHashEntry(&htiter)) != NULL) { - Jim_AddHashEntry(dupHt, he->key, he->u.val); + dict->size = JimHashTableNextPower(size); + dict->sizemask = dict->size - 1; + + /* Allocate a new table so that we don't need to recalulate hashes */ + dict->ht = Jim_Alloc(dict->size * sizeof(*dict->ht)); + memset(dict->ht, 0, dict->size * sizeof(*dict->ht)); + + /* Now add all the table entries to the new table */ + for (i = 0; i < prevsize; i++) { + if (prevht[i].offset > 0) { + /* Find the location in the new table for this entry */ + unsigned h = prevht[i].hash; + unsigned idx = h & dict->sizemask; + unsigned peturb = h; + + while (dict->ht[idx].offset) { + peturb >>= 5; + idx = (5 * idx + 1 + peturb) & dict->sizemask; + } + dict->ht[idx].offset = prevht[i].offset; + dict->ht[idx].hash = h; + } } + Jim_Free(prevht); +} - dupPtr->internalRep.ptr = dupHt; - dupPtr->typePtr = &dictObjType; +/** + * Add an entry to the hash table for 'keyObjPtr' + * If the entry already exists, returns the current tvoffset. + * Otherwise inserts a new entry with table value offset dict->len + 1 + * and returns 0. + */ +static int JimDictAdd(Jim_Dict *dict, Jim_Obj *keyObjPtr) +{ + /* If we are trying to add an entry and the hash table is too small, + * increase the size now, even if it may exist and the add would + * do nothing. + * This way we don't need to recalculate the hash index in case + * it didn't exist and is added. + */ + if (dict->size <= dict->len) { + /* The first add grows the size to 8, and thereafter it is doubled + * in size. Note that hash table sizes are always powers of two. + */ + JimDictExpandHashTable(dict, dict->size ? dict->size * 2 : 8); + } + return JimDictHashFind(dict, keyObjPtr, DICT_HASH_ADD); } -static Jim_Obj **JimDictPairs(Jim_Obj *dictPtr, int *len) +/** + * Allocate and return a new Jim_Dict structure + * with space for 'table_size' (key, object) entries + * and hash table size 'ht_size' + * These can be 0. + */ +static Jim_Dict *JimDictNew(Jim_Interp *interp, int table_size, int ht_size) { - Jim_HashTable *ht; - Jim_HashTableIterator htiter; - Jim_HashEntry *he; - Jim_Obj **objv; + Jim_Dict *dict = Jim_Alloc(sizeof(*dict)); + memset(dict, 0, sizeof(*dict)); + + if (ht_size) { + JimDictExpandHashTable(dict, ht_size); + } + if (table_size) { + dict->table = Jim_Alloc(table_size * sizeof(*dict->table)); + dict->maxLen = table_size; + } +#ifdef JIM_RANDOMISE_HASH + /* This is initialised to a random value to avoid a hash collision attack. + * See: n.runs-SA-2011.004 + */ + dict->uniq = (rand() ^ time(NULL) ^ clock()); +#endif + return dict; +} + +static void FreeDictInternalRep(Jim_Interp *interp, Jim_Obj *objPtr) +{ + JimFreeDict(interp, objPtr->internalRep.dictValue); +} + +static void DupDictInternalRep(Jim_Interp *interp, Jim_Obj *srcPtr, Jim_Obj *dupPtr) +{ + Jim_Dict *oldDict = srcPtr->internalRep.dictValue; int i; - ht = dictPtr->internalRep.ptr; + /* Create a new hash table */ + Jim_Dict *newDict = JimDictNew(interp, oldDict->maxLen, oldDict->size); - /* Turn the hash table into a flat vector of Jim_Objects. */ - objv = Jim_Alloc((ht->used * 2) * sizeof(Jim_Obj *)); - JimInitHashTableIterator(ht, &htiter); - i = 0; - while ((he = Jim_NextHashEntry(&htiter)) != NULL) { - objv[i++] = Jim_GetHashEntryKey(he); - objv[i++] = Jim_GetHashEntryVal(he); + /* Copy the table of key and value objects, incrementing the reference count of both */ + for (i = 0; i < oldDict->len; i++) { + newDict->table[i] = oldDict->table[i]; + Jim_IncrRefCount(newDict->table[i]); } - *len = i; - return objv; + newDict->len = oldDict->len; + + /* Must keep the same uniq so that the hashes agree */ + newDict->uniq = oldDict->uniq; + + /* Now copy the the hash table efficiently */ + memcpy(newDict->ht, oldDict->ht, sizeof(*oldDict->ht) * oldDict->size); + + dupPtr->internalRep.dictValue = newDict; + dupPtr->typePtr = &dictObjType; } static void UpdateStringOfDict(struct Jim_Obj *objPtr) { - /* Turn the hash table into a flat vector of Jim_Objects. */ - int len; - Jim_Obj **objv = JimDictPairs(objPtr, &len); - - /* And now generate the string rep as a list */ - JimMakeListStringRep(objPtr, objv, len); - - Jim_Free(objv); + JimMakeListStringRep(objPtr, objPtr->internalRep.dictValue->table, objPtr->internalRep.dictValue->len); } static int SetDictFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) @@ -7257,35 +7433,57 @@ static int SetDictFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) if (Jim_IsList(objPtr) && Jim_IsShared(objPtr)) { /* A shared list, so get the string representation now to avoid - * changing the order in case of fast conversion to dict. + * losing duplicate keys from the string rep when converting to + * a dict. */ Jim_String(objPtr); } - /* For simplicity, convert a non-list object to a list and then to a dict */ + /* Convert a non-list object to a list and then to a dict + * since we will need the list of key, value pairs anyway + */ listlen = Jim_ListLength(interp, objPtr); if (listlen % 2) { Jim_SetResultString(interp, "missing value to go with key", -1); return JIM_ERR; } else { - /* Converting from a list to a dict can't fail */ - Jim_HashTable *ht; + /* Allocate space in the hash table for twice the number of elements */ + Jim_Dict *dict = JimDictNew(interp, 0, listlen); int i; - ht = Jim_Alloc(sizeof(*ht)); - Jim_InitHashTable(ht, &JimDictHashTableType, interp); + /* Take ownership of the list array */ + dict->table = objPtr->internalRep.listValue.ele; + dict->maxLen = objPtr->internalRep.listValue.maxLen; + /* Now add all the elements to the hash table */ for (i = 0; i < listlen; i += 2) { - Jim_Obj *keyObjPtr = Jim_ListGetIndex(interp, objPtr, i); - Jim_Obj *valObjPtr = Jim_ListGetIndex(interp, objPtr, i + 1); - - Jim_ReplaceHashEntry(ht, keyObjPtr, valObjPtr); + int tvoffset = JimDictAdd(dict, dict->table[i]); + if (tvoffset) { + /* A duplicate key, so replace the value but and don't add a new entry */ + /* Discard the old value */ + Jim_DecrRefCount(interp, dict->table[tvoffset]); + /* Set the new value */ + dict->table[tvoffset] = dict->table[i + 1]; + /* Discard the duplicate key */ + Jim_DecrRefCount(interp, dict->table[i]); + } + else { + if (dict->len != i) { + /* Need to move later entries down to fill the hole created by + * a previous duplicate entry. + */ + dict->table[dict->len++] = dict->table[i]; + dict->table[dict->len++] = dict->table[i + 1]; + } + else { + dict->len += 2; + } + } } - Jim_FreeIntRep(interp, objPtr); objPtr->typePtr = &dictObjType; - objPtr->internalRep.ptr = ht; + objPtr->internalRep.dictValue = dict; return JIM_OK; } @@ -7302,13 +7500,62 @@ static int SetDictFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) static int DictAddElement(Jim_Interp *interp, Jim_Obj *objPtr, Jim_Obj *keyObjPtr, Jim_Obj *valueObjPtr) { - Jim_HashTable *ht = objPtr->internalRep.ptr; + Jim_Dict *dict = objPtr->internalRep.dictValue; + if (valueObjPtr == NULL) { + /* Removing an entry */ + int tvoffset = JimDictHashFind(dict, keyObjPtr, DICT_HASH_REMOVE); + if (tvoffset) { + /* Found, so we need to remove the value from the table too, and if it is not the last + * entry, need to swap with the last entry + */ + /* Remove the table entries */ + Jim_DecrRefCount(interp, dict->table[tvoffset - 1]); + Jim_DecrRefCount(interp, dict->table[tvoffset]); + dict->len -= 2; + if (tvoffset != dict->len + 1) { + /* Swap the last pair of table entries into the now empty entries */ + dict->table[tvoffset - 1] = dict->table[dict->len]; + dict->table[tvoffset] = dict->table[dict->len + 1]; + + /* Now we need to update the hash table for the swapped entry */ + JimDictHashFind(dict, dict->table[tvoffset - 1], tvoffset); + } + return JIM_OK; + } + return JIM_ERR; + } + else { + /* Adding an entry - does it already exist? */ + int tvoffset = JimDictAdd(dict, keyObjPtr); + if (tvoffset) { + /* Yes, already exists, so just replace value entry in the table */ + Jim_IncrRefCount(valueObjPtr); + Jim_DecrRefCount(interp, dict->table[tvoffset]); + dict->table[tvoffset] = valueObjPtr; + } + else { + /* No, so need to make space in the table + * and insert this entry at dict->len, dict->len + 1 + */ + if (dict->maxLen == dict->len) { + /* Expand the table */ + if (dict->maxLen < 4) { + dict->maxLen = 4; + } + else { + dict->maxLen *= 2; + } + dict->table = Jim_Realloc(dict->table, dict->maxLen * sizeof(*dict->table)); + } + Jim_IncrRefCount(keyObjPtr); + Jim_IncrRefCount(valueObjPtr); + + dict->table[dict->len++] = keyObjPtr; + dict->table[dict->len++] = valueObjPtr; - if (valueObjPtr == NULL) { /* unset */ - return Jim_DeleteHashEntry(ht, keyObjPtr); + } + return JIM_OK; } - Jim_ReplaceHashEntry(ht, keyObjPtr, valueObjPtr); - return JIM_OK; } /* Add an element, higher-level interface for DictAddElement(). @@ -7334,8 +7581,8 @@ Jim_Obj *Jim_NewDictObj(Jim_Interp *interp, Jim_Obj *const *elements, int len) objPtr = Jim_NewObj(interp); objPtr->typePtr = &dictObjType; objPtr->bytes = NULL; - objPtr->internalRep.ptr = Jim_Alloc(sizeof(Jim_HashTable)); - Jim_InitHashTable(objPtr->internalRep.ptr, &JimDictHashTableType, interp); + + objPtr->internalRep.dictValue = JimDictNew(interp, len, len); for (i = 0; i < len; i += 2) DictAddElement(interp, objPtr, elements[i], elements[i + 1]); return objPtr; @@ -7349,37 +7596,52 @@ Jim_Obj *Jim_NewDictObj(Jim_Interp *interp, Jim_Obj *const *elements, int len) int Jim_DictKey(Jim_Interp *interp, Jim_Obj *dictPtr, Jim_Obj *keyPtr, Jim_Obj **objPtrPtr, int flags) { - Jim_HashEntry *he; - Jim_HashTable *ht; + int tvoffset; + Jim_Dict *dict; if (SetDictFromAny(interp, dictPtr) != JIM_OK) { return -1; } - ht = dictPtr->internalRep.ptr; - if ((he = Jim_FindHashEntry(ht, keyPtr)) == NULL) { + dict = dictPtr->internalRep.dictValue; + tvoffset = JimDictHashFind(dict, keyPtr, DICT_HASH_FIND); + if (tvoffset == 0) { if (flags & JIM_ERRMSG) { Jim_SetResultFormatted(interp, "key \"%#s\" not known in dictionary", keyPtr); } return JIM_ERR; } - else { - *objPtrPtr = Jim_GetHashEntryVal(he); - return JIM_OK; - } + *objPtrPtr = dict->table[tvoffset]; + return JIM_OK; } -/* Return an allocated array of key/value pairs for the dictionary. Stores the length in *len */ -int Jim_DictPairs(Jim_Interp *interp, Jim_Obj *dictPtr, Jim_Obj ***objPtrPtr, int *len) +/* Return the key/value pairs array for the dictionary. Stores the length in *len + * + * Note that the point is to the internal table, so is only + * valid until the dict is next modified, and the result should + * not be freed. + * + * Returns NULL if the object can't be converted to a dictionary, or if the length is 0. + */ +Jim_Obj **Jim_DictPairs(Jim_Interp *interp, Jim_Obj *dictPtr, int *len) { + /* If it is a list with an even number of elements, no need to convert to dict first */ + if (Jim_IsList(dictPtr)) { + Jim_Obj **table; + JimListGetElements(interp, dictPtr, len, &table); + if (*len % 2 == 0) { + return table; + } + /* Otherwise fall through to get the standard error */ + } if (SetDictFromAny(interp, dictPtr) != JIM_OK) { - return JIM_ERR; + /* Make sure we can differentiate between an empty dict/list and bad length */ + *len = 1; + return NULL; } - *objPtrPtr = JimDictPairs(dictPtr, len); - - return JIM_OK; + *len = dictPtr->internalRep.dictValue->len; + return dictPtr->internalRep.dictValue->table; } - /* Return the value associated to the specified dict keys */ int Jim_DictKeysVector(Jim_Interp *interp, Jim_Obj *dictPtr, Jim_Obj *const *keyv, int keyc, Jim_Obj **objPtrPtr, int flags) @@ -14143,30 +14405,32 @@ static int Jim_RenameCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *a */ int Jim_DictMatchTypes(Jim_Interp *interp, Jim_Obj *objPtr, Jim_Obj *patternObj, int match_type, int return_types) { - Jim_HashEntry *he; Jim_Obj *listObjPtr; - Jim_HashTableIterator htiter; + Jim_Dict *dict; + int i; if (SetDictFromAny(interp, objPtr) != JIM_OK) { return JIM_ERR; } + dict = objPtr->internalRep.dictValue; listObjPtr = Jim_NewListObj(interp, NULL, 0); - JimInitHashTableIterator(objPtr->internalRep.ptr, &htiter); - while ((he = Jim_NextHashEntry(&htiter)) != NULL) { + for (i = 0; i < dict->len; i += 2 ) { + Jim_Obj *keyObj = dict->table[i]; + Jim_Obj *valObj = dict->table[i + 1]; if (patternObj) { - Jim_Obj *matchObj = (match_type == JIM_DICTMATCH_KEYS) ? (Jim_Obj *)he->key : Jim_GetHashEntryVal(he); + Jim_Obj *matchObj = (match_type == JIM_DICTMATCH_KEYS) ? keyObj : valObj; if (!Jim_StringMatchObj(interp, patternObj, matchObj, 0)) { /* no match */ continue; } } if (return_types & JIM_DICTMATCH_KEYS) { - Jim_ListAppendElement(interp, listObjPtr, (Jim_Obj *)he->key); + Jim_ListAppendElement(interp, listObjPtr, keyObj); } if (return_types & JIM_DICTMATCH_VALUES) { - Jim_ListAppendElement(interp, listObjPtr, Jim_GetHashEntryVal(he)); + Jim_ListAppendElement(interp, listObjPtr, valObj); } } @@ -14179,7 +14443,7 @@ int Jim_DictSize(Jim_Interp *interp, Jim_Obj *objPtr) if (SetDictFromAny(interp, objPtr) != JIM_OK) { return -1; } - return ((Jim_HashTable *)objPtr->internalRep.ptr)->used; + return objPtr->internalRep.dictValue->len / 2; } /** @@ -14196,18 +14460,20 @@ Jim_Obj *Jim_DictMerge(Jim_Interp *interp, int objc, Jim_Obj *const *objv) /* Note that we don't optimise the trivial case of a single argument */ for (i = 0; i < objc; i++) { - Jim_HashTable *ht; - Jim_HashTableIterator htiter; - Jim_HashEntry *he; + Jim_Obj **table; + int tablelen; + int j; - if (SetDictFromAny(interp, objv[i]) != JIM_OK) { + /* If the object is a list, avoid converting to a dictionary as + * we may mishandle duplicate keys + */ + table = Jim_DictPairs(interp, objv[i], &tablelen); + if (tablelen && !table) { Jim_FreeNewObj(interp, objPtr); return NULL; } - ht = objv[i]->internalRep.ptr; - JimInitHashTableIterator(ht, &htiter); - while ((he = Jim_NextHashEntry(&htiter)) != NULL) { - Jim_ReplaceHashEntry(objPtr->internalRep.ptr, Jim_GetHashEntryKey(he), Jim_GetHashEntryVal(he)); + for (j = 0; j < tablelen; j += 2) { + DictAddElement(interp, objPtr, table[j], table[j + 1]); } } return objPtr; @@ -14215,50 +14481,19 @@ Jim_Obj *Jim_DictMerge(Jim_Interp *interp, int objc, Jim_Obj *const *objv) int Jim_DictInfo(Jim_Interp *interp, Jim_Obj *objPtr) { - Jim_HashTable *ht; - unsigned int i; char buffer[100]; - int sum = 0; - int nonzero_count = 0; Jim_Obj *output; - int bucket_counts[11] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + Jim_Dict *dict; if (SetDictFromAny(interp, objPtr) != JIM_OK) { return JIM_ERR; } - ht = (Jim_HashTable *)objPtr->internalRep.ptr; + dict = objPtr->internalRep.dictValue; /* Note that this uses internal knowledge of the hash table */ - snprintf(buffer, sizeof(buffer), "%d entries in table, %d buckets\n", ht->used, ht->size); + snprintf(buffer, sizeof(buffer), "%d entries in table, %d buckets", dict->len, dict->size); output = Jim_NewStringObj(interp, buffer, -1); - - for (i = 0; i < ht->size; i++) { - Jim_HashEntry *he = ht->table[i]; - int entries = 0; - while (he) { - entries++; - he = he->next; - } - if (entries > 9) { - bucket_counts[10]++; - } - else { - bucket_counts[entries]++; - } - if (entries) { - sum += entries; - nonzero_count++; - } - } - for (i = 0; i < 10; i++) { - snprintf(buffer, sizeof(buffer), "number of buckets with %d entries: %d\n", i, bucket_counts[i]); - Jim_AppendString(interp, output, buffer, -1); - } - snprintf(buffer, sizeof(buffer), "number of buckets with 10 or more entries: %d\n", bucket_counts[10]); - Jim_AppendString(interp, output, buffer, -1); - snprintf(buffer, sizeof(buffer), "average search distance for entry: %.1f", nonzero_count ? (double)sum / nonzero_count : 0.0); - Jim_AppendString(interp, output, buffer, -1); Jim_SetResult(interp, output); return JIM_OK; } @@ -14291,12 +14526,12 @@ static int JimDictWith(Jim_Interp *interp, Jim_Obj *dictVarName, Jim_Obj *const return JIM_ERR; } /* Set the local variables */ - if (Jim_DictPairs(interp, objPtr, &dictValues, &len) == JIM_ERR) { + dictValues = Jim_DictPairs(interp, objPtr, &len); + if (len && dictValues == NULL) { return JIM_ERR; } for (i = 0; i < len; i += 2) { if (Jim_SetVariable(interp, dictValues[i], dictValues[i + 1]) == JIM_ERR) { - Jim_Free(dictValues); return JIM_ERR; } } @@ -14323,8 +14558,6 @@ static int JimDictWith(Jim_Interp *interp, Jim_Obj *dictVarName, Jim_Obj *const } } - Jim_Free(dictValues); - return ret; } diff --git a/jim.h b/jim.h index ad66b16..a1e4c46 100644 --- a/jim.h +++ b/jim.h @@ -236,6 +236,8 @@ typedef struct Jim_HashTableIterator { (entry)->u.val = (_val_); \ } while(0) +#define Jim_SetHashIntVal(ht, entry, _val_) (entry)->u.intval = (_val_) + #define Jim_FreeEntryKey(ht, entry) \ if ((ht)->type->keyDestructor) \ (ht)->type->keyDestructor((ht)->privdata, (entry)->key) @@ -256,6 +258,7 @@ typedef struct Jim_HashTableIterator { #define Jim_GetHashEntryKey(he) ((he)->key) #define Jim_GetHashEntryVal(he) ((he)->u.val) +#define Jim_GetHashEntryIntVal(he) ((he)->u.intval) #define Jim_GetHashTableCollisions(ht) ((ht)->collisions) #define Jim_GetHashTableSize(ht) ((ht)->size) #define Jim_GetHashTableUsed(ht) ((ht)->used) @@ -318,6 +321,8 @@ typedef struct Jim_Obj { int len; /* Length */ int maxLen; /* Allocated 'ele' length */ } listValue; + /* dict object */ + struct Jim_Dict *dictValue; /* String type */ struct { int maxLength; @@ -455,7 +460,22 @@ typedef int Jim_CmdProc(struct Jim_Interp *interp, int argc, Jim_Obj *const *argv); typedef void Jim_DelCmdProc(struct Jim_Interp *interp, void *privData); - +/* The dict structure. It uses the same approach as Python OrderedDict + * of storing a hash table of table offsets into a table containing keys and objects. + * This preserves order when adding and replacing elements. + */ +typedef struct Jim_Dict { + struct JimDictHashEntry { + int offset; + unsigned hash; + } *ht; /* Allocated hash table of size 'size' */ + unsigned int size; /* Size of the hash table (0 or power of two) */ + unsigned int sizemask; /* mask to apply to hash to index into offsets table */ + unsigned int uniq; /* unique value to add to hash generator */ + Jim_Obj **table; /* Table of alternating key, value elements */ + int len; /* Number of used elements in table */ + int maxLen; /* Allocated length of table */ +} Jim_Dict; /* A command is implemented in C if isproc is 0, otherwise * it is a Tcl procedure with the arglist and body represented by the @@ -799,8 +819,8 @@ JIM_EXPORT int Jim_DictKeysVector (Jim_Interp *interp, JIM_EXPORT int Jim_SetDictKeysVector (Jim_Interp *interp, Jim_Obj *varNamePtr, Jim_Obj *const *keyv, int keyc, Jim_Obj *newObjPtr, int flags); -JIM_EXPORT int Jim_DictPairs(Jim_Interp *interp, - Jim_Obj *dictPtr, Jim_Obj ***objPtrPtr, int *len); +JIM_EXPORT Jim_Obj **Jim_DictPairs(Jim_Interp *interp, + Jim_Obj *dictPtr, int *len); JIM_EXPORT int Jim_DictAddElement(Jim_Interp *interp, Jim_Obj *objPtr, Jim_Obj *keyObjPtr, Jim_Obj *valueObjPtr); diff --git a/jim_tcl.txt b/jim_tcl.txt index 25e2130..2a60a3c 100644 --- a/jim_tcl.txt +++ b/jim_tcl.txt @@ -64,6 +64,7 @@ Changes between 0.78 and 0.79 8. `regsub` now fully supports +{backslash}A+ 9. Add `socket pty` to create a pseudo-tty pair 10. Null characters (\x00) are now supported in variable and proc names +11. dictionaries and arrays now preserve insertion order, matching Tcl and the documentation Changes between 0.77 and 0.78 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ diff --git a/tests/array.test b/tests/array.test index 38494de..7581de2 100644 --- a/tests/array.test +++ b/tests/array.test @@ -111,7 +111,7 @@ test array-1.19 "array unset non-array" -body { test array-1.20 "array stat" -body { set output [array stat a] - regexp "1 entries in table.*number of buckets with 1 entries: 1" $output + regexp "entries in table.*buckets" $output } -result {1} test array-1.21 "array stat non-array" -body { diff --git a/tests/dict.test b/tests/dict.test index c0528e8..4dcf4f4 100644 --- a/tests/dict.test +++ b/tests/dict.test @@ -249,4 +249,40 @@ test dict-24.4 {dict/list shimmering with lappend and foreach} { llength $a } 12 +# As of 0.79, dicts maintain insertion order +test dict-25.1 {dict ordering} { + dict keys {a x 0 y} +} {a 0} + +test dict-25.2 {dict ordering} { + dict keys {0 x a y} +} {0 a} + +test dict-25.3 {dict ordering} { + set d [dict create a y 0 x 2 z] + dict set d 1 w + dict keys $d +} {a 0 2 1} + +test dict-25.3 {dict ordering} { + set d [dict create a y 0 x 2 z] + dict set d 0 w + dict keys $d +} {a 0 2} + +test dict-25.4 {removal of keys that hash earlier} { + set parsed {formPost {text {This is text.} {text file} Hello. {image file} abc}} + + dict unset parsed formPost text + dict unset parsed formPost {image file} + dict get $parsed formPost {text file} +} Hello. + +test dict-25.5 {list to dict, duplicate keys} { + set l [list a 1 a 2 a 3] + # make sure there is no string rep + lappend l b 4 + dict get $l a +} {3} + testreport diff --git a/tests/dict2.test b/tests/dict2.test index ddb545c..493cf91 100644 --- a/tests/dict2.test +++ b/tests/dict2.test @@ -1273,7 +1273,7 @@ test dict-23.4 {dict with usage} -body { test dict-23.5 {dict with badvar} -constraints jim -body { dict with dictnulls {lsort [info locals]} -} -returnCodes ok -result [list \0ghi kl\0m ab\0c de\0f] +} -returnCodes ok -result [list ab\0c de\0f \0ghi kl\0m] test dict-23.6 {dict with baddict} -body { dict with dictbad {} diff --git a/tests/runall.tcl b/tests/runall.tcl index 4dfa539..57f6399 100644 --- a/tests/runall.tcl +++ b/tests/runall.tcl @@ -55,7 +55,9 @@ if {[info commands interp] eq ""} { # Extract the counts foreach var {pass fail skip tests} { - incr total($var) [$i eval "set testinfo(num$var)"] + catch { + incr total($var) [$i eval "set testinfo(num$var)"] + } } $i delete } -- 2.11.4.GIT