[PATCH] ihash ids should be unsigned

[Marcus Brinkmann]

Hi,

the libihash ids are signed integers, but all users actually provide
unsigned integers, and expect it to work.  If a large integer is provided
that is cast to a negative number, the hash value will be negative as well,
and there will be underflow errors (negative array indices).  I remember
that Neal told me he actually saw that happening, but I don't know in what
code it was (ours, or code he was hacking) and under which situation. 
Anyway, it's apparently wrong.  Neal seems to like to use unsigned long
instead, which would give 64 bit on 64 bit arches, but I am more
conservative and provide this patch which uses unsigned int.

I also want to remove ihash/primes.c which is obsolete but wasn't removed at
the time Roland replaced it by sizes.c.  The file will still be in the
repository, of course (under Attic).

Ok to apply?

Thanks,
Marcus

Index: ChangeLog
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ChangeLog,v
retrieving revision 1.5
diff -u -p -r1.5 ChangeLog
--- ChangeLog   15 Aug 2001 09:29:37 -0000      1.5
+++ ChangeLog   16 Aug 2003 22:10:52 -0000
@@ -1,3 +1,18 @@
+2003-08-17  Marcus Brinkmann  <address@hidden>
+
+       * ihash.h (struct ihash): Change type of IDS to unsigned int *.
+       (ihash_add): Change type of ID argument in prototype to unsigned.
+       (ihash_find): Likewise.
+       (ihash_remove): Likewise.
+       * ihash.c (index_valid): Change type of ID to unsigned.
+       (find_index): Likewise.  Also for H and FIRSTH.
+       (ihash_add): Likewise.  Also for H and FIRSTH.  Change type of
+       OLD_IDS to unsigned int *.
+       (ihash_find): Likewise.
+       (ihash_remove): Likewise.
+       * ihash.c (find_index): Use UINT_MAX instead -1.
+       (ihash_add): Likewise.
+
 2001-08-15  Roland McGrath  <address@hidden>
 
        * sizes.c: New file, a list of prime numbers useful for table sizes.
Index: ihash.c
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ihash.c,v
retrieving revision 1.6
diff -u -p -r1.6 ihash.c
--- ihash.c     15 Aug 2001 09:29:26 -0000      1.6
+++ ihash.c     16 Aug 2003 22:10:52 -0000
@@ -1,6 +1,6 @@
 /* Integer-keyed hash table functions.
 
-   Copyright (C) 1993,94,95,96,97,2001 Free Software Foundation, Inc.
+   Copyright (C) 1993-1997, 2001, 2003 Free Software Foundation, Inc.
 
    This file is part of the GNU Hurd.
 
@@ -52,7 +52,7 @@ index_empty(ihash_t ht, int index)
 }
 
 static inline int
-index_valid(ihash_t ht, int index, int id)
+index_valid(ihash_t ht, int index, unsigned int id)
 {
   return !index_empty(ht, index) && ht->ids[index] == id;
 }
@@ -61,14 +61,15 @@ index_valid(ihash_t ht, int index, int i
    key.  You must subsequently check to see whether the given index is valid
    (with index_valid() or index_empty()).  */
 static inline int
-find_index(ihash_t ht, int id)
+find_index(ihash_t ht, unsigned int id)
 {
-  int h, firsth = -1;
+  unsigned int h = UINT_MAX;
+  unsigned int firsth = UINT_MAX;
 
   for (h = HASH(ht, id);
        ht->tab[h] != HASH_EMPTY && ht->ids[h] != id && h != firsth;
        h = REHASH(ht, id, h))
-    if (firsth == -1)
+    if (firsth == UINT_MAX)
       firsth = h;
 
   return h;
@@ -138,17 +139,18 @@ ihash_set_cleanup(ihash_t ht,
    stashed value with ihash_locp_remove().  If a memory allocation error
    occurs, ENOMEM is returned, otherwise 0.  */
 error_t
-ihash_add(ihash_t ht, int id, void *item, void ***locp)
+ihash_add(ihash_t ht, unsigned int id, void *item, void ***locp)
 {
   if (ht->size)
     {
-      int h, firsth = -1;
+      unsigned int h = UINT_MAX;
+      unsigned int firsth = UINT_MAX;
 
       /* Search for for an empty or deleted space.  */
       for (h = HASH(ht, id);
           ht->tab[h] != HASH_EMPTY && ht->tab[h] != HASH_DEL && h != firsth;
           h = REHASH(ht, id, h))
-       if (firsth == -1)
+       if (firsth == UINT_MAX)
          firsth = h;
 
       if (index_empty(ht, h) || ht->ids[h] == id)
@@ -173,7 +175,7 @@ ihash_add(ihash_t ht, int id, void *item
     int old_size = ht->size;
     void **old_tab = ht->tab;
     void ****old_locps = ht->locps;
-    int *old_ids = ht->ids;
+    unsigned int *old_ids = ht->ids;
 
     i = 0;
     while (_ihash_sizes[i] <= old_size)
@@ -226,7 +228,7 @@ ihash_add(ihash_t ht, int id, void *item
 /* Find and return the item in hash table HT with key ID, or NULL if it
    doesn't exist.  */
 void *
-ihash_find (ihash_t ht, int id)
+ihash_find (ihash_t ht, unsigned int id)
 {
   if (ht->size == 0)
     return 0;
@@ -272,7 +274,7 @@ ihash_locp_remove(ihash_t ht, void **loc
 /* Remove the entry with a key of ID from HT.  If anything was actually
    removed, 1 is returned, otherwise (if there was no such element), 0.  */
 int
-ihash_remove(ihash_t ht, int id)
+ihash_remove(ihash_t ht, unsigned int id)
 {
   int index = find_index(ht, id);
   if (index_valid(ht, index, id))
Index: ihash.h
===================================================================
RCS file: /cvsroot/hurd/hurd/libihash/ihash.h,v
retrieving revision 1.4
diff -u -p -r1.4 ihash.h
--- ihash.h     25 Apr 1996 05:01:46 -0000      1.4
+++ ihash.h     16 Aug 2003 22:10:52 -0000
@@ -34,7 +34,7 @@ struct ihash
   void **tab;
 
   /* An array storing the integer key for each element.  */
-  int *ids;
+  unsigned int *ids;
 
   /* An array storing pointers to the `location pointers' for each element.
      These are used as cookies for quick 'n' easy removal.  */
@@ -72,11 +72,11 @@ void ihash_set_cleanup(ihash_t ht,
    deleted, so you can't stash its value elsewhere and hope to use the
    stashed value with ihash_locp_remove()].  If a memory allocation error
    occurs, ENOMEM is returned, otherwise 0.  */
-error_t ihash_add(ihash_t ht, int id, void *item, void ***locp);
+error_t ihash_add(ihash_t ht, unsigned int id, void *item, void ***locp);
 
 /* Find and return the item in hash table HT with key ID, or NULL if it
    doesn't exist.  */
-void *ihash_find(ihash_t ht, int id);
+void *ihash_find(ihash_t ht, unsigned int id);
 
 /* Call function FUN of one arg for each element of HT.  FUN's only arg is a
    pointer to the value stored in the hash table.  If FUN ever returns
@@ -86,7 +86,7 @@ error_t ihash_iterate(ihash_t ht, error_
 
 /* Remove the entry with a key of ID from HT.  If anything was actually
    removed, 1 is returned, otherwise (if there was no such element), 0.  */
-int ihash_remove(ihash_t ht, int id);
+int ihash_remove(ihash_t ht, unsigned int id);
 
 /* Remove the entry at LOCP from the hashtable HT.  LOCP is as returned from
    an earlier call to ihash_add().  This call should be faster than


-- 
`Rhubarb is no Egyptian god.' GNU      http://www.gnu.org    address@hidden
Marcus Brinkmann              The Hurd http://www.gnu.org/software/hurd/
address@hidden
http://www.marcus-brinkmann.de/