Permalink
Find file Copy path
4c70655 Oct 1, 2016
1 contributor

Users who have contributed to this file

153 lines (129 sloc) 2.72 KB
PROGRAM hash
%NOLOCKGROUP
CONST
%INCLUDE includes/hash.c
TYPE
%INCLUDE includes/hash.t
ROUTINE djb2(str : STRING) : INTEGER
VAR
hash : INTEGER
i : INTEGER
char : INTEGER
BEGIN
hash = 5381
FOR i=1 TO STR_LEN(str) DO
char = ORD(str, i)
hash = hash * 33 + char
ENDFOR
RETURN(hash)
END djb2
-- From Java 1.5 string library
ROUTINE jsStrHash(str : STRING) : INTEGER
VAR
hash : INTEGER
i : INTEGER
BEGIN
hash = 0
FOR i=1 TO STR_LEN(str) DO
hash = (31 * hash) + ord(str, i)
ENDFOR
RETURN(hash)
END jsStrHash
ROUTINE hModHash(key : STRING; len : INTEGER) : INTEGER
VAR
hash : INTEGER
BEGIN
hash = jsStrHash(key)
RETURN(hash MOD len + 1)
END hModHash
ROUTINE hGetIndex(key : STRING; get : BOOLEAN; tbl : ARRAY OF hashNode) : INTEGER
VAR
hash : INTEGER
tblLength : INTEGER
index : INTEGER
count : INTEGER
BEGIN
hash = jsStrHash(key)
tblLength = ARRAY_LEN(tbl)
index = hash MOD tblLength + 1
FOR count=0 TO tblLength DO
IF UNINIT(tbl[index].key) THEN tbl[index].key = ''; ENDIF
IF get THEN
-- get requests require key=key
IF ((tbl[index].key=key)) THEN
RETURN(index)
ENDIF
ELSE
-- put requests require key=key or empty
IF ((tbl[index].key=key) OR
(tbl[index].key='')) THEN
RETURN(index)
ENDIF
ENDIF
index = index + 1
IF index > tblLength THEN
index = 1
ENDIF
ENDFOR
-- did not find index
RETURN(0)
END hGetIndex
ROUTINE hPut(key : STRING; value : STRING; tbl : ARRAY OF hashNode) : BOOLEAN
VAR
index : INTEGER
BEGIN
index = hGetIndex(key, false, tbl)
IF index > 0 THEN
tbl[index].key = key
tbl[index].val = value
RETURN(TRUE)
ELSE
RETURN(FALSE)
ENDIF
END hPut
ROUTINE hGet(key : STRING; tbl : ARRAY OF hashNode) : STRING
VAR
index : INTEGER
BEGIN
index = hGetIndex(key, true, tbl)
IF index > 0 THEN
RETURN(tbl[index].val)
ENDIF
RETURN('')
END hGet
ROUTINE hDel(key : STRING; tbl : ARRAY OF hashNode) : BOOLEAN
VAR
index : INTEGER
BEGIN
index = hGetIndex(key, true, tbl)
IF index > 0 THEN
IF ((tbl[index].key=key)) THEN
tbl[index].key = ''
RETURN(TRUE)
ENDIF
ENDIF
RETURN(FALSE)
END hDel
ROUTINE hashPut(key : STRING; value : STRING; tblProg : STRING; tblName : STRING) : BOOLEAN
VAR
entry : INTEGER
BEGIN
IF (key='') THEN RETURN(FALSE); ENDIF
RETURN(hPut(key, value, BYNAME(tblProg, tblName, entry)))
END hashPut
ROUTINE hashGet(key : STRING; tblProg : STRING; tblName : STRING) : STRING
VAR
entry : INTEGER
BEGIN
IF (key='') THEN RETURN(''); ENDIF
RETURN (hGet(key, BYNAME(tblProg, tblName, entry)))
END hashGet
ROUTINE hashDel(key : STRING; tblProg : STRING; tblName : STRING) : BOOLEAN
VAR
entry : INTEGER
BEGIN
IF (key='') THEN RETURN(FALSE); ENDIF
RETURN (hDel(key, BYNAME(tblProg, tblName, entry)))
END hashDel
BEGIN
END hash