Initial commit

1 files changed, 212 insertions, 0 deletions

diff --git a/pkg/utilities/nttools/tunits/unhash.x b/pkg/utilities/nttools/tunits/unhash.x
new file mode 100644
index 00000000..3ae9c24e
--- /dev/null
+++ b/pkg/utilities/nttools/tunits/unhash.x
@@ -0,0 +1,212 @@
+# A set of procedures that implement a generic hash table. The hash table 
+# stores the key, plus a pointer to the value structure. It should be 
+# wrapped  in a more specific set of calls that can read the value structure
+
+define	LEN_UNHSTRUCT	5
+
+define	UNH_SIZE	Memi[$1]
+define	UNH_NEXT	Memi[$1+1]
+define	UNH_KEYBUF	Memi[$1+2]
+define	UNH_VALBUF	Memi[$1+3]
+define	UNH_STRBUF	Memi[$1+4]
+
+define	UNH_KEY		Memi[UNH_KEYBUF($1)+$2]
+define	UNH_VALUE	Memi[UNH_VALBUF($1)+$2]
+
+#* HISTORY *
+#* B.Simon	07-Jan-99	Original
+
+# ADD_UNHASH -- Add a new keyword and value to the hash table
+
+procedure add_unhash (hash, keyword, value)
+
+pointer	hash		# i: Descriptor of hash table
+char	keyword[ARB]	# i: Keyword to add to hash table
+pointer	value		# i: Value descriptor
+#--
+int	index, nc
+
+string	duplicate  "Cannot add duplicate keyword to hash table"
+
+int	gstrcpy(), loc_unhash()
+
+begin
+	# Find where keyword should be inserted
+
+	index = loc_unhash (hash, keyword)
+
+	# Adding duplicate keywords is not allowed
+
+	if (UNH_KEY(hash,index) != NULL) {
+	    call tuniterr (duplicate, keyword)
+
+	} else {
+	    UNH_KEY(hash,index) = UNH_NEXT(hash)
+	    UNH_VALUE(hash,index) = value
+
+	    nc = gstrcpy (keyword, Memc[UNH_NEXT(hash)], ARB)
+	    UNH_NEXT(hash) = UNH_NEXT(hash) + nc + 1
+	}
+end
+
+# CALC_UNHASH -- Calculate hash index and step size from keyword
+
+procedure calc_unhash (hash, keyword, index, step)
+
+pointer	hash		# i: Descriptor of hash table
+char	keyword[ARB]	# i: Keyword to search for in hash table
+int	index		# o: Location to place keyword at in hash
+int	step		# o: Step size in case location is filled
+#--
+int	ic
+
+begin
+	# Standard hash table function based on munging characters
+ 
+	index = 0
+	step = 0
+
+	for (ic = 1; keyword[ic] != EOS; ic = ic + 1) {
+	    index = 2 * index + keyword[ic]
+	    step = step + keyword[ic]
+	}
+
+	# This line ensures the step size is odd
+
+	step = step - mod (step, 2) + 1
+end
+
+# EACH_UNHASH -- Retrieve values from hash table serially
+
+int procedure each_unhash (hash, index, keyword, value, maxch)
+
+pointer	hash		# i: Descriptor of hash table
+int	index		# u: Index of next slot in hash table to examine
+char	keyword[ARB]	# o: Keyword name
+pointer	value		# o: Keyword value
+int	maxch		# i: Maximum length of keyword
+#--
+
+begin
+	while (index < UNH_SIZE(hash)) {
+	    if (UNH_KEY(hash,index) != NULL) {
+		call strcpy (Memc[UNH_KEY(hash,index)], keyword, maxch)
+		value = UNH_VALUE(hash,index)
+		index = index + 1
+		return (OK)
+	    }
+
+	    index = index + 1
+	}
+
+	return (EOF)
+end
+
+# FREE_UNHASH -- Free a hash table
+
+procedure free_unhash (hash)
+
+pointer	hash		# i: hash table descriptor
+#--
+
+begin
+	# This code assumes that all memory associated 
+	# with the values has already been freed
+
+	call mfree (UNH_STRBUF(hash), TY_CHAR)
+	call mfree (UNH_VALBUF(hash), TY_INT)
+	call mfree (UNH_KEYBUF(hash), TY_INT)
+	call mfree (hash, TY_INT)
+end
+
+# GET_UNHASH -- Return a keyword's value from a hash
+
+int procedure get_unhash (hash, keyword, value)
+
+pointer	hash		# i: Descriptor of hash table
+char	keyword[ARB]	# i: Keyword to add to hash table
+pointer	value		# o: pointer to hash table value
+#--
+int	index, status
+
+int	loc_unhash ()
+
+begin
+	# The keyword is found if its slot is not null
+
+	index = loc_unhash (hash, keyword)
+
+	if (UNH_KEY(hash,index) == NULL) {
+	    value = NULL
+	    status = NO
+	} else {
+	    value = UNH_VALUE(hash,index)
+	    status = YES
+	}
+
+	return (status)
+end
+
+# LOC_UNHASH -- Return index of location where a key should be inserted
+
+int procedure loc_unhash (hash, keyword)
+
+pointer	hash		# i: Descriptor of hash table
+char	keyword[ARB]	# i: Keyword to add to hash table
+#--
+int	index, step
+
+bool	streq()
+
+begin
+	# Calculate initial guess at position in hash table
+	# and step size in case guessed position is already filled
+
+	call calc_unhash (hash, keyword, index, step)
+	index = mod (index, UNH_SIZE(hash))
+
+	# Loop until an empty slot is found or the keyword is matched
+
+	repeat {
+	    if (UNH_KEY(hash,index) == NULL) {
+		break
+
+	    } else if (streq (Memc[UNH_KEY(hash,index)], keyword)) {
+		break
+	    }
+
+	    index = mod (index + step, UNH_SIZE(hash))
+	}
+
+	return (index)
+end
+
+# NEW_UNHASH -- Create a new hash table
+
+pointer procedure new_unhash (nkey, keysize)
+
+int	nkey		# i: number of keywords in the hash
+int	keysize		# i: maximum length of a key
+#--
+int	size
+pointer	hash
+
+begin
+	# Find a power of two greater than the number of keywords
+
+	for (size = 1; size < 2 * nkey; size = 2 * size)
+	    ;
+
+	# Allocate structure for hash and set initial values
+
+	call malloc (hash, LEN_UNHSTRUCT, TY_INT)
+	call calloc (UNH_KEYBUF(hash), size, TY_INT)
+	call calloc (UNH_VALBUF(hash), size, TY_INT)
+	call malloc (UNH_STRBUF(hash), size*(keysize+1), TY_CHAR)
+
+	UNH_SIZE(hash) = size
+	UNH_NEXT(hash) = UNH_STRBUF(hash)
+
+	return (hash)
+end
+