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