File: C:\NOAA\NEMS_11731\src\chem\gocart\src\GMAO_Shared\MAPL_Base\hash.c

1     #ifndef sysAIX
2     #include <malloc.h>
3     #include <stdio.h>
4     #include <stdlib.h>
5     #include <math.h>
6     #include <limits.h>
7     
8     #define HASHCHUNK 32
9     #define HEAPCHUNK 4
10     
11     #define FREE(A) if(A) free(A); A=NULL
12     
13     typedef struct {
14     int i,j,k;
15     } entry_t;
16     
17     typedef struct{
18       entry_t *entry_list;
19       int next_entry, size;
20     }  bucket_t;
21       
22     typedef struct {
23       bucket_t *bucket_list;
24       int num_entries, num_buckets;
25     }  hash_t;
26     
27     hash_t *hash_heap=(hash_t *)NULL;
28     int hash_heap_size = HEAPCHUNK;
29     
30     void init_hash(hash_t *h, int nbuckets) {
31       int i;
32       h->bucket_list = (bucket_t *)malloc((size_t)(nbuckets*sizeof(bucket_t)));
33       if(!h->bucket_list) {
34         printf("hash.c line=%d : Could not allocate bucket list\n",__LINE__);
35         exit(1);
36       }
37       for(i=0;i<nbuckets;i++) (h->bucket_list+i)->entry_list=(entry_t *)NULL;
38       h->num_entries = 0;
39       h->num_buckets = nbuckets;
40     }
41     
42     void init_bucket(bucket_t *b) {
43       b->size       = HASHCHUNK;
44       b->next_entry = 0;
45       b->entry_list = (entry_t *)malloc((size_t)(b->size*sizeof(entry_t)));
46       if(!b->entry_list) {
47         printf("hash.c line=%d : Could not allocate entry list\n",__LINE__);
48         exit(1);
49       }
50     }
51     
52     // Create an empty hash with nbuckets
53     
54     int create_hash(int nbuckets)
55     {
56       int i;
57     
58       if(!hash_heap) {
59         hash_heap = (hash_t *)malloc(hash_heap_size*sizeof(hash_t));
60         if(!hash_heap) {
61           printf("hash.c line=%d : Could not allocate hash_heap\n",__LINE__);
62           exit(1);
63         }
64         for(i=0;i<hash_heap_size;i++) hash_heap[i].bucket_list=(bucket_t *)NULL;
65       }
66     
67       for(i=0;i<hash_heap_size;i++) {
68         if(!hash_heap[i].bucket_list){
69           (void)init_hash(hash_heap+i,nbuckets);
70           return i;
71         }
72       }
73     
74       hash_heap = 
75         (hash_t *)realloc(hash_heap,sizeof(hash_t)*(hash_heap_size+=HEAPCHUNK));
76     
77       if(!hash_heap) {
78         printf("hash.c line=%d : Could not expand hash_heap\n",__LINE__);
79         exit(1);
80       }
81     }
82     
83     // Destroy the hash identified by handle h, releasing all its space
84     
85     void destroy_hash(int h)
86     {
87       int i;
88     
89       if(!hash_heap) {
90         printf("hash.c line=%d : Attemp to destroy hash from empty heap\n",__LINE__);
91         exit(1);
92       } else if(!hash_heap[h].bucket_list) {
93         printf("hash.c line=%d : Attemp to destroy uninitalized hash\n",__LINE__);
94         exit(1);
95       } else { 
96         for(i=1;i<hash_heap[h].num_buckets;i++)
97           FREE(hash_heap[h].bucket_list[i].entry_list);
98     
99         FREE(hash_heap[h].bucket_list);
100       }
101     }
102     
103     
104     
105     int hash_size(int h)
106     {
107       int l, num;
108       bucket_t *bucket;
109       hash_t   *hash;
110     
111       hash = hash_heap+h;
112       num  = 0;
113       for(l=0; l<hash->num_buckets; l++) {
114         bucket = hash->bucket_list + l;
115         if(bucket->entry_list) num = num + bucket->next_entry;
116       }
117       return num;
118     }
119     
120     void dump_hash(int h, int *i, int *j)
121     {
122       int l, k, num;
123       bucket_t *bucket;
124       entry_t  *entry;
125       hash_t   *hash;
126     
127       hash = hash_heap+h;
128       num  = 0;
129     
130       for(l=0; l<hash->num_buckets; l++) {
131         bucket = hash->bucket_list + l;
132         for(k=0; k<bucket->next_entry; k++) {
133           entry = (bucket->entry_list) + k;
134           i[num]==entry->i;
135           j[num]==entry->j;
136           num++;
137         }
138       }
139     
140     }
141     
142     
143     // Main hashing method checks hash for (i,j) pair.
144     // If present it returns its Id. If not it adds
145     // to the hash, giving the new entry the next id
146     // value, and returns the Id. Currently the next Id
147     // is determined by incrementing a counter.
148     
149     int increment_hash(int h, int i, int j)
150     {
151     
152       if(!hash_heap) {
153     
154         printf("hash.c line=%d : Attemp to increment hash from empty heap\n",__LINE__);
155         exit(1);
156     
157       } else if(!(hash_heap[h].bucket_list)) {
158     
159         printf("hash.c line=%d : Attemp to increment uninitalized hash %d i=%d j=%d %ld\n",
160     	   __LINE__,h,i,j,hash_heap[h].bucket_list);
161         exit(1);
162     
163       } else {
164     
165         bucket_t *bucket;
166         entry_t  *entry;
167         hash_t   *hash;
168         int key;
169     
170         // Start
171     
172         if(j==INT_MAX) 
173           key=hash1(i);
174         else
175           key=hash2(i,j);
176     
177         hash   = hash_heap+h;
178         bucket = hash->bucket_list + (key & (hash->num_buckets - 1));
179     
180         //    printf("In Hash , bucket= %d \n",(key & (hash->num_buckets - 1)));
181     
182         if(!(bucket->entry_list)) {
183     
184           init_bucket(bucket);
185     
186         } else {
187     
188           int k;
189           //	  printf("In Hash 2, entries= %d \n",hash->num_entries);
190           //	  printf("In Hash 2,   next= %d \n",bucket->next_entry);
191           for(k=0; k<bucket->next_entry; k++) {
192     	entry = (bucket->entry_list) + k;
193     	if(entry->i==i && entry->j==j)
194     	  return entry->k;
195           }
196     
197           if(bucket->next_entry == bucket->size) {
198     	bucket->size      += HASHCHUNK;
199     	bucket->entry_list = 
200     	  (entry_t *)realloc(bucket->entry_list,sizeof(entry_t)*bucket->size);
201     	if(!bucket->entry_list) {
202     	  printf("hash.c %d : Could not reallocate entry list\n",__LINE__);
203     	  exit(1);
204     	}
205           }
206     
207         }
208     
209     
210         ++(hash->num_entries);
211         entry = bucket->entry_list + bucket->next_entry++;
212     
213         entry->i = i;
214         entry->j = j;
215         entry->k = hash->num_entries;
216     
217         return entry->k;
218       }  
219     }
220     
221     // Hash function from 2 ints to 1 int
222     
223     int hash2(int i, int j)
224     { unsigned long long key;
225       key = (unsigned long long)i << 32 | (unsigned long long)j;
226       key = (~key) + (key << 18); // key = (key << 18) - key - 1;
227       key = key ^ (key >> 31);
228       key = key * 21; // key = (key + (key << 2)) + (key << 4);
229       key = key ^ (key >> 11);
230       key = key + (key << 6);
231       key = key ^ (key >> 22);
232       return (int)key;
233     }
234     
235     // Hash function from 1 ints to 1 int
236     
237     int hash1(int key)
238     {
239       key = ~key + (key << 15); // key = (key << 15) - key - 1;
240       key = key ^ (key >> 12);
241       key = key + (key << 2);
242       key = key ^ (key >> 4);
243       key = key * 2057; // key = (key + (key << 3)) + (key << 11);
244       key = key ^ (key >> 16);
245       return key;
246     }
247     
248     // Fortran bindings
249     
250     void DESTROYHASH (int *h){destroy_hash(*h);}
251     void DESTROYHASH_(int *h){destroy_hash(*h);}
252     void destroyhash (int *h){destroy_hash(*h);}
253     void destroyhash_(int *h){destroy_hash(*h);}
254     
255     int INCREMENTHASH (int *h,int *i, int *j){return increment_hash(*h,*i,*j);}
256     int INCREMENTHASH_(int *h,int *i, int *j){return increment_hash(*h,*i,*j);}
257     int incrementhash (int *h,int *i, int *j){return increment_hash(*h,*i,*j);}
258     int incrementhash_(int *h,int *i, int *j){return increment_hash(*h,*i,*j);}
259     
260     int CREATEHASH (int *nbuckets){return create_hash(*nbuckets);}
261     int CREATEHASH_(int *nbuckets){return create_hash(*nbuckets);}
262     int createhash (int *nbuckets){return create_hash(*nbuckets);}
263     int createhash_(int *nbuckets){return create_hash(*nbuckets);}
264     
265     int HASHSIZE (int *h){return hash_size(*h);}
266     int HASHSIZE_(int *h){return hash_size(*h);}
267     int hashsize (int *h){return hash_size(*h);}
268     int hashsize_(int *h){return hash_size(*h);}
269     
270     void DUMPHASH (int *h, int *i,int *j){dump_hash(*h,i,j);}
271     void DUMPHASH_(int *h, int *i,int *j){dump_hash(*h,i,j);}
272     void dumphash (int *h, int *i,int *j){dump_hash(*h,i,j);}
273     void dumphash_(int *h, int *i,int *j){dump_hash(*h,i,j);}
274     
275     #endif
276