On Thu, Feb 02, 2012 at 05:29:03PM +0100, Steffen Daode Nurpmeso wrote:
> OH!
> I see!
>
> Otto Moerbeek wrote [2012-02-02 16:43+0100]:
> > The cast might indeed be needed. For the rest: I think doing things
> > like h ^= h and writing a multiplication as a shift and addition is
> > silly: it's the compiler's job to find a good way of computing the
> > desired values.
>
> (Once i copied over the algorithm a multiplication was 10 and
> a addition and shift 1 cycles, if i recall correctly (Cyrix 166+),
> and i came from a lot of nasm stuff.
> And yes, here the cast is definitely needed, because it's indeed
> a macro and that's used in multiple functions, including buffer
> ones with void* argument.)
>
> > -Otto
>
> Anyway - Chris Toreks algorithm really rocks, only some of its
> users are something stupid.
>
> --steffen
New diff, with cast.
Now that the tree isn't locked anymore, I'd like to get this in.
OK?
I'm thinking about parameterizing the hash function so on each run it
differs a little. Theroretically it could protect against malicious
code filling the hash with colliding strings and causing a DOS (think
cgi and related stuff).
-Otto
Index: table.c
===================================================================
RCS file: /cvs/src/bin/ksh/table.c,v
retrieving revision 1.14
diff -u -p -r1.14 table.c
--- table.c 2 Feb 2012 08:42:46 -0000 1.14
+++ table.c 14 Feb 2012 08:49:39 -0000
@@ -18,8 +18,8 @@ hash(const char *n)
unsigned int h = 0;
while (*n != '\0')
- h = 2*h + *n++;
- return h * 32821; /* scatter bits */
+ h = 33*h + (unsigned char)(*n++);
+ return h;
}
void
@@ -44,7 +44,7 @@ texpand(struct table *tp, int nsize)
for (i = 0; i < nsize; i++)
ntblp[i] = NULL;
tp->size = nsize;
- tp->nfree = 8*nsize/10; /* table can get 80% full */
+ tp->nfree = 7*nsize/10; /* table can get 70% full */
tp->tbls = ntblp;
if (otblp == NULL)
return;
@@ -108,7 +108,7 @@ ktenter(struct table *tp, const char *n,
}
if (tp->nfree <= 0) { /* too full */
- if (tp->size <= SHRT_MAX/2)
+ if (tp->size <= INT_MAX/2)
texpand(tp, 2*tp->size);
else
internal_errorf(1, "too many vars");
Index: table.h
===================================================================
RCS file: /cvs/src/bin/ksh/table.h,v
retrieving revision 1.7
diff -u -p -r1.7 table.h
--- table.h 11 Dec 2005 20:31:21 -0000 1.7
+++ table.h 14 Feb 2012 08:49:39 -0000
@@ -8,7 +8,7 @@
struct table {
Area *areap; /* area to allocate entries */
- short size, nfree; /* hash size (always 2^^n), free entries */
+ int size, nfree; /* hash size (always 2^^n), free entries */
struct tbl **tbls; /* hashed table items */
};
