TBBT/trace_play/generic_hash.c

   1 /* generic_hash.c: Generic hash function that hashes on a maximum of three keys
   2  * $Id: generic_hash.c,v 1.5 2002/08/21 22:08:01 ningning Exp $
   3  * Changes:
   4  *
   5  *      $Log: generic_hash.c,v $
   6  *      Revision 1.5  2002/08/21 22:08:01  ningning
   7  *      *** empty log message ***
   8  *
   9  */
  10
  11 #include <stdio.h>
  12 #include "generic_hash.h"
  13
  14 /* create an entry for a block */
  15 void generic_insert(char * key1, unsigned int key1_size, unsigned int key3, struct generic_entry **htable, int hsize)
  16 {
  17 unsigned int index;
  18 struct generic_entry *p,*q;
  19
  20 unsigned int * tmp =(unsigned int *)key1;
  21 unsigned int i;
  22 index = 0;
  23 for (i=0; i<(key1_size/4); i++)
  24         index += *(tmp+i);
  25 index = index%hsize;
  26 {
  27 //printf ("generic_insert index %d key %s\n", index, key1);
  28 }
  29 p = q = htable[index];
  30 while (p) {
  31     if ((!memcmp(p->key1, key1, key1_size))
  32         && (p->key3==key3)) {
  33         return;
  34     }
  35     q = p;
  36     p = p->next;
  37 }
  38 if (!p) {
  39     p = (struct generic_entry *)malloc(sizeof(struct generic_entry));
  40     memcpy(p->key1, key1, key1_size);
  41     p->key3 = key3;
  42     p->next = NULL;
  43 }
  44 if (!q)
  45     htable[index] = p;
  46 else
  47     q->next = p;
  48 return;
  49 }
  50
  51 void generic_delete(char * key1, unsigned int key1_size, unsigned int key3, struct generic_entry **htable, int hsize)
  52 {
  53 unsigned int index;
  54 int found;
  55 struct generic_entry *p,*q;
  56
  57 unsigned int * tmp =(unsigned int *)key1;
  58 unsigned int i;
  59 index = 0;
  60 for (i=0; i<(key1_size/4); i++)
  61         index += *(tmp+i);
  62 index = index%hsize;
  63
  64 p = q = htable[index];
  65 found = 0;
  66 while (p) {
  67     if ((!memcmp(p->key1, key1, key1_size))
  68             && (p->key3==key3)) {
  69                 found = 1;
  70                 break;
  71     }
  72         q = p;
  73     p = p->next;
  74 }
  75 RFS_ASSERT(found==1);
  76 if (p==htable[index])
  77     htable[index] = p->next;
  78 else
  79     q->next = p->next;
  80
  81 /* free hash entry */
  82
  83 free(p);
  84
  85 return;
  86 }
  87
  88 struct generic_entry *generic_lookup(char * key1, unsigned int key1_size, unsigned int key3, struct generic_entry **htable, int hsize)
  89 {
  90 unsigned int index;
  91 struct generic_entry *p;
  92
  93 unsigned int * tmp =(unsigned int *)key1;
  94 unsigned int i;
  95 index = 0;
  96 for (i=0; i<(key1_size/4); i++)
  97         index += *(tmp+i);
  98 index = index%hsize;
  99 {
 100 //printf ("generic_lookup index %d key %s\n", index, key1);
 101 }
 102
 103 p = htable[index];
 104 while (p) {
 105     if (!memcmp(p->key1, key1, key1_size))
 106         {
 107                 return p;
 108     }
 109     p = p->next;
 110 }
 111 /*RFS_ASSERT(0);*/
 112 return NULL;
 113 }
 114
 115 struct generic_entry *generic_lookup1(unsigned int key1, unsigned int key2, unsigned int key3, struct generic_entry **htable, int hsize)
 116 {
 117 unsigned int index;
 118 struct generic_entry *p;
 119
 120 index = ((unsigned int)key1)%hsize;
 121 p = htable[index];
 122 while (p) {
 123     if (p->key1==key1)
 124                 return p;
 125     p = p->next;
 126 }
 127 /*RFS_ASSERT(0);*/
 128 return NULL;
 129 }
 130
 131 struct generic_entry *generic_lookup2(unsigned int key1, unsigned int key2, unsigned int key3, struct generic_entry **htable, int hsize)
 132 {
 133 unsigned int index;
 134 struct generic_entry *p;
 135
 136 index = (key1 + key2)%hsize;
 137 p = htable[index];
 138 while (p) {
 139     if (   (p->key1==key1)
 140             && (p->key2==key2)
 141            )
 142                 return p;
 143     p = p->next;
 144 }
 145 /*RFS_ASSERT(0);*/
 146 return NULL;
 147 }
 148
 149 void generic_display(struct generic_entry **htable, int hsize, int numkeys)
 150 {
 151 int i;
 152 struct generic_entry *p;
 153 int counter = 0;
 154
 155 for (i=0;i<hsize;i++) {
 156     p = htable[i];
 157         if (p)
 158                 printf ("htable[%d]", i);
 159     while (p) {
 160                 if (numkeys==1)
 161                         printf("%d, ", p->key1);
 162                 else if (numkeys==2)
 163                         printf("(%d,%x), ", p->key1,p->key2);
 164                 else
 165                         printf("(%d,%d,%d), ", p->key1,p->key2,p->key3);
 166             p = p->next;
 167         counter++;
 168                 if ((counter%4)==3)
 169                     printf("\n");
 170     }
 171 }
 172 printf("\ncounter was %d\n",counter);
 173 }
 174
 175 /* create an entry for a block */
 176 void generic_long_insert4(unsigned int key1, unsigned int key2, unsigned int key3, unsigned int key4, unsigned int key5, unsigned int key6, struct generic_long_entry **htable, int hsize)
 177 {
 178 int index;
 179 struct generic_long_entry *p,*q;
 180
 181 index = (key1 + key2 + key3 + key4)%hsize;
 182 p = q = htable[index];
 183 while (p) {
 184     if ((p->key1==key1)
 185             && (p->key2==key2)
 186             && (p->key3==key3)
 187             && (p->key4==key4)
 188             && (p->key5==key5)
 189             && (p->key6==key6)) {
 190                 return;
 191     }
 192         q = p;
 193     p = p->next;
 194 }
 195 if (!p) {
 196         p = (struct generic_long_entry *)malloc(sizeof(struct generic_long_entry));
 197         p->key1 = key1;
 198         p->key2 = key2;
 199         p->key3 = key3;
 200         p->key4 = key4;
 201         p->key5 = key5;
 202         p->key6 = key6;
 203     p->next = NULL;
 204 }
 205 if (!q)
 206     htable[index] = p;
 207 else
 208     q->next = p;
 209 return;
 210 }
 211
 212 struct generic_entry *generic_long_lookup4(unsigned int key1, unsigned int key2, unsigned int key3, unsigned int key4, struct generic_long_entry **htable, int hsize)
 213 {
 214 int index;
 215 struct generic_long_entry *p;
 216
 217 index = (key1 + key2 + key3 + key4 )%hsize;
 218 p = htable[index];
 219 while (p) {
 220     if (   (p->key1==key1)
 221             && (p->key2==key2)
 222                 && (p->key3==key3)
 223                 && (p->key4==key4)
 224            )
 225                 return p;
 226     p = p->next;
 227 }
 228 /*RFS_ASSERT(0);*/
 229 return NULL;
 230 }