gas/hash.c: add interface for looking up non-NUL-terminated strings

gas/hash.c: add interface for looking up non-NUL-terminated strings

[Zack Weinberg]

The appended patch adds a new interface to gas/hash.c, hash_find_n,
with exactly the same semantics as hash_find except that the length of
the key is passed in as an argument, and the key is not assumed to be
NUL-terminated.  This is more convenient when parsing an assembly
instruction: one does not need to write a NUL into the line buffer so
that hash_find knows where to stop.

Thoughts?  The only downside that I see is that the other hash_*
functions may now be marginally slower, since they have to call strlen
up front.  I thought this was better than duplicating the entire body
of hash_lookup.

zw

        * hash.c (hash_lookup): Delete unnecessary forward declaration.
        Add 'len' argument.  Do not assume 'key' is NUL-terminated.
        All callers changed to match.
        (hash_find_n): New interface.
        * hash.h: Prototype hash_find_n.

===================================================================
Index: hash.c
--- hash.c	(revision 7)
+++ hash.c	(revision 8)
@@ -120,19 +120,13 @@
    Each time we look up a string, we move it to the start of the list
    for its hash code, to take advantage of referential locality.  */
 
-static struct hash_entry *hash_lookup (struct hash_control *,
-				       const char *,
-				       struct hash_entry ***,
-				       unsigned long *);
-
 static struct hash_entry *
