summaryrefslogtreecommitdiffstats
path: root/generic/tcl.h
diff options
context:
space:
mode:
authorericm <ericm>2000-07-19 22:15:28 (GMT)
committerericm <ericm>2000-07-19 22:15:28 (GMT)
commit36c983a93395d03061b02a8ac82105313991650f (patch)
treeca5b2921b3c60013f2c00545146190946b6ef5e8 /generic/tcl.h
parent8c6040fe85cad9ab5bb5452596ea1107e155f450 (diff)
downloadtcl-36c983a93395d03061b02a8ac82105313991650f.zip
tcl-36c983a93395d03061b02a8ac82105313991650f.tar.gz
tcl-36c983a93395d03061b02a8ac82105313991650f.tar.bz2
* generic/tclStubInit.c:
* generic/tclObj.c: * generic/tclInt.h: * generic/tclHash.c: * generic/tclDecls.h: * generic/tcl.h: * generic/tcl.decls: * doc/Hash.3: Applied patch from Paul Duffin to extend hash tables to allow custom key types, such as Tcl_Obj *'s, and others.
Diffstat (limited to 'generic/tcl.h')
-rw-r--r--generic/tcl.h184
1 files changed, 160 insertions, 24 deletions
diff --git a/generic/tcl.h b/generic/tcl.h
index ed6c2ac..2add458 100644
--- a/generic/tcl.h
+++ b/generic/tcl.h
@@ -12,7 +12,7 @@
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tcl.h,v 1.72 2000/06/24 00:26:08 ericm Exp $
+ * RCS: @(#) $Id: tcl.h,v 1.73 2000/07/19 22:15:29 ericm Exp $
*/
#ifndef _TCL
@@ -337,6 +337,14 @@ typedef long LONG;
#endif
/*
+ * This flag controls whether binary compatability is maintained with
+ * extensions built against a previous version of Tcl.
+ */
+#ifndef TCL_PRESERVE_BINARY_COMPATABILITY
+#define TCL_PRESERVE_BINARY_COMPATABILITY 1
+#endif
+
+/*
* Data structures defined opaquely in this module. The definitions below
* just provide dummy types. A few fields are made visible in Tcl_Interp
* structures, namely those used for returning a string result from
@@ -942,13 +950,30 @@ typedef struct Tcl_DString {
#define TCL_LINK_READ_ONLY 0x80
/*
- * Forward declaration of Tcl_HashTable. Needed by some C++ compilers
- * to prevent errors when the forward reference to Tcl_HashTable is
- * encountered in the Tcl_HashEntry structure.
+ * Forward declarations of Tcl_HashTable and related types.
*/
-#ifdef __cplusplus
-struct Tcl_HashTable;
+typedef struct Tcl_HashKeyType Tcl_HashKeyType;
+typedef struct Tcl_HashTable Tcl_HashTable;
+typedef struct Tcl_HashEntry Tcl_HashEntry;
+
+typedef unsigned int (Tcl_HashKeyProc) _ANSI_ARGS_((Tcl_HashTable *tablePtr,
+ VOID *keyPtr));
+typedef int (Tcl_CompareHashKeysProc) _ANSI_ARGS_((VOID *keyPtr,
+ Tcl_HashEntry *hPtr));
+typedef Tcl_HashEntry *(Tcl_AllocHashEntryProc) _ANSI_ARGS_((
+ Tcl_HashTable *tablePtr, VOID *keyPtr));
+typedef void (Tcl_FreeHashEntryProc) _ANSI_ARGS_((Tcl_HashEntry *hPtr));
+
+/*
+ * This flag controls whether the hash table stores the hash of a key, or
+ * recalculates it. There should be no reason for turning this flag off
+ * as it is completely binary and source compatible unless you directly
+ * access the bucketPtr member of the Tcl_HashTableEntry structure. This
+ * member has been removed and the space used to store the hash value.
+ */
+#ifndef TCL_HASH_KEY_STORE_HASH
+#define TCL_HASH_KEY_STORE_HASH 1
#endif
/*
@@ -957,14 +982,25 @@ struct Tcl_HashTable;
* defined below.
*/
-typedef struct Tcl_HashEntry {
- struct Tcl_HashEntry *nextPtr; /* Pointer to next entry in this
+struct Tcl_HashEntry {
+ Tcl_HashEntry *nextPtr; /* Pointer to next entry in this
* hash bucket, or NULL for end of
* chain. */
- struct Tcl_HashTable *tablePtr; /* Pointer to table containing entry. */
- struct Tcl_HashEntry **bucketPtr; /* Pointer to bucket that points to
+ Tcl_HashTable *tablePtr; /* Pointer to table containing entry. */
+#if TCL_HASH_KEY_STORE_HASH
+# if TCL_PRESERVE_BINARY_COMPATABILITY
+ VOID *hash; /* Hash value, stored as pointer to
+ * ensure that the offsets of the
+ * fields in this structure are not
+ * changed. */
+# else
+ unsigned int hash; /* Hash value. */
+# endif
+#else
+ Tcl_HashEntry **bucketPtr; /* Pointer to bucket that points to
* first entry in this entry's chain:
* used for deleting the entry. */
+#endif
ClientData clientData; /* Application stores something here
* with Tcl_SetHashValue. */
union { /* Key has one of these forms: */
@@ -978,16 +1014,72 @@ typedef struct Tcl_HashEntry {
* will be as large as needed to hold
* the key. */
} key; /* MUST BE LAST FIELD IN RECORD!! */
-} Tcl_HashEntry;
+};
/*
+ * Flags used in Tcl_HashKeyType.
+ *
+ * TCL_HASH_KEY_RANDOMIZE_HASH:
+ * There are some things, pointers for example
+ * which don't hash well because they do not use
+ * the lower bits. If this flag is set then the
+ * hash table will attempt to rectify this by
+ * randomising the bits and then using the upper
+ * N bits as the index into the table.
+ */
+#define TCL_HASH_KEY_RANDOMIZE_HASH 0x1
+
+/*
+ * Structure definition for the methods associated with a hash table
+ * key type.
+ */
+#define TCL_HASH_KEY_TYPE_VERSION 1
+struct Tcl_HashKeyType {
+ int version; /* Version of the table. If this structure is
+ * extended in future then the version can be
+ * used to distinguish between different
+ * structures.
+ */
+
+ int flags; /* Flags, see above for details. */
+
+ /* Calculates a hash value for the key. If this is NULL then the pointer
+ * itself is used as a hash value.
+ */
+ Tcl_HashKeyProc *hashKeyProc;
+
+ /* Compares two keys and returns zero if they do not match, and non-zero
+ * if they do. If this is NULL then the pointers are compared.
+ */
+ Tcl_CompareHashKeysProc *compareKeysProc;
+
+ /* Called to allocate memory for a new entry, i.e. if the key is a
+ * string then this could allocate a single block which contains enough
+ * space for both the entry and the string. Only the key field of the
+ * allocated Tcl_HashEntry structure needs to be filled in. If something
+ * else needs to be done to the key, i.e. incrementing a reference count
+ * then that should be done by this function. If this is NULL then Tcl_Alloc
+ * is used to allocate enough space for a Tcl_HashEntry and the key pointer
+ * is assigned to key.oneWordValue.
+ */
+ Tcl_AllocHashEntryProc *allocEntryProc;
+
+ /* Called to free memory associated with an entry. If something else needs
+ * to be done to the key, i.e. decrementing a reference count then that
+ * should be done by this function. If this is NULL then Tcl_Free is used
+ * to free the Tcl_HashEntry.
+ */
+ Tcl_FreeHashEntryProc *freeEntryProc;
+};
+
+/*
* Structure definition for a hash table. Must be in tcl.h so clients
* can allocate space for these structures, but clients should never
* access any fields in this structure.
*/
#define TCL_SMALL_HASH_TABLE 4
-typedef struct Tcl_HashTable {
+struct Tcl_HashTable {
Tcl_HashEntry **buckets; /* Pointer to bucket array. Each
* element points to first entry in
* bucket's hash chain, or NULL. */
@@ -1006,16 +1098,20 @@ typedef struct Tcl_HashTable {
int mask; /* Mask value used in hashing
* function. */
int keyType; /* Type of keys used in this table.
- * It's either TCL_OBJ_KEYS,
+ * It's either TCL_CUSTOM_KEYS,
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS,
* or an integer giving the number of
* ints that is the size of the key.
*/
- Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
+#if TCL_PRESERVE_BINARY_COMPATABILITY
+ Tcl_HashEntry *(*findProc) _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
- Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
+ Tcl_HashEntry *(*createProc) _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
-} Tcl_HashTable;
+#endif
+ Tcl_HashKeyType *typePtr; /* Type of the keys used in the
+ * Tcl_HashTable. */
+};
/*
* Structure definition for information used to keep track of searches
@@ -1032,35 +1128,75 @@ typedef struct Tcl_HashSearch {
/*
* Acceptable key types for hash tables:
+ *
+ * TCL_STRING_KEYS: The keys are strings, they are copied into
+ * the entry.
+ * TCL_ONE_WORD_KEYS: The keys are pointers, the pointer is stored
+ * in the entry.
+ * TCL_CUSTOM_TYPE_KEYS: The keys are arbitrary types which are copied
+ * into the entry.
+ * TCL_CUSTOM_PTR_KEYS: The keys are pointers to arbitrary types, the
+ * pointer is stored in the entry.
+ *
+ * While maintaining binary compatability the above have to be distinct
+ * values as they are used to differentiate between old versions of the
+ * hash table which don't have a typePtr and new ones which do. Once binary
+ * compatability is discarded in favour of making more wide spread changes
+ * TCL_STRING_KEYS can be the same as TCL_CUSTOM_TYPE_KEYS, and
+ * TCL_ONE_WORD_KEYS can be the same as TCL_CUSTOM_PTR_KEYS because they
+ * simply determine how the key is accessed from the entry and not the
+ * behaviour.
*/
-#define TCL_OBJ_KEYS -1
#define TCL_STRING_KEYS 0
#define TCL_ONE_WORD_KEYS 1
+#if TCL_PRESERVE_BINARY_COMPATABILITY
+# define TCL_CUSTOM_TYPE_KEYS -2
+# define TCL_CUSTOM_PTR_KEYS -1
+#else
+# define TCL_CUSTOM_TYPE_KEYS TCL_STRING_KEYS
+# define TCL_CUSTOM_PTR_KEYS TCL_ONE_WORD_KEYS
+#endif
+
/*
* Macros for clients to use to access fields of hash entries:
*/
#define Tcl_GetHashValue(h) ((h)->clientData)
#define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
-#define Tcl_GetHashKey(tablePtr, h) \
- ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS || \
- (tablePtr)->keyType == TCL_OBJ_KEYS) \
- ? (h)->key.oneWordValue \
- : (h)->key.string))
+#if TCL_PRESERVE_BINARY_COMPATABILITY
+# define Tcl_GetHashKey(tablePtr, h) \
+ ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS || \
+ (tablePtr)->keyType == TCL_CUSTOM_PTR_KEYS) \
+ ? (h)->key.oneWordValue \
+ : (h)->key.string))
+#else
+# define Tcl_GetHashKey(tablePtr, h) \
+ ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) \
+ ? (h)->key.oneWordValue \
+ : (h)->key.string))
+#endif
/*
* Macros to use for clients to use to invoke find and create procedures
* for hash tables:
*/
-#define Tcl_FindHashEntry(tablePtr, key) \
+#if TCL_PRESERVE_BINARY_COMPATABILITY
+# define Tcl_FindHashEntry(tablePtr, key) \
(*((tablePtr)->findProc))(tablePtr, key)
-#define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
+# define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
(*((tablePtr)->createProc))(tablePtr, key, newPtr)
+#endif
/*
+ * Macro to use new extended version of Tcl_InitHashTable.
+ */
+#define Tcl_InitHashTable(tablePtr, keyType) \
+ Tcl_InitHashTableEx(tablePtr, keyType, NULL)
+
+/*
* Flag values to pass to Tcl_DoOneEvent to disable searches
* for some kinds of events:
*/