home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / sun / volume1 / palette / part02 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-18  |  4.1 KB  |  169 lines
  1. /* 
  2.  * hash.c - This module implements and maintains a closed hash table 
  3.  *          containing one entry for each colormap.
  4.  *          
  5.  *          Note that the data structure is stored locally in hash_tab.
  6.  *          
  7.  *          Exported routines:
  8.  *            H_MakeNull
  9.  *            H_Insert
  10.  *            H_Member
  11.  *            H_Delete
  12.  */
  13.  
  14. /**************************************************************************
  15.  *      palette - a colormap editor
  16.  *      Copyright (c) 1988 Wayne Mesard                                   *
  17.  *                                                                        *
  18.  *      This is free software.  It may be reproduced, retransmitted,      *
  19.  *      redistributed and otherwise propogated at will, provided that     *
  20.  *      no monetary profit is realized and that this notice remains       *
  21.  *      intact and in place.                                              *
  22.  *                                                                        *
  23.  *      Please direct bug reports, code enhancements and comments         *
  24.  *      to mesard@BBN.COM.                                                *
  25.  *                                                                        *
  26.  **************************************************************************/
  27.  
  28. #include <stdio.h>
  29. #include "hash.h"
  30. #include <strings.h>
  31.  
  32. #define NullP(ENTRY)    (ENTRY.name[0] == '\0')
  33. #define NotNullP(ENTRY) (ENTRY.name[0] != '\0')
  34. #define DeletedP(ENTRY)    (ENTRY.name[0] == '\001')
  35. #define NotDeletedP(ENTRY) (ENTRY.name[0] != '\001')
  36. #define DoDelete(ENTRY) (ENTRY.name[0] = '\001')
  37. #define STREQ(S1, S2) (!strcmp(S1, S2))
  38.  
  39. static cms_tab_t hash_tab;
  40.  
  41. /*
  42.  * H_MakeNull 
  43.  */
  44.  
  45. void H_MakeNull()
  46. {
  47.     int i;
  48.  
  49.     for (i = -1; ++i < CMS_TAB_SIZE;)
  50.     hash_tab[i].name[0] = '\0';
  51. }
  52.  
  53.  
  54. /* 
  55.  * H_Insert - Places an entry in the table if it isn't already there.  
  56.  *            Returns false, iff the hash table was full.
  57.  */
  58.  
  59. boolean H_Insert(targ, size, presentation, RGB)
  60. char *targ;
  61. int size;
  62. caddr_t presentation;
  63. struct cms_map *RGB;
  64. {
  65.     int b;
  66.     
  67.     if (!STREQ(hash_tab[b = locate(targ, false)].name, targ)) {
  68.     b = locate(targ, true);
  69.     if (NullP(hash_tab[b]) || DeletedP(hash_tab[b])) {
  70.         (void) strcpy(hash_tab[b].name, targ);
  71.         hash_tab[b].size = size;
  72.         hash_tab[b].presentation = presentation;
  73.         hash_tab[b].map = *RGB;
  74.         return(true);
  75.     }
  76.     else
  77.         return(false);
  78.     }
  79.     else
  80.     return(true);
  81. }
  82.  
  83.  
  84.  
  85. /* 
  86.  * H_Member - Returns zero if targ is not in the hash table.  Otherwise 
  87.  *            it returns the size field.  Additionally, if the second 
  88.  *            and third params are non-null, it fills copies the map and 
  89.  *            presentation fields into them.
  90.  */
  91.  
  92. int H_Member(targ, cms, presentation)
  93. char *targ;
  94. caddr_t *presentation;
  95. struct cms_map *cms;
  96. {
  97.     int b;
  98.  
  99.     if (STREQ(hash_tab[b = locate(targ, false)].name, targ)) {
  100.     if (cms)
  101.         bcopy((char *)&(hash_tab[b].map), (char *)cms, 
  102.           sizeof(struct cms_map));
  103.     if (presentation)
  104.         *presentation = hash_tab[b].presentation;
  105.     return(hash_tab[b].size);
  106.     }
  107.     else
  108.     return(0);
  109. }
  110.  
  111.     
  112.  
  113.     
  114. /*
  115.  * H_Delete - Removes an entry from the hash-table.
  116.  *              Note non-modular bogosity: frees memory which was not
  117.  *            allocated by this package.
  118.  */
  119.  
  120. void H_Delete(targ)
  121. char *targ;
  122. {
  123.     int b = locate(targ, false);
  124.  
  125.     if (STREQ(hash_tab[b].name, targ)) {
  126.     DoDelete(hash_tab[b]);
  127.     free((char *) hash_tab[b].map.cm_red);
  128.     free((char *) hash_tab[b].map.cm_green);
  129.     free((char *) hash_tab[b].map.cm_blue);
  130.     }
  131. }
  132.  
  133.  
  134.  
  135. static int h(s)
  136. char *s;
  137. {
  138.     int val = 0;
  139.  
  140.     while (*s)
  141.     val += (*s++<<1);
  142.  
  143.     return (val % CMS_TAB_SIZE);
  144. }
  145.  
  146.  
  147. /* 
  148.  * locate - Scans until it finds targ or an empty bucket.  If deletedP 
  149.  *          is true it will also stop at deleted buckets.  Returns the 
  150.  *          bucket number.
  151.  */
  152.  
  153. static int locate(targ, deletedP)
  154. char *targ;
  155. boolean deletedP;
  156. {
  157.     int h();
  158.     int i=0, initial=h(targ);
  159.  
  160.     while ((i < CMS_TAB_SIZE) &&
  161.        NotNullP(hash_tab[(initial+i) % CMS_TAB_SIZE]) &&
  162.        (deletedP ? NotDeletedP(hash_tab[(initial+i) % CMS_TAB_SIZE]) : true) &&
  163.        !STREQ(hash_tab[(initial+i) % CMS_TAB_SIZE].name, targ))
  164.     i++;
  165.  
  166.     return((initial+i) % CMS_TAB_SIZE);
  167. }
  168.  
  169.