home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  9.9 KB  |  339 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: hash.c $
  7. * Version:        $Revision: 1.4 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement generic hash tables.
  13. *
  14. * $Id: hash.c 1.4 91/12/31 19:40:02 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    hash.c $
  20. * Revision 1.4  91/12/31  19:40:02  kjb
  21. * Modified include file directories.
  22. * 
  23. * Revision 1.3  91/09/03  18:28:01  ROOT_DOS
  24. * Ported to UNIX.
  25. * 
  26. * Revision 1.2  91/09/01  16:43:56  ROOT_DOS
  27. * Minor cosmetic changes.
  28. * 
  29. * Added function hsh_kill() to delete a hash table and all the symbols it
  30. * contains.
  31. * 
  32. * Revision 1.1  91/08/16  13:14:45  ROOT_DOS
  33. * Initial revision
  34. * 
  35. ****************************************************************************/
  36.  
  37. #include <stdio.h>
  38. #include <malloc.h>
  39. #include <ctype.h>
  40. #include <signal.h>
  41. #include <string.h>
  42. #include "debug.h"
  43. #include "hash.h"
  44. #include "ssort.h"
  45.  
  46. PUBLIC void *hsh_newsym(int size)
  47. /****************************************************************************
  48. *
  49. * Function:        hsh_newsym
  50. * Parameters:    size    - Amount of memory to allocate for symbol
  51. * Returns:        Pointer to the allocated symbols user space.
  52. *
  53. * Description:    Allocates the memory required for a symbol, adding a small
  54. *                header at the start of the symbol. We return a reference to
  55. *                the user space of the symbol, as if it had be allocated via
  56. *                malloc.
  57. *
  58. ****************************************************************************/
  59. {
  60.     HSH_BUCKET    *sym;
  61.  
  62.     if ( !(sym = (HSH_BUCKET*)malloc(size+sizeof(HSH_BUCKET))) ) {
  63.         fprintf(stderr,"Can't get memory for BUCKET\n");
  64.         raise(SIGABRT);
  65.         return NULL;
  66.         }
  67.  
  68.     return HSH_USERSPACE(sym);        /* Return pointer to user space        */
  69. }
  70.  
  71. PUBLIC void hsh_freesym(void *sym)
  72. /****************************************************************************
  73. *
  74. * Function:        hsh_freesym
  75. * Parameters:    sym        - Symbol to free
  76. *
  77. * Description:    Frees a symbol previously allocated with newsym().
  78. *
  79. ****************************************************************************/
  80. {
  81.     free(HSH_HEADER(sym));
  82. }
  83.  
  84. PUBLIC HASH_TAB *hsh_init(unsigned maxsym,unsigned (*hash_function)(),
  85.                          int (*cmp_function)() )
  86. /****************************************************************************
  87. *
  88. * Function:        hsh_init
  89. * Parameters:    maxsym            - Maximum number of symbols
  90. *                hash_function    - Hash function to the table
  91. *                cmp_function    - Comparison function for the elements
  92. * Returns:        Pointer to the newly created hash table.
  93. *
  94. * Description:    Makes a hash table of the given size and returns a pointer
  95. *                to it. Note that we call calloc() to allocate the memory,
  96. *                so that all the hash table pointers are initially NULL.
  97. *
  98. ****************************************************************************/
  99. {
  100.     HASH_TAB    *p;
  101.  
  102.     if (!maxsym)
  103.         maxsym = 127;            /* Default size */
  104.  
  105.                         /*    |<--- space for table -->|<- and header -->| */
  106.     if( (p=(HASH_TAB*)calloc(1,(maxsym*sizeof(HSH_BUCKET*)) + sizeof(HASH_TAB)))
  107.             != NULL) {
  108.         p->size = maxsym;
  109.         p->numsyms = 0;
  110.         p->hash = hash_function;
  111.         p->cmp = cmp_function;
  112.         }
  113.     else {
  114.         fprintf(stderr,"Insufficient memory for symbol table\n");
  115.         raise(SIGABRT);
  116.         return NULL;
  117.         }
  118.     return p;
  119. }
  120.  
  121. PUBLIC void hsh_kill(HASH_TAB *tabp,void (*freeSym)(void *))
  122. /****************************************************************************
  123. *
  124. * Function:        hsh_kill
  125. * Parameters:    tabp    - Hash table to kill
  126. *                freeSym    - Pointer to user function to free a symbol
  127. *
  128. * Description:    Kills the hash table tab, by deleting all the symbols in the
  129. *                table, and then deleting the table itself. Note that we call
  130. *                the user supplied routine (*freeSym)() to free each hash
  131. *                table symbol. This allows the user program to perform any
  132. *                extra processing needed to kill each symbol (if each symbol
  133. *                contains pointers to other items on the heap for example).
  134. *                If no extra processing is required, just pass the address of
  135. *                hsh_freesym(), ie:
  136. *
  137. *                    hsh_kill(mytab,hsh_freesym);
  138. *
  139. ****************************************************************************/
  140. {
  141.     HSH_BUCKET    *p,*sym,**symtab;
  142.     int            i;
  143.  
  144.     if (tabp && tabp->size != 0)
  145.         for (symtab = tabp->table, i = tabp->size; --i >= 0 ; symtab++) {
  146.             sym = *symtab;
  147.             while (sym) {
  148.                 p = sym;
  149.                 sym = sym->next;
  150.                 (*freeSym)(HSH_USERSPACE(p));
  151.                 }
  152.             }
  153.     free(tabp);
  154. }
  155.  
  156. PUBLIC void *hsh_addsym(HASH_TAB *tabp, void *isym)
  157. /****************************************************************************
  158. *
  159. * Function:        hsh_addsym
  160. * Parameters:    tabp    - The hash table
  161. *                isym    - Symbol to add
  162. *
  163. * Description:    Adds a symbol to the hash table. The new symbol is linked
  164. *                onto the head of the chain at it's particular hash location.
  165. *
  166. ****************************************************************************/
  167. {
  168.     HSH_BUCKET    **p,*tmp;
  169.     HSH_BUCKET    *sym = HSH_HEADER(isym);
  170.  
  171.     p = &(tabp->table)[ (*tabp->hash)(isym) % tabp->size ];
  172.  
  173.     tmp = *p;
  174.     *p = sym;
  175.     sym->prev = p;
  176.     sym->next = tmp;
  177.  
  178.     if (tmp)
  179.         tmp->prev = &sym->next;
  180.  
  181.     tabp->numsyms++;
  182.     return HSH_USERSPACE(sym);
  183. }
  184.  
  185. PUBLIC void hsh_delsym(HASH_TAB *tabp, void *isym)
  186. /****************************************************************************
  187. *
  188. * Function:        hsh_delsym
  189. * Parameters:    tabp    - The hash table
  190. *                isym    - Symbol to delete
  191. *
  192. * Description:    Removes a symbol from the hash table. "sym" is a pointer
  193. *                from a previous findsym() call. It points initially at the
  194. *                user space, but is decremented to get at the BUCKET header.
  195. *
  196. ****************************************************************************/
  197. {
  198.     HSH_BUCKET    *sym = HSH_HEADER(isym);
  199.  
  200.     if (tabp && sym) {
  201.         --tabp->numsyms;
  202.  
  203.         if ( (*(sym->prev) = sym->next) != NULL)
  204.             sym->next->prev = sym->prev;
  205.         }
  206. }
  207.  
  208. PUBLIC void *hsh_findsym(HASH_TAB *tabp, void *sym)
  209. /****************************************************************************
  210. *
  211. * Function:        hsh_findsym
  212. * Parameters:    tabp    - The hash table
  213. *                isym    - Symbol to look for
  214. * Returns:        pointer to the symbol if it exist, NULL otherwise
  215. *
  216. * Description:    Returns a pointer to the hash table element having a
  217. *                particular symbol, or NULL if the symbol isn't in the table.
  218. *
  219. ****************************************************************************/
  220. {
  221.     HSH_BUCKET *p;
  222.  
  223.     if (!tabp)            /* Table empty */
  224.         return NULL;
  225.  
  226.     p = (tabp->table)[ (*tabp->hash)(sym) % tabp->size ];
  227.  
  228.     while (p && (*tabp->cmp)(sym,HSH_USERSPACE(p)) )
  229.         p = p->next;
  230.  
  231.     return (p ? HSH_USERSPACE(p) : NULL);
  232. }
  233.  
  234. PUBLIC void *hsh_nextsym(HASH_TAB *tabp,void *i_last)
  235. /****************************************************************************
  236. *
  237. * Function:        hsh_nextsym
  238. * Parameters:    tabp    - The hash table
  239. *                i_last    - The last symbol accessed
  240. * Returns:        Pointer to the next symbol in the current chain
  241. *
  242. * Description:    Returns a pointer to the next node in the current chain that
  243. *                has the same key as the last node found (or NULL if there
  244. *                is no such node). "i_last" is a pointer returned from a
  245. *                previous findsym() or nextsym() call.
  246. *
  247. ****************************************************************************/
  248. {
  249.     HSH_BUCKET    *last = HSH_HEADER(i_last);
  250.  
  251.     for (; last->next; last = last->next)
  252.         if ( (tabp->cmp)(i_last, last->next + 1) == 0)    /* Keys match */
  253.             return HSH_USERSPACE(last->next);
  254.     return NULL;
  255. }
  256.  
  257. PRIVATE int (*User_cmp)(void *,void *);
  258.  
  259. PRIVATE int internal_cmp(HSH_BUCKET **p1,HSH_BUCKET **p2)
  260. {
  261.     return (*User_cmp)(HSH_USERSPACE(*p1),HSH_USERSPACE(*p2));
  262. }
  263.  
  264. PUBLIC int hsh_ptab(HASH_TAB *tabp,void (*print)(void *,void *),void *param,
  265.                 int sort)
  266. /****************************************************************************
  267. *
  268. * Function:        hsh_ptab
  269. * Parameters:    tabp    - The hash table
  270. *                print    - Routine to printe a symbol
  271. *                param    - Parameters to the print routine
  272. *                sort    - True if the table should be sorted
  273. * Returns:        True if completed, false otherwise
  274. *
  275. * Description:    Prints the table of symbols by calling the print routine
  276. *                for every symbol in the table. If sort is true, the table
  277. *                is sorted first before it is printed. The print function
  278. *                is called with two arguments:
  279. *
  280. *                    (*print)(sym,param)
  281. *
  282. *                Sym is a pointer to a HSH_BUCKET user area.
  283. *
  284. ****************************************************************************/
  285. {
  286.     HSH_BUCKET    **outtab,**outp,*sym,**symtab;
  287.     int            i;
  288.  
  289.     if (!tabp || tabp->size == 0)        /* table is empty */
  290.         return 1;
  291.  
  292.     if (!sort) {
  293.         for (symtab = tabp->table, i = tabp->size; --i >= 0 ; symtab++) {
  294.  
  295.             /* Print all symbols in the current chain. */
  296.  
  297.             for (sym = *symtab; sym ; sym = sym->next)
  298.                 (*print)(HSH_USERSPACE(sym),param);
  299.             }
  300.         }
  301.     else {
  302.         /* Allocate memory for the outtab, an array of pointers to
  303.          * HSH_BUCKETS, and initialise it. The outtab is different from
  304.          * the actual hash table in that every outtab element points
  305.          * to a single HSH_BUCKET structure, rather than to a linked list
  306.          * of them.
  307.          */
  308.  
  309.         if ( !(outtab = (HSH_BUCKET**)malloc(tabp->numsyms * sizeof(HSH_BUCKET*)) ))
  310.             return 0;
  311.  
  312.         outp = outtab;
  313.  
  314.         for ( symtab = tabp->table, i = tabp->size; --i >= 0; symtab++)
  315.             for (sym = *symtab; sym ; sym = sym->next) {
  316.                 if (outp > outtab + tabp->numsyms) {
  317.                     fprintf(stderr,"Internal error [ptab], table overflow\n");
  318.                     exit(1);
  319.                     }
  320.                 *outp++ = sym;
  321.                 }
  322.  
  323.         /* Sort the outtab and then print it. The (*outp) + 1 in the
  324.          * print call increments the pointer past the header part
  325.          * of the HSH_BUCKET structure. During sorting, the increment
  326.          * is done in internal_cmp.
  327.          */
  328.  
  329.         User_cmp = tabp->cmp;
  330.         assort((void**)outtab, tabp->numsyms, sizeof(HSH_BUCKET*), internal_cmp);
  331.  
  332.         for (outp = outtab, i = tabp->numsyms; --i >= 0; outp++)
  333.             (*print)(HSH_USERSPACE(*outp),param);
  334.  
  335.         free(outtab);
  336.         }
  337.     return 1;
  338. }
  339.