home *** CD-ROM | disk | FTP | other *** search
/ vsiftp.vmssoftware.com / VSIPUBLIC@vsiftp.vmssoftware.com.tar / FREEWARE / FREEWARE40.ZIP / xpaint-247 / hash.c < prev    next >
C/C++ Source or Header  |  1996-06-25  |  6KB  |  266 lines
  1. /* +-------------------------------------------------------------------+ */
  2. /* | Copyright 1992, David Koblas.                                     | */
  3. /* | Copyright 1995, 1996 Torsten Martinsen (bullestock@dk-online.dk)  | */
  4. /* |                                                                   | */
  5. /* |   Permission to use, copy, modify, and distribute this software   | */
  6. /* |   and its documentation for any purpose and without fee is hereby | */
  7. /* |   granted, provided that the above copyright notice appear in all | */
  8. /* |   copies and that both that copyright notice and this permission  | */
  9. /* |   notice appear in supporting documentation.  This software is    | */
  10. /* |   provided "as is" without express or implied warranty.           | */
  11. /* +-------------------------------------------------------------------+ */
  12.  
  13. /* $Id: hash.c,v 1.3 1996/04/15 14:19:09 torsten Exp $ */
  14.  
  15. /*
  16. **  A simple useful set of hash routines:
  17. **
  18. **   void *HashCreate(int (*cmp)(void *, void*), void (*free)(void *), int nelem)
  19. **     -- Create a hash table with cmp() function, and optional free() function.
  20. **   void     HashDestroy(HashTable *tbl)
  21. **     -- Destroy the whole hash table
  22. **   void    *HashFind(HashTable *tbl, int value, void *val)
  23. **     -- Find an element in the hash table, returns NULL if not found
  24. **   int      HashAdd(HashTable *tbl, int value, void *val)
  25. **     -- Add an element to the table, returns non-zero on failure
  26. **   int      HashRemove(HashTable *tbl, int value, void *elem)
  27. **     -- Remove a particular hash entry from the table, pointer comparison
  28.  */
  29.  
  30.  
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33.  
  34. #include <X11/Intrinsic.h>
  35. #include "misc.h"
  36. #include "hash.h"
  37.  
  38.  
  39. typedef struct hash_s {
  40.     int *val;
  41.     struct hash_s *left, *right, *same, **parentp;
  42. } HashElement;
  43.  
  44. typedef struct {
  45.     int (*cmp) (void *, void *);
  46.     void (*free) (void *);
  47.     HashElement **table;
  48.     int nelem;
  49. } HashTable;
  50.  
  51. /*
  52. **  Create a hashtable, with cmp() compare function, and free() free function
  53. **       with a hash table width of nelem, free can be null in which case the
  54. **       system free function will be used.
  55.  */
  56. void *
  57. HashCreate(int (*cmp) (void *, void *), void (*free) (void *), int nelem)
  58. {
  59.     HashTable *new;
  60.     int i;
  61.  
  62.     new = (HashTable *) xmalloc(sizeof(HashTable));
  63.     new->nelem = nelem;
  64.     new->cmp = cmp;
  65.     new->free = free;
  66.     new->table = (HashElement **) xmalloc(nelem * sizeof(HashElement *));
  67.  
  68.     for (i = 0; i < nelem; i++)
  69.     new->table[i] = NULL;
  70.  
  71.     return (void *) new;
  72. }
  73.  
  74. /*
  75.  * Helper function for HashDestroy()
  76.  */
  77. static void 
  78. hashDestory(void (*func) (void *), HashElement * entry)
  79. {
  80.     if (entry->left != NULL) {
  81.     hashDestory(func, entry->left);
  82.     free(entry->left);
  83.     }
  84.     if (entry->right != NULL) {
  85.     hashDestory(func, entry->right);
  86.     free(entry->right);
  87.     }
  88.     if (entry->same != NULL) {
  89.     hashDestory(func, entry->same);
  90.     free(entry->same);
  91.     }
  92.     if (entry->val)
  93.     func(entry->val);
  94. }
  95.  
  96. /*
  97. **  Free the entire hash table, and all elements
  98.  */
  99. void 
  100. HashDestroy(void *t)
  101. {
  102.     int i;
  103.     HashTable *tbl = (HashTable *) t;
  104.  
  105.     if (tbl == NULL)
  106.     return;
  107.  
  108.     for (i = 0; i < tbl->nelem; i++) {
  109.     if (tbl->table[i] != NULL) {
  110.         hashDestory(tbl->free ? tbl->free : free, tbl->table[i]);
  111.         free(tbl->table[i]);
  112.     }
  113.     }
  114.     free(tbl->table);
  115.     free(tbl);
  116. }
  117.  
  118. /*
  119. **  Find a particular element in the hash table, returns NULL if it isn't found
  120.  */
  121. void *
  122. HashFind(void *t, int value, void *val)
  123. {
  124.     HashTable *tbl = (HashTable *) t;
  125.     HashElement *cur;
  126.     int v;
  127.  
  128.     if (tbl == NULL)
  129.     return NULL;
  130.  
  131.     cur = tbl->table[value];
  132.  
  133.     while (cur != NULL) {
  134.     if ((v = tbl->cmp(cur->val, val)) == 0)
  135.         return cur->val;
  136.  
  137.     if (v < 0)
  138.         cur = cur->left;
  139.     else
  140.         cur = cur->right;
  141.     }
  142.  
  143.     return NULL;
  144. }
  145.  
  146. /*
  147. **  Add a new element to the hash table, returns non-zero on failure
  148.  */
  149. int 
  150. HashAdd(void *t, int value, void *val)
  151. {
  152.     HashTable *tbl = (HashTable *) t;
  153.     HashElement *new;
  154.     HashElement *cur = tbl->table[value];
  155.     HashElement **prev;
  156.     int v;
  157.  
  158.     if (tbl == NULL)
  159.     return 1;
  160.  
  161.     new = (HashElement *) xmalloc(sizeof(HashElement));
  162.  
  163.     new->left = NULL;
  164.     new->right = NULL;
  165.     new->same = NULL;
  166.     new->val = val;
  167.     new->parentp = NULL;
  168.  
  169.     prev = &tbl->table[value];
  170.     while (cur != NULL) {
  171.     if ((v = tbl->cmp(cur->val, val)) < 0) {
  172.         prev = &cur->left;
  173.         cur = cur->left;
  174.     } else if (v > 0) {
  175.         prev = &cur->right;
  176.         cur = cur->right;
  177.     } else {
  178.         prev = &cur->same;
  179.         new->same = cur->same;
  180.         if (cur->same != NULL)
  181.         cur->same->parentp = &new->same;
  182.         break;
  183.     }
  184.     }
  185.     *prev = new;
  186.     new->parentp = prev;
  187.  
  188.     return 0;
  189. }
  190.  
  191. static HashElement *
  192. find(HashElement * pos, void *elem)
  193. {
  194.     HashElement *v;
  195.  
  196.     if (pos == NULL)
  197.     return NULL;
  198.  
  199.     if (pos->val == elem)
  200.     return pos;
  201.     if (pos->left != NULL && (v = find(pos->left, elem)) != NULL)
  202.     return v;
  203.     if (pos->right != NULL && (v = find(pos->right, elem)) != NULL)
  204.     return v;
  205.     if (pos->same != NULL && (v = find(pos->same, elem)) != NULL)
  206.     return v;
  207.     return NULL;
  208. }
  209.  
  210. /*
  211. **  Remove a particular element from the hash table, done using pointer compares
  212.  */
  213. int 
  214. HashRemove(void *t, int value, void *elem)
  215. {
  216.     HashTable *tbl = (HashTable *) t;
  217.     HashElement *v;
  218.  
  219.     if (elem == NULL || tbl == NULL)
  220.     return 1;
  221.  
  222.     if ((v = find(tbl->table[value], elem)) == NULL)
  223.     return 0;        /* The element was not actually in the table */
  224.  
  225.     if (v->same != NULL) {
  226.     /*
  227.     **  Same links are not allowed to have left & right children
  228.     **   so just inherit the parent's children.
  229.      */
  230.     if (v->left != NULL)
  231.         v->left->parentp = &v->same->left;
  232.     if (v->right != NULL)
  233.         v->right->parentp = &v->same->right;
  234.     v->same->left = v->left;
  235.     v->same->right = v->right;
  236.  
  237.     *v->parentp = v->same;
  238.     v->same->parentp = v->parentp;
  239.     } else if (v->left != NULL) {
  240.     *v->parentp = v->left;
  241.     v->left->parentp = v->parentp;
  242.     if (v->right != NULL) {
  243.         HashElement *cur = v->left, **prev = &v->left;
  244.         while (cur != NULL) {
  245.         if (tbl->cmp(cur->val, v->right->val) < 0) {
  246.             prev = &cur->left;
  247.             cur = cur->left;
  248.         } else {
  249.             prev = &cur->right;
  250.             cur = cur->right;
  251.         }
  252.         }
  253.         *prev = v->right;
  254.         v->right->parentp = prev;
  255.     }
  256.     } else {
  257.     /* no left side, just attach the right */
  258.     *v->parentp = v->right;
  259.     if (v->right != NULL)
  260.         v->right->parentp = v->parentp;
  261.     }
  262.     free(v);
  263.  
  264.     return 1;
  265. }
  266.