-hash_lookup (struct hash_control *table, const char *key,
+hash_lookup (struct hash_control *table, const char *key, size_t len,
 	     struct hash_entry ***plist, unsigned long *phash)
 {
-  register unsigned long hash;
-  unsigned int len;
-  register const unsigned char *s;
-  register unsigned int c;
+  unsigned long hash;
+  size_t n;
+  unsigned int c;
   unsigned int index;
   struct hash_entry **list;
   struct hash_entry *p;
@@ -143,13 +137,11 @@
 #endif
 
   hash = 0;
-  len = 0;
-  s = (const unsigned char *) key;
-  while ((c = *s++) != '\0')
+  for (n = 0; n < len; n++)
     {
+      c = key[n];
       hash += c + (c << 17);
       hash ^= hash >> 2;
-      ++len;
     }
   hash += len + (len << 17);
   hash ^= hash >> 2;
@@ -176,7 +168,7 @@
 	  ++table->string_compares;
 #endif
 
-	  if (strcmp (p->string, key) == 0)
+	  if (p->string[len] == '\0' && strncmp (p->string, key, len) == 0)
 	    {
 	      if (prev != NULL)
 		{
@@ -207,7 +199,7 @@
   struct hash_entry **list;
   unsigned long hash;
 
-  p = hash_lookup (table, key, &list, &hash);
+  p = hash_lookup (table, key, strlen (key), &list, &hash);
   if (p != NULL)
     return "exists";
 
@@ -237,7 +229,7 @@
   struct hash_entry **list;
   unsigned long hash;
 
-  p = hash_lookup (table, key, &list, &hash);
+  p = hash_lookup (table, key, strlen (key), &list, &hash);
   if (p != NULL)
     {
 #ifdef HASH_STATISTICS
@@ -274,7 +266,7 @@
   struct hash_entry *p;
   PTR ret;
 
-  p = hash_lookup (table, key, NULL, NULL);
+  p = hash_lookup (table, key, strlen (key), NULL, NULL);
   if (p == NULL)
     return NULL;
 
@@ -297,13 +289,28 @@
 {
   struct hash_entry *p;
 
-  p = hash_lookup (table, key, NULL, NULL);
+  p = hash_lookup (table, key, strlen (key), NULL, NULL);
   if (p == NULL)
     return NULL;
 
   return p->data;
 }
 
+/* As hash_find, but KEY is of length LEN and is not guaranteed to be
+   NUL-terminated.  */
+
+PTR
+hash_find_n (struct hash_control *table, const char *key, size_t len)
+{
+  struct hash_entry *p;
+
+  p = hash_lookup (table, key, len, NULL, NULL);
+  if (p == NULL)
+    return NULL;
+
+  return p->data;
+}
+
 /* Delete an entry from a hash table.  This returns the value stored
    for that entry, or NULL if there is no such entry.  */
 
@@ -313,7 +320,7 @@
   struct hash_entry *p;
   struct hash_entry **list;
 
-  p = hash_lookup (table, key, &list, NULL);
+  p = hash_lookup (table, key, strlen (key), &list, NULL);
   if (p == NULL)
     return NULL;
 
===================================================================
Index: hash.h
--- hash.h	(revision 7)
+++ hash.h	(revision 8)
@@ -59,6 +59,11 @@
 
 extern PTR hash_find (struct hash_control *, const char *key);
 
+/* As hash_find, but KEY is of length LEN and is not guaranteed to be
+   NUL-terminated.  */
+
+extern PTR hash_find_n (struct hash_control *, const char *key, size_t len);
+
 /* Delete an entry from a hash table.  This returns the value stored
    for that entry, or NULL if there is no such entry.  */
 

Re: gas/hash.c: add interface for looking up non-NUL-terminated strings

[Alan Modra]

On Tue, Mar 29, 2005 at 12:00:37PM -0800, Zack Weinberg wrote:
> 
> The appended patch adds a new interface to gas/hash.c, hash_find_n,
> with exactly the same semantics as hash_find except that the length of
> the key is passed in as an argument, and the key is not assumed to be
> NUL-terminated.  This is more convenient when parsing an assembly
> instruction: one does not need to write a NUL into the line buffer so
> that hash_find knows where to stop.

Hmm, seems to me that writing a NUL into the line buffer isn't that
onerous.  I'd like to see more justification for this patch,
particularly since we have too many hash table implementations already
in binutils.  At some stage I'd like to move bfd and gas over to use
libiberty's hashtab.c, and another interface difference will make that
task harder.

> -	  if (strcmp (p->string, key) == 0)
> +	  if (p->string[len] == '\0' && strncmp (p->string, key, len) == 0)

Potential access past the end of p->string.  The strncmp must come
first.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: gas/hash.c: add interface for looking up non-NUL-terminated strings

[Zack Weinberg]

Alan Modra <amodra@bigpond.net.au> writes:

> On Tue, Mar 29, 2005 at 12:00:37PM -0800, Zack Weinberg wrote:
>> 
>> The appended patch adds a new interface to gas/hash.c, hash_find_n,
>> with exactly the same semantics as hash_find except that the length of
>> the key is passed in as an argument, and the key is not assumed to be
>> NUL-terminated.  This is more convenient when parsing an assembly
>> instruction: one does not need to write a NUL into the line buffer so
>> that hash_find knows where to stop.
>
> Hmm, seems to me that writing a NUL into the line buffer isn't that
> onerous. 

I suppose to some extent it's a matter of taste, but having this
interface available allows me to make dramatic simplifications in
tc-arm.c.  I should have something to show y'all sometime this week on
that score.

> I'd like to see more justification for this patch, particularly
> since we have too many hash table implementations already in
> binutils.  At some stage I'd like to move bfd and gas over to use
> libiberty's hashtab.c, and another interface difference will make
> that task harder.

For what GAS uses hash tables for, I don't think that's a good idea.
libiberty's hashtab.c is extremely generic; you'd have to write
nontrivial amounts of wrapper code, and you'd take a nasty performance
hit.  (multiple indirect function calls on every lookup).

cpplib's symtab.c might be a better fit (it can be used independently
from the rest of cpplib) -- and it already has this interface. :)

>> -	  if (strcmp (p->string, key) == 0)
>> +	  if (p->string[len] == '\0' && strncmp (p->string, key, len) == 0)
>
> Potential access past the end of p->string.  The strncmp must come
> first.

Good point, will correct in my copy.

zw