[tac_plus] RFC: refactoring hashing algorithm (was: contributing patched to tac_plus)

[heasley]

Wed, Dec 03, 2014 at 10:45:15AM -0900, David M. Syzdek:
> Heasly,
> 
> Looking at the hashing algorithm used for storing devices, users, groups, and ACLs, it appears that at most 157 entries can be stored in each hash table (less if the key strings create a collision).  My organization currently has 1,428 devices with unique keys.  So I need a method which allows more than 157 entries to be stored in each hash table.
> 
> Refer to the following code from hash.c to see the limitation:
> 
>     tac_plus.h:
>     220 #define HASH_TAB_SIZE 157        /* user and group hash table sizes */
> 
>     hash.c:
>      32 /* Calculate hash value from a string */
>      33 static int
>      34 calculate_hash(char *name)
>      35 {
>      36     int i;
>      37     int len = strlen(name);
>      38     int hashval = 0;
>      39
>      40     for (i = 0; i < len; i++) {
>      41         hashval += name[i] * (i + 1);
>      42     }
>      43     hashval += name[0];
>      44     hashval = hashval > 0 ? hashval : -hashval;
>      45     return(hashval);
>      46 }
>      47
>      48 /* Lookup a name in a hash table.  Return its node if it exists, else NULL *    /
>      49 void *
>      50 hash_lookup(void **hashtab, char *name)
>      51 {
>      52     ENTRY *entry;
>      53     int hashval = calculate_hash(name);
>      54
>      55     entry = hashtab[hashval % HASH_TAB_SIZE];
>      56                     
>      57     while (entry) {
>      58         if (STREQ(name, entry->name))
>      59             /* Node exists in table. return it */
>      60             return(entry);
>      61         entry = entry->hash;
>      62     }    
>      63     return(NULL);
>      64 }    
> 
> 
> I would like refactor hash.c to use a sorted array and binary search rather than a fixed length reallocated hash table.  This would incur a performance hit on start-up and slightly increase the time required to lookup items within the hash, I can add an autoconf option which will allow tac_plus to be compiled with the old hashing methods or the new hashing methods.
> 
> Does anyone foresee an issue with the proposed change?

nope; i wouldnt bother with the autoconf knob either.