home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / mrdebug.tar.Z / mrdebug.tar / mrhash.c < prev    next >
C/C++ Source or Header  |  1993-10-25  |  6KB  |  271 lines
  1. /*
  2. **++
  3. **  ABSTRACT:
  4. **
  5. **    This module contains hashing functions specific to the gateway
  6. **    implementation.
  7. **
  8. **  FUNCTIONS and PROCEDURES:
  9. **
  10. **    create_htable        Create hash table and initialize it
  11. **    delete_htable        Remove entry from hash table
  12. **    insert_htable        Insert entry into hash table
  13. **    lookup_htable        Search for specific entry in table
  14. **    update_htable        Modify entry in table
  15. **
  16. **  AUTHOR:
  17. **
  18. **      Deb Agarwal (original by: Paul W. Ciarfella)
  19. **
  20. **  CREATION DATE:     14June93 (17Aug92)
  21. **
  22. **  MODIFICATION HISTORY:
  23. **--
  24. **/
  25.  
  26.  
  27. /*
  28. **
  29. **  INCLUDE FILES
  30. **
  31. */
  32.  
  33. #include <stddef.h>
  34. #include <stdio.h>
  35. #include <sysexits.h>
  36.  
  37. #include "types.h"
  38. #include "mrhash.h"
  39. #include "data_struct_proto.h"
  40.  
  41. void   Sys_exit( int error )
  42. {
  43.     printf( "PROGRAM EXITTING WITH ERROR %d\n", error );
  44.     exit( error );
  45. }
  46.  
  47. /*
  48. ** The hash table uses a simple division scheme with chaining on collision.
  49. ** The table itself is an array of pointers to HENTRY.  The data in the table
  50. ** is stored as a linked list of HENTRY structures anchored from a slot in
  51. ** the table.
  52. **
  53. **    Slots    Data entries
  54. **    -------- --------------------------------------------
  55. **    [ 0 ] -> [ HENTRY ] <-> [ HENTRY ] <-> ... [ HENTRY ]
  56. **      :
  57. **    [ n ] -> [ HENTRY ] <-> [ HENTRY ] <-> ... [ HENTRY ]
  58. **
  59. **
  60. **     Posn in slot   Prev_p     Next_p
  61. **     ------------   --------   ------------------------------
  62. **     First          Null       Non-null if next entry exists
  63. **                               Null if no entry exists
  64. **     Middle         Non-null   Non-null
  65. **     End            Non-null   Null
  66. */
  67.  
  68. void create_htable( HTABLE_t *table_p, int slots )
  69.  
  70. {
  71. HENTRY_t *newtbl_p;
  72.  
  73. /*
  74. ** Use calloc to allocate memory, explicit initialization to 0 is not needed
  75. */
  76.  
  77.     if ( ( newtbl_p = (HENTRY_t *)calloc(slots, sizeof(HENTRY_t)) ) == NULL )
  78.     {
  79.     printf("create_htable: Malloc returned NULL\n");
  80.     Sys_exit( EX_OSERR );
  81.     }
  82.  
  83.     table_p->htbl_p  = (HENTRY_t **) newtbl_p;
  84.     table_p->slots   = slots;
  85.     table_p->entries = 0;
  86. }
  87.  
  88. /*
  89. ** Hashing function: very generic.  Specific functions could be defined
  90. ** by adding a hash_function field to the HTABLE structure.  Different
  91. ** hash tables could use different hashing functions.
  92. */
  93.  
  94. long       hash_index( char *key_p, long tbl_length )
  95. {
  96.     long  len,
  97.           pos,
  98.           index;
  99.  
  100.     index = 0;
  101.     len = strlen( key_p );
  102.     for( pos = 0; pos < len; pos++ )
  103.         index += (int)key_p[pos];
  104.     index %= tbl_length;
  105.     return index;
  106. }
  107.  
  108. /*
  109. **       Look-up an entry in the hash table and return
  110. **       a pointer to it if it is found.
  111. */
  112.  
  113. HENTRY_t *lookup_htable( HTABLE_t *table_p, char *key_p )
  114.  
  115. {
  116. long hidx;
  117. HENTRY_t *match_p;
  118.  
  119. /*
  120. ** Calculate index
  121. */
  122.     hidx = hash_index( key_p, table_p->slots );
  123.  
  124. /*
  125. ** Search for match
  126. */
  127.     for ( match_p = table_p->htbl_p[ hidx ];
  128.          match_p != NULL; match_p = match_p->next_p )
  129.     if ( !strcmp( match_p->key_p, key_p ))
  130.         /* the entry is already in the table */
  131.         break;
  132.  
  133. /*
  134. **  Return a pointer to the entry in the table.
  135. */
  136.     return( match_p );
  137.  
  138. }
  139.  
  140.  
  141. void delete_htable( HTABLE_t *table_p, char *key_p )
  142.  
  143. {
  144. HENTRY_t *entry_p;
  145.  
  146. /*
  147. ** Find entry in the table
  148. */
  149.     if ( ( entry_p = lookup_htable( table_p, key_p ) ) == NULL )
  150.     {
  151.     printf("ERROR: delete_htable: Did not find entry\n");
  152.     Sys_exit( EX_SOFTWARE );
  153.     }
  154. /*
  155. ** Remove entry from the table.
  156. */
  157.     if ( entry_p->prev_p == NULL )
  158.     table_p->htbl_p[ entry_p->hidx ] = entry_p->next_p;
  159.     else
  160.     {
  161.     entry_p->prev_p->next_p = entry_p->next_p;
  162.     if ( entry_p->next_p != NULL )
  163.         entry_p->next_p->prev_p = entry_p->prev_p;
  164.     }
  165.     free( entry_p );
  166.  
  167.     if ( --table_p->entries == 0 )
  168.         printf("delete_htable: WARNING: table is empty.\n" );
  169.     else
  170.         if ( table_p->entries < 0 )
  171.         {
  172.         printf("delete_htable: ERROR!! hash table entries < 0 \n");
  173.         Sys_exit( EX_SOFTWARE );
  174.         }
  175. }
  176.  
  177.  
  178. /*
  179. ** Assumes that entry does not already exist for this data
  180. */
  181.  
  182. void insert_htable( HTABLE_t *table_p, char *key_p, long index, long *subnet, char *name )
  183.  
  184. {
  185. long       hidx;
  186. HENTRY_t *nentry_p;
  187.  
  188. /*
  189. ** Calculate index
  190. */
  191.     hidx = hash_index( key_p, table_p->slots );
  192.     /*printf( "name %s has hash index %ld\n", key_p, hidx );*/
  193.  
  194. /*
  195. ** Create new entry
  196. */
  197.     if ( ( nentry_p = (HENTRY_t *) malloc( sizeof( HENTRY_t ) ) ) == NULL )
  198.     {
  199.     printf("insert_htable: malloc returned NULL\n");
  200.     Sys_exit( EX_OSERR );
  201.     }
  202.     nentry_p->hidx      = hidx;        /* Slot number in table        */
  203.     strcpy( nentry_p->key_p, key_p );  /* IP name                     */
  204.     nentry_p->index     = index;       /* adjacency list index of name */
  205.     nentry_p->subnet    = subnet;      /* pointer to the subnet interface */
  206.     if( name != NULL )
  207.        strcpy( nentry_p->name, name );
  208.  
  209. /*
  210. ** Insert entry:
  211. **     if slot in table is empty then put it there; otherwise slip it in
  212. **     front of the existing entries on that slot.
  213. */
  214.     nentry_p->prev_p = NULL;
  215.     if ( table_p->htbl_p[ hidx ] == NULL )
  216.     nentry_p->next_p = NULL;
  217.     else
  218.     {
  219.     nentry_p->next_p = table_p->htbl_p[ hidx ];
  220.     nentry_p->next_p->prev_p = nentry_p;
  221.     }
  222.     table_p->htbl_p[ hidx ] = nentry_p;
  223.     ++table_p->entries;
  224. }
  225.  
  226. void update_htable( HTABLE_t *table_p, char *key_p, long index )
  227.  
  228. {
  229. HENTRY_t *entry_p;
  230.  
  231. /*
  232. ** Find entry in the table
  233. */
  234.     if ( ( entry_p = lookup_htable( table_p, key_p ) ) == NULL )
  235.     {
  236.     printf("ERROR: update_htable: Did not find entry\n");
  237.     Sys_exit( EX_SOFTWARE );
  238.     }
  239. /*
  240. ** Update entry 
  241. */
  242.     entry_p->index = index;
  243. }
  244.  
  245. void  print_htable( HTABLE_t *table_p )
  246. {
  247.     long i, count;
  248.     HENTRY_t  *cur_p;
  249.  
  250.     count = 0;
  251.     printf( "there should be %d entries in the table\n", table_p->entries);
  252.     for( i = 0; i < table_p->slots; i++ )
  253.         {
  254.         printf( "\nSLOT %ld: ", i);
  255.         for( cur_p = table_p->htbl_p[i]; cur_p != NULL; 
  256.                         cur_p = cur_p->next_p )
  257.             {
  258.             printf( "%s,%ld; ", cur_p->key_p, cur_p->index );
  259.             count++;
  260.             }
  261.         }
  262.     printf( "The actual count came to %ld\n", count );
  263. }
  264. /*
  265. **
  266. ** END: hash.c
  267. **
  268. */
  269.  
  270.  
  271.