* 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.

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