home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / HASH.H < prev    next >
C/C++ Source or Header  |  1997-07-05  |  3KB  |  89 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. #ifndef HASH__H
  4. #define HASH__H
  5.  
  6. #include <stddef.h>           /* For size_t     */
  7.  
  8. /*
  9. ** A hash table consists of an array of these buckets.  Each bucket
  10. ** holds a copy of the key, a pointer to the data associated with the
  11. ** key, and a pointer to the next bucket that collided with this one,
  12. ** if there was one.
  13. */
  14.  
  15. typedef struct bucket {
  16.     char *key;
  17.     void *data;
  18.     struct bucket *next;
  19. } bucket;
  20.  
  21. /*
  22. ** This is what you actually declare an instance of to create a table.
  23. ** You then call 'construct_table' with the address of this structure,
  24. ** and a guess at the size of the table.  Note that more nodes than this
  25. ** can be inserted in the table, but performance degrades as this
  26. ** happens.  Performance should still be quite adequate until 2 or 3
  27. ** times as many nodes have been inserted as the table was created with.
  28. */
  29.  
  30. typedef struct hash_table {
  31.     size_t size;
  32.     bucket **table;
  33. } hash_table;
  34.  
  35. /*
  36. ** This is used to construct the table.  If it doesn't succeed, it sets
  37. ** the table's size to 0, and the pointer to the table to NULL.
  38. */
  39.  
  40. hash_table *construct_table(hash_table *table,size_t size);
  41.  
  42. /*
  43. ** Inserts a pointer to 'data' in the table, with a copy of 'key' as its
  44. ** key.  Note that this makes a copy of the key, but NOT of the
  45. ** associated data.
  46. */
  47.  
  48. void *insert(char *key,void *data,struct hash_table *table);
  49.  
  50. /*
  51. ** Returns a pointer to the data associated with a key.  If the key has
  52. ** not been inserted in the table, returns NULL.
  53. */
  54.  
  55. void *lookup(char *key,struct hash_table *table);
  56.  
  57. /*
  58. ** Deletes an entry from the table.  Returns a pointer to the data that
  59. ** was associated with the key so the calling code can dispose of it
  60. ** properly.
  61. */
  62.  
  63. void *del(char *key,struct hash_table *table);
  64.  
  65. /*
  66. ** Goes through a hash table and calls the function passed to it
  67. ** for each node that has been inserted.  The function is passed
  68. ** a pointer to the key, and a pointer to the data associated
  69. ** with it.
  70. */
  71.  
  72. void enumerate(struct hash_table *table,void (*func)(char *,void *));
  73.  
  74. /*
  75. ** Frees a hash table.  For each node that was inserted in the table,
  76. ** it calls the function whose address it was passed, with a pointer
  77. ** to the data that was in the table.  The function is expected to
  78. ** free the data.  Typical usage would be:
  79. ** free_table(&table, free);
  80. ** if the data placed in the table was dynamically allocated, or:
  81. ** free_table(&table, NULL);
  82. ** if not.  ( If the parameter passed is NULL, it knows not to call
  83. ** any function with the data. )
  84. */
  85.  
  86. void free_table(hash_table *table, void (*func)(void *));
  87.  
  88. #endif /* HASH__H */
  89.