summaryrefslogtreecommitdiffstats
path: root/doc
diff options
context:
space:
mode:
authordkf <donal.k.fellows@manchester.ac.uk>2007-11-20 20:43:08 (GMT)
committerdkf <donal.k.fellows@manchester.ac.uk>2007-11-20 20:43:08 (GMT)
commit69ece03dc014b44e93da9576bb02d060b202013b (patch)
treeb18999bb6907a1311f4eb7808445c05911198c15 /doc
parent0500cb0762976df7a95232b162dbb09d7876d0ea (diff)
downloadtcl-69ece03dc014b44e93da9576bb02d060b202013b.zip
tcl-69ece03dc014b44e93da9576bb02d060b202013b.tar.gz
tcl-69ece03dc014b44e93da9576bb02d060b202013b.tar.bz2
* generic/tclDictObj.c: Changed the underlying implementation of the
hash table used in dictionaries to additionally keep all entries in the hash table in a linked list, which is only ever added to at the end. This makes iteration over all entries in the dictionary in key insertion order a trivial operation, and so cleans up a great deal of complexity relating to dictionary representation and stability of iteration order.
Diffstat (limited to 'doc')
-rw-r--r--doc/DictObj.316
-rw-r--r--doc/dict.n31
2 files changed, 24 insertions, 23 deletions
diff --git a/doc/DictObj.3 b/doc/DictObj.3
index 20d3514..4e72a1c 100644
--- a/doc/DictObj.3
+++ b/doc/DictObj.3
@@ -4,7 +4,7 @@
'\" See the file "license.terms" for information on usage and redistribution
'\" of this file, and for a DISCLAIMER OF ALL WARRANTIES.
'\"
-'\" RCS: @(#) $Id: DictObj.3,v 1.9 2007/06/29 22:37:27 dkf Exp $
+'\" RCS: @(#) $Id: DictObj.3,v 1.10 2007/11/20 20:43:11 dkf Exp $
'\"
.so man.macros
.TH Tcl_DictObj 3 8.5 Tcl "Tcl Library Procedures"
@@ -99,9 +99,14 @@ sub-dictionaries of the main dictionary object passed to them.
.SH DESCRIPTION
.PP
Tcl dictionary objects have an internal representation that supports
-efficient mapping from keys to values and which does not guarantee any
-particular ordering of keys within the dictionary (the underlying
-basic data-structure is a hash table created with \fBTcl_InitObjHashTable\fR).
+efficient mapping from keys to values and which guarantees that the
+particular ordering of keys within the dictionary remains the same
+modulo any keys being deleted (which removes them from the order) or
+added (which adds them to the end of the order). If reinterpreted as a
+list, the values at the even-valued indices in the list will be the
+keys of the dictionary, and each will be followed (in the odd-valued
+index) bu the value associated with that key.
+.PP
The procedures described in this man page are used to
create, modify, index, and iterate over dictionary objects from C code.
.PP
@@ -190,7 +195,7 @@ keys must exist and have dictionaries as their values.
.SH EXAMPLE
Using the dictionary iteration interface to search determine if there
is a key that maps to itself:
-
+.PP
.CS
Tcl_DictSearch search;
Tcl_Obj *key, *value;
@@ -225,7 +230,6 @@ for (; done ; \fBTcl_DictObjNext\fR(&search, &key, &value, &done)) {
Tcl_SetObjResult(interp, Tcl_NewBooleanObj(!done));
return TCL_OK;
.CE
-
.SH "SEE ALSO"
Tcl_NewObj, Tcl_DecrRefCount, Tcl_IncrRefCount, Tcl_InitObjHashTable
.SH KEYWORDS
diff --git a/doc/dict.n b/doc/dict.n
index a1dea2c..e963f4c 100644
--- a/doc/dict.n
+++ b/doc/dict.n
@@ -4,7 +4,7 @@
'\" See the file "license.terms" for information on usage and redistribution
'\" of this file, and for a DISCLAIMER OF ALL WARRANTIES.
'\"
-'\" RCS: @(#) $Id: dict.n,v 1.15 2007/10/29 01:42:18 dkf Exp $
+'\" RCS: @(#) $Id: dict.n,v 1.16 2007/11/20 20:43:11 dkf Exp $
'\"
.so man.macros
.TH dict n 8.5 Tcl "Tcl Built-In Commands"
@@ -60,7 +60,8 @@ argument after the rule selection word is a two-element list. If the
\fIscript\fR returns with a condition of \fBTCL_BREAK\fR, no further
key/value pairs are considered for inclusion in the resulting
dictionary, and a condition of \fBTCL_CONTINUE\fR is equivalent to a false
-result. The order in which the key/value pairs are tested is undefined.
+result. The key/value pairs are tested in the order in which the keys
+were inserted into the dictionary.
.TP
\fBdict filter \fIdictionaryValue \fBvalue \fIglobPattern\fR
The value rule only matches those key/value pairs whose values match
@@ -78,7 +79,8 @@ body generates a \fBTCL_BREAK\fR result, no further pairs from the
dictionary will be iterated over and the \fBdict for\fR command will
terminate successfully immediately. If any evaluation of the body
generates a \fBTCL_CONTINUE\fR result, this shall be treated exactly like a
-normal \fBTCL_OK\fR result. The order of iteration is undefined.
+normal \fBTCL_OK\fR result. The order of iteration is the order in
+which the keys were inserted into the dictionary.
.TP
\fBdict get \fIdictionaryValue \fR?\fIkey ...\fR?
Given a dictionary value (first argument) and a key (second argument),
@@ -120,11 +122,8 @@ string produced by \fBTcl_HashStats\fR, similar to \fBarray info\fR.
\fBdict keys \fIdictionaryValue \fR?\fIglobPattern\fR?
Return a list of all keys in the given dictionary value. If a pattern
is supplied, only those keys that match it (according to the rules of
-\fBstring match\fR) will be returned. The returned keys will be in an
-arbitrary implementation-specific order, though where no pattern is
-supplied the \fIi\fR'th key returned by \fBdict keys\fR will be the key for
-the \fIi\fR'th value returned by \fBdict values\fR applied to the same
-dictionary value.
+\fBstring match\fR) will be returned. The returned keys will be in the
+order that they were inserted into the dictionary.
.TP
\fBdict lappend \fIdictionaryVariable key \fR?\fIvalue ...\fR?
This appends the given items to the list value that the given key maps
@@ -194,10 +193,8 @@ contents only happen when \fIbody\fR terminates.
Return a list of all values in the given dictionary value. If a
pattern is supplied, only those values that match it (according to the
rules of \fBstring match\fR) will be returned. The returned values
-will be in an arbitrary implementation-specific order, though where no
-pattern is supplied the \fIi\fR'th key returned by \fBdict keys\fR will be
-the key for the \fIi\fR'th value returned by \fBdict values\fR applied to
-the same dictionary value.
+will be in the order of that the keys associated with those values
+were inserted into the dictionary.
.TP
\fBdict with \fIdictionaryVariable \fR?\fIkey ...\fR? \fIbody\fR
Execute the Tcl script in \fIbody\fR with the value for each key in
@@ -215,15 +212,15 @@ dictionaries no longer exists. The result of \fBdict with\fR is
traces; changes to the \fIdictionaryVariable\fR's contents only happen
when \fIbody\fR terminates.
.SH "DICTIONARY VALUES"
-Dictionaries are values that contain an efficient (but \fInot\fR
-order-preserving) mapping from arbitrary keys to arbitrary values.
+Dictionaries are values that contain an efficient, order-preserving
+mapping from arbitrary keys to arbitrary values.
They have a textual format that is exactly that of any list with an
even number of elements, with each mapping in the dictionary being
-represented as two items in the list. When a command takes a
+represented as two items in the list. When a command takes a
dictionary and produces a new dictionary based on it (either returning
it or writing it back into the variable that the starting dictionary
-was read from) there is \fIno\fR guarantee that the new dictionary
-will have the same ordering of keys.
+was read from) the new dictionary will have the same order of keys,
+modulo any deleted keys and with new keys added on to the end.
.SH EXAMPLES
Constructing and using nested dictionaries:
.CS