aboutsummaryrefslogtreecommitdiff
path: root/jim-array.c
AgeCommit message (Collapse)AuthorFilesLines
2021-01-10package: add ABI version checkingSteve Bennett1-3/+1
jim.h now includes JIM_ABI_VERSION that should be incremented whenever the ABI changes. Then all loadable modules should call Jim_CheckAbiVersion() to make sure they are loaded against the correct version. Add Jim_PackageProvideCheck() that does both Jim_CheckAbiVersion() and Jim_PackageProvide() to simplify the implementation of loadable extensions. Also rename the "big" sqlite3 extension to just sqlite to avoid a naming conflict with the smaller jim-sqlite3 extension. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2020-06-25core: dicts (and arrays) now preserve insertion orderSteve Bennett1-2/+2
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 <steveb@workware.net.au>
2016-11-14dict: Fix [dict values] with duplicate valuesSteve Bennett1-3/+2
The script implementation of dict values was not correctly handling the case where a dictionary had duplicate values. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2016-10-12Array fixes and testsEvan Hunter1-3/+8
Changed 'array exists' to actually check if the variable is an array (matches tclsh) Fix Jim_DictInfo to avoid using printf() and make output match tclsh Added some more tests for array command - checked these work with tclsh
2014-04-23array: avoid crash on unset variableSteve Bennett1-0/+5
Fix the case where the variable does not exist and a pattern is specified. Courtesy of coverity Signed-off-by: Steve Bennett <steveb@workware.net.au>
2014-01-15array: array set to non-dict should failSteve Bennett1-0/+3
Currently returns the error message but does not set JIM_ERR Also add a test case Signed-off-by: Steve Bennett <steveb@workware.net.au>
2014-01-15array: error msg for odd length array getSteve Bennett1-14/+10
Currently an error is set, but with no message Signed-off-by: Steve Bennett <steveb@workware.net.au>
2014-01-03Remove tabs from source filesSteve Bennett1-3/+2
Tabs accidentally crept into source files in violaton of the style guide Signed-off-by: Steve Bennett <steveb@workware.net.au>
2013-12-21Implement more dict sub commandsSteve Bennett1-0/+17
dict for, values, incr, append, lappend, update, replace and info Also implement array stat (the same as dict info) Note that [dict info] and [array stat] are for useful for checking the behaviour of the hash randomiser Add Jim_EvalEnsemble() Signed-off-by: Steve Bennett <steveb@workware.net.au>
2011-11-24Create build-jim-ext for building extensionsSteve Bennett1-3/+1
Simplifies the process of building loadable extensions Signed-off-by: Steve Bennett <steveb@workware.net.au>
2011-11-18Add a general purpose hashtable pattern matcherSteve Bennett1-57/+29
Invokes a callback to add elements with keys matching a pattern to a list Use for info subcommands: commands, procs, channels, globals, locals, vars Also: dict keys, array get Also avoid some dict/list conversions And simplify the implementation of array set
2011-11-07Allow building with MSVC on windowsSteve Bennett1-1/+0
Signed-off-by: Steve Bennett <steveb@workware.net.au>
2011-11-07Remove use of designated initialisersSteve Bennett1-37/+37
For better compatibility c89 compatibility. Also simplify jim-subcmd. Remove -usage and command descriptions. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2011-09-12Remove all trailing whitespace in sourceSteve Bennett1-4/+4
Signed-off-by: Steve Bennett <steveb@workware.net.au>
2011-08-03Fix commit cbeb3ea: unset missing array elementSteve Bennett1-1/+1
Although [dict unset] should not complain about being unable to unset a missing element, unset via array syntax (dict sugar) should - to be compatible with Tcl. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-12-21All Jim source should include jimautoconf.hSteve Bennett1-0/+1
This ensures that everything picks up the autoconf settings
2010-11-24Add support for [dict] size, merge, withSteve Bennett1-1/+4
Implement 'dict with' and 'dict merge' as scripts since this is simpler. Use 'dict size' to implement 'array size' Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-11-17Add UTF-8 support to JimSteve Bennett1-2/+2
Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-11-09Allow jim to be used as an autoconf subdirSteve Bennett1-1/+1
Ensure that no public headers include the autoconf header, jimautoconf.h, as it leads to problems with redefined symbols. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-20Add support for 'dict keys'Steve Bennett1-25/+1
And implement 'array names' in terms of it Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Licence wording updates.Steve Bennett1-4/+2
Per v0.51, don't refer to the FreeBSD licence Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Ensure that Tcl extensions can be built-in or externalSteve Bennett1-0/+3
All C extensions must call Jim_PackageProvide() make-c-ext ensures that Tcl extensions call Jim_PackageProvide() if compiled in. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Minor cleanups and fixesSteve Bennett1-5/+6
array get for odd length list now returns an error comment fixes and small code rearrangement Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Reduce excessive stack usageSteve Bennett1-1/+0
Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Clean up the indentation messSteve Bennett1-6/+5
Use 'indent'. Not perfect, but at least consistent. Signed-off-by: Steve Bennett <steveb@workware.net.au>
2010-10-15Many improvements, bug fixesSteve Bennett1-7/+24
*: Allow math functions to be enabled via configure *: Allow support for references to be removed *: Documentation updates *: Jim_ListLength() now returns the result directly *: Optimise list -> dict conversion *: Consistent capitalisation of some structures, functions *: Add support for abbreviations to Jim_GetEnum() *: The commands to 'info' may be abbreviated *: Use abbreviation support in parsing options to 'subst' *: Use Jim_GetEnum() to parse return code names *: Optimise 'array get', 'array set' if no conversion needed *: Import Tcl string.test *: string compare now returns -1,0,1 like Tcl *: Fix 'string last' with index=0 *: Add support for 'string reverse' *: Add -nocase option to 'string equal' *: Fix infinite loop in 'string repeat str -1' *: Support braced patterns in glob *: glob should not return dot files unless the pattern starts with . *: Simplify glob.tcl by using some new features *: When creating C extensions from Tcl, preserve newlines and invoke with Jim_Eval_Named() to produce more meaningful error messages. *: Also remove all comments, not just those starting in the first column *: Add support for 'n+n' and 'n-n' in string/list indexes (Tcl 8.5) *: Add a level to the stack trace for 'return -code error' *: 'return -code' should also affect the return from 'source' (see Tcl docs) *: Fix lsort -command *: Some systems don't have INFINITY
2010-10-15Implement 'array' in CSteve Bennett1-0/+277
generated by cgit v1.1 at 2024-07-16 17:47:49 +0000