home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / OS2 / CPOSTSRC.ZIP / HASH.C < prev    next >
C/C++ Source or Header  |  1992-08-08  |  7KB  |  279 lines
  1. /*------------------------------------------------------------------
  2.  * hash.c : hash table functions
  3.  *------------------------------------------------------------------
  4.  * 10-19-88 originally by Patrick J. Mueller
  5.  * 08-07-92 fixed up by Patrick J. Mueller
  6.  *------------------------------------------------------------------*/
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. #include "list.h"
  13. #include "hash.h"
  14.  
  15. /*------------------------------------------------------------------
  16.  * create hash table
  17.  *------------------------------------------------------------------*/
  18. Hash *HashCreate(
  19.    int                  itemSize,
  20.    int                  buckets,
  21.    HashFunc            *hashFunc,
  22.    ListCompareFunc     *cmpFunc,
  23.    ListNoMemFunc       *memFunc
  24.    )
  25.    {
  26.    Hash *hash;
  27.    int   i;
  28.  
  29.    /*---------------------------------------------------------------
  30.     * sanity check
  31.     *---------------------------------------------------------------*/
  32.    if (!itemSize || !buckets || !cmpFunc || !hashFunc)
  33.       return NULL;
  34.  
  35.    /*---------------------------------------------------------------
  36.     * allocate table structure
  37.     *---------------------------------------------------------------*/
  38.    hash = malloc(sizeof(List));
  39.    if (!hash)
  40.       {
  41.       if (memFunc)
  42.          memFunc();
  43.       return NULL;
  44.       }
  45.  
  46.    /*---------------------------------------------------------------
  47.     * fill in fields
  48.     *---------------------------------------------------------------*/
  49.    hash->itemSize = itemSize;
  50.    hash->buckets  = buckets;
  51.    hash->hashFunc = hashFunc;
  52.    hash->memFunc  = memFunc;
  53.  
  54.    /*---------------------------------------------------------------
  55.     * allocate buckets
  56.     *---------------------------------------------------------------*/
  57.    hash->bucket = malloc(buckets*sizeof(List *));
  58.    if (!hash->bucket)
  59.       {
  60.       free(hash);
  61.  
  62.       if (memFunc)
  63.          memFunc();
  64.  
  65.       return NULL;
  66.       }
  67.  
  68.    /*---------------------------------------------------------------
  69.     * initialize to zero
  70.     *---------------------------------------------------------------*/
  71.    memset(hash->bucket,0,buckets*sizeof(List *));
  72.  
  73.    /*---------------------------------------------------------------
  74.     * initialize buckets
  75.     *---------------------------------------------------------------*/
  76.    for (i=0; i<buckets; i++)
  77.       {
  78.       hash->bucket[i] = ListCreate(itemSize,cmpFunc,memFunc);
  79.  
  80.       if (!hash->bucket[i])
  81.          {
  82.          HashDestroy(hash);
  83.  
  84.          if (memFunc)
  85.             memFunc();
  86.          }
  87.       }
  88.  
  89.    /*---------------------------------------------------------------
  90.     * return
  91.     *---------------------------------------------------------------*/
  92.    return hash;
  93.    }
  94.  
  95. /*------------------------------------------------------------------
  96.  * destroy hash table
  97.  *------------------------------------------------------------------*/
  98. void HashDestroy(
  99.    Hash *hash
  100.    )
  101.    {
  102.    int i;
  103.  
  104.    if (!hash)
  105.       return;
  106.  
  107.    for (i=0; i<hash->buckets; i++)
  108.       ListDestroy(hash->bucket[i]);
  109.  
  110.    free(hash->bucket);
  111.    free(hash);
  112.    }
  113.  
  114. /*------------------------------------------------------------------
  115.  * find entry in hash table
  116.  *------------------------------------------------------------------*/
  117. void *HashFind(
  118.    Hash *hash,
  119.    void *pItem
  120.    )
  121.    {
  122.    int h;
  123.  
  124.    if (!hash)
  125.       return NULL;
  126.  
  127.    h = hash->hashFunc(pItem,hash->buckets);
  128.    if ((h < 0) || (h >= hash->buckets))
  129.       return NULL;
  130.  
  131.    return ListFind(hash->bucket[h],pItem);
  132.    }
  133.  
  134. /*------------------------------------------------------------------
  135.  * add entry to hash table
  136.  *------------------------------------------------------------------*/
  137. void *HashAdd(
  138.    Hash *hash,
  139.    void *pItem
  140.    )
  141.    {
  142.    int h;
  143.  
  144.    if (!hash)
  145.       return NULL;
  146.  
  147.    h = hash->hashFunc(pItem,hash->buckets);
  148.    if ((h < 0) || (h >= hash->buckets))
  149.       return NULL;
  150.  
  151.    return ListAdd(hash->bucket[h],pItem);
  152.    }
  153.  
  154. /*------------------------------------------------------------------
  155.  * delete entry from hash table
  156.  *------------------------------------------------------------------*/
  157. void HashDelete(
  158.    Hash *hash,
  159.    void *pItem
  160.    )
  161.    {
  162.    int h;
  163.  
  164.    if (!hash)
  165.       return;
  166.  
  167.    h = hash->hashFunc(pItem,hash->buckets);
  168.    if ((h < 0) || (h >= hash->buckets))
  169.       return;
  170.  
  171.    ListDelete(hash->bucket[h],pItem);
  172.    }
  173.  
  174. /*------------------------------------------------------------------
  175.  * iterate through hash table
  176.  *------------------------------------------------------------------*/
  177. void HashIterate(
  178.    Hash            *hash,
  179.    ListIterateFunc *pIterateFunc,
  180.    void            *pUserData
  181.    )
  182.    {
  183.    int i;
  184.  
  185.    if (!hash)
  186.       return;
  187.  
  188.    for (i=0; i<hash->buckets; i++)
  189.       ListIterate(hash->bucket[i],pIterateFunc,pUserData);
  190.    }
  191.  
  192. /*------------------------------------------------------------------
  193.  * test suite
  194.  *------------------------------------------------------------------*/
  195. #if defined(TEST)
  196.  
  197. /*------------------------------------------------------------------
  198.  * compare function
  199.  *------------------------------------------------------------------*/
  200. static int compareFunc(
  201.    void *overi1,
  202.    void *overi2
  203.    )
  204.    {
  205.    int *i1 = overi1;
  206.    int *i2 = overi2;
  207.  
  208.    if      (*i1 < *i2) return -1;
  209.    else if (*i1 > *i2) return  1;
  210.    else                return  0;
  211.    }
  212.  
  213. /*------------------------------------------------------------------
  214.  * hash function
  215.  *------------------------------------------------------------------*/
  216. static int hashFunc(
  217.    void *overi,
  218.    int   buckets
  219.    )
  220.    {
  221.    int *i = overi;
  222.    return *i % buckets;
  223.    }
  224.  
  225. /*------------------------------------------------------------------
  226.  * iterate function
  227.  *------------------------------------------------------------------*/
  228. static void iterateFunc(
  229.    void *overI,
  230.    void *overCounter
  231.    )
  232.    {
  233.    int *pi       = overI;
  234.    int *pCounter = overCounter;
  235.  
  236.    printf("%5d : %5d\n",*pCounter,*pi);
  237.    *pCounter += 1;
  238.    }
  239.  
  240. /*------------------------------------------------------------------
  241.  *
  242.  *------------------------------------------------------------------*/
  243. int main(void)
  244.    {
  245.    Hash *iHash;
  246.    int   i;
  247.    int   counter;
  248.  
  249.    iHash = HashCreate(sizeof(int),3,compareFunc,hashFunc,NULL);
  250.  
  251.    for (i= 1; i<10; i++)
  252.       HashAdd(iHash,&i);
  253.  
  254.    for (i=20; i>10; i--)
  255.       HashAdd(iHash,&i);
  256.  
  257.    for (i=0; i<=21; i++)
  258.       if (!HashFind(iHash,&i))
  259.          printf("didn't find %d\n",i);
  260.  
  261.    counter = 1;
  262.    HashIterate(iHash,iterateFunc,&counter);
  263.  
  264.    for (i=-1; i<5; i++)
  265.       HashDelete(iHash,&i);
  266.  
  267.    for (i=21; i>15; i--)
  268.       HashDelete(iHash,&i);
  269.  
  270.    counter = 1;
  271.    HashIterate(iHash,iterateFunc,&counter);
  272.  
  273.    HashDestroy(iHash);
  274.  
  275.    return 0;
  276.    }
  277.  
  278. #endif
  279.