summaryrefslogtreecommitdiff
path: root/src/lib/libast/cdt/dtstrhash.c
diff options
context:
space:
mode:
authorIgor Pashev <pashev.igor@gmail.com>2012-06-24 22:28:35 +0000
committerIgor Pashev <pashev.igor@gmail.com>2012-06-24 22:28:35 +0000
commit3950ffe2a485479f6561c27364d3d7df5a21d124 (patch)
tree468c6e14449d1b1e279222ec32f676b0311917d2 /src/lib/libast/cdt/dtstrhash.c
downloadksh-upstream.tar.gz
Imported Upstream version 93u+upstream
Diffstat (limited to 'src/lib/libast/cdt/dtstrhash.c')
-rw-r--r--src/lib/libast/cdt/dtstrhash.c61
1 files changed, 61 insertions, 0 deletions
diff --git a/src/lib/libast/cdt/dtstrhash.c b/src/lib/libast/cdt/dtstrhash.c
new file mode 100644
index 0000000..7eaac89
--- /dev/null
+++ b/src/lib/libast/cdt/dtstrhash.c
@@ -0,0 +1,61 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2011 AT&T Intellectual Property *
+* and is licensed under the *
+* Eclipse Public License, Version 1.0 *
+* by AT&T Intellectual Property *
+* *
+* A copy of the License is available at *
+* http://www.eclipse.org/org/documents/epl-v10.html *
+* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
+* *
+* Information and Software Systems Research *
+* AT&T Research *
+* Florham Park NJ *
+* *
+* Glenn Fowler <gsf@research.att.com> *
+* David Korn <dgk@research.att.com> *
+* Phong Vo <kpv@research.att.com> *
+* *
+***********************************************************************/
+#include "dthdr.h"
+
+/* Hashing a string into an unsigned integer.
+** The basic method is to continuingly accumulate bytes and multiply
+** with some given prime. The length n of the string is added last.
+** The recurrent equation is like this:
+** h[k] = (h[k-1] + bytes)*prime for 0 <= k < n
+** h[n] = (h[n-1] + n)*prime
+** The prime is chosen to have a good distribution of 1-bits so that
+** the multiplication will distribute the bits in the accumulator well.
+** The below code accumulates 2 bytes at a time for speed.
+**
+** Written by Kiem-Phong Vo (02/28/03)
+*/
+
+#if __STD_C
+uint dtstrhash(uint h, Void_t* args, ssize_t n)
+#else
+uint dtstrhash(h,args,n)
+reg uint h;
+Void_t* args;
+ssize_t n;
+#endif
+{
+ unsigned char *s = (unsigned char*)args;
+
+ if(n <= 0)
+ { for(; *s != 0; s += s[1] ? 2 : 1)
+ h = (h + (s[0]<<8) + s[1])*DT_PRIME;
+ n = s - (unsigned char*)args;
+ }
+ else
+ { unsigned char* ends;
+ for(ends = s+n-1; s < ends; s += 2)
+ h = (h + (s[0]<<8) + s[1])*DT_PRIME;
+ if(s <= ends)
+ h = (h + (s[0]<<8))*DT_PRIME;
+ }
+ return (h+n)*DT_PRIME;
+}