1 
2 #include "OVOneToAny.h"
3 #include "OVHeapArray.h"
4 #include "ov_utility.h"
5 
6 #define HASH(value,mask) (((value^(value>>24))^((value>>8)^(value>>16)))&mask)
7 
8 
9 /* FYI: "up" stands for UniquePair -- a precursor to OneToAny */
10 
11 typedef struct {
12   int active;
13   ov_word forward_value, reverse_value;
14   ov_size forward_next;
15 } up_element;
16 
17 struct _OVOneToAny {
18   OVHeap *heap;
19   ov_uword mask;
20   ov_size size, n_inactive;
21   ov_word next_inactive;
22   up_element *elem;
23   ov_word *forward;
24 };
25 
OVOneToAny_Init(OVOneToAny * up,OVHeap * heap)26 OVstatus OVOneToAny_Init(OVOneToAny * up, OVHeap * heap)
27 {
28   ov_utility_zero_range(up, up + 1);
29   up->heap = heap;
30   return_OVstatus_SUCCESS;
31 }
32 
OVOneToAny_New(OVHeap * heap)33 OVOneToAny *OVOneToAny_New(OVHeap * heap)
34 {
35   OVOneToAny *up;
36   up = OVHeap_ALLOC(heap, OVOneToAny);
37   up->heap = heap;
38   return up;
39 }
40 
OVOneToAny_Purge(OVOneToAny * up)41 void OVOneToAny_Purge(OVOneToAny * up)
42 {
43   if(up) {
44     OVHeapArray_FREE_AUTO_NULL(up->elem);
45     OVHeap_FREE_AUTO_NULL(up->heap, up->forward);
46   }
47 }
48 
OVOneToAny_Del(OVOneToAny * up)49 void OVOneToAny_Del(OVOneToAny * up)
50 {
51   if(up) {
52     OVOneToAny_Purge(up);
53     OVHeap_FREE_AUTO_NULL(up->heap, up);
54   }
55 }
56 
OVOneToAny_Reset(OVOneToAny * up)57 void OVOneToAny_Reset(OVOneToAny * up)
58 {
59   OVOneToAny_Purge(up);
60   OVOneToAny_Init(up, up->heap);
61 }
62 
OVOneToAny_Dump(OVOneToAny * up)63 void OVOneToAny_Dump(OVOneToAny * up)
64 {
65   ov_uword a;
66   ov_boolean empty = OV_TRUE;
67   if(up && up->mask) {
68     for(a = 0; a <= up->mask; a++) {
69       if(up->forward[a]) {
70         fprintf(stderr,
71                 " OVOneToAny_Dump: Hashes forward[0x%02x]->%d\n",
72                 (unsigned int) a, (int) up->forward[a]);
73         empty = OV_FALSE;
74       }
75     }
76 
77     for(a = 0; a < up->size; a++)
78       if(up->elem[a].active) {
79         fprintf(stderr,
80                 " OVOneToAny_Dump: Elements %d:    %d (->%d)    %d \n",
81                 (int) a + 1,
82                 (int) up->elem[a].forward_value,
83                 (int) up->elem[a].forward_next, (int) up->elem[a].reverse_value);
84         empty = OV_FALSE;
85       }
86   }
87   if(empty) {
88     fprintf(stderr, " OVOneToAny_Dump: Empty.\n");
89   }
90 }
91 
Reload(OVOneToAny * up)92 static void Reload(OVOneToAny * up)
93 {                               /* assumes hash tables are clean and initialized to zero */
94 #ifdef DEBUG_UP
95   fprintf(stderr, "Reload-Debug: entered\n");
96 #endif
97   ov_uword mask = up->mask;
98 
99   if(up->elem && mask) {
100     {
101       up_element *elem = up->elem;
102       ov_uword a;
103       for(a = 0; a < up->size; a++) {
104         if(elem->active) {
105           elem->forward_next = 0;       /* 0 is the sentinel for end of list */
106         }
107         elem++;
108       }
109     }
110 
111     {
112       ov_uword a;
113       ov_word *forward = up->forward;
114       up_element *elem = up->elem;
115       {
116         ov_word fwd;
117         ov_word fwd_val;
118         for(a = 0; a < up->size; a++) {
119           if(elem->active) {
120             fwd_val = elem->forward_value;
121             fwd = HASH(fwd_val, mask);
122             elem->forward_next = forward[fwd];
123             forward[fwd] = a + 1;       /* NOTE: 1 based indices */
124           }
125           elem++;
126         }
127       }
128     }
129   }
130 #ifdef DEBUG_UP
131   {
132     ov_uword a;
133     for(a = 0; a <= up->mask; a++) {
134       fprintf(stderr, "Reload-Debug: forward[%d]=%d\n", a, up->forward[a],);
135     }
136   }
137 #endif
138 
139 }
140 
OVOneToAny_GetKey(OVOneToAny * up,ov_word forward_value)141 OVreturn_word OVOneToAny_GetKey(OVOneToAny * up, ov_word forward_value)
142 {
143 #ifdef DEBUG_OVOneToAny
144   fprintf(stderr, "OVOneToAnyGetKey-Debug: %d\n", forward_value);
145 #endif
146   if(!up) {
147     OVreturn_word result = { OVstatus_NULL_PTR };
148     return result;
149   } else {
150     ov_uword mask = up->mask;
151     if(mask) {
152       ov_word hash = HASH(forward_value, mask);
153       up_element *elem = up->elem;
154       ov_word index = up->forward[hash];
155       up_element *cur_elem = elem + (index - 1);
156 #ifdef DEBUG_OVOneToAny
157       fprintf(stderr, "OVOneToAnyGetKey-Debug: hash %d index %d\n", hash, index);
158 #endif
159 
160       while(index) {
161 #ifdef DEBUG_OVOneToAny
162         fprintf(stderr, "OVOneToAnyGetKey-Debug: index %d forward_value %d\n", index,
163                 cur_elem->forward_value);
164 #endif
165 
166         if(cur_elem->forward_value == forward_value) {
167           OVreturn_word result = { OVstatus_SUCCESS };
168           result.word = cur_elem->reverse_value;
169           return result;
170         }
171         index = cur_elem->forward_next;
172         cur_elem = elem + (index - 1);
173       }
174     }
175     {
176       OVreturn_word result = { OVstatus_NOT_FOUND };
177       return result;
178     }
179   }
180 }
181 
Recondition(OVOneToAny * up,ov_uword size,int force)182 static OVstatus Recondition(OVOneToAny * up, ov_uword size, int force)
183 {
184   if(!up) {
185     return_OVstatus_NULL_PTR;
186   } else {
187     ov_uword mask = up->mask;
188 #ifdef DEBUG_UP
189     fprintf(stderr, "Recondition-Debug: entered for size %d.\n", size);
190 #endif
191     if((size > mask) || ((size << 2) < mask) || force) {
192 
193       while((size << 2) < mask) {
194         mask = mask >> 1;
195         if(mask < 2)
196           break;
197       }
198 
199       while(size > mask) {
200         mask = (mask << 1) + 1;
201       }
202 
203 #ifdef DEBUG_UP
204       fprintf(stderr, "Recondition-Debug: mask %d\n", mask);
205 #endif
206       {
207         if(!up->elem) {
208           up->elem = OVHeapArray_CALLOC(up->heap, up_element, size);
209           if(!up->elem) {
210             return_OVstatus_OUT_OF_MEMORY;
211           }
212         }
213         if(mask != up->mask) {
214           ov_word *tmp_forward = OVHeap_CALLOC(up->heap, ov_word, mask + 1);
215           if(!tmp_forward) {    /* validate */
216             OVHeap_FREE_AUTO_NULL(up->heap, tmp_forward);
217             /* being unable to condition is not an error */
218           } else {
219             /* impossible to fail after here... */
220             OVHeap_FREE_AUTO_NULL(up->heap, up->forward);
221             up->forward = tmp_forward;
222             up->mask = mask;
223           }
224         } else {
225           ov_utility_zero_range(up->forward, up->forward + (up->mask + 1));
226         }
227         Reload(up);
228       }
229     }
230   }
231   return_OVstatus_SUCCESS;
232 }
233 
OVOneToAny_Pack(OVOneToAny * up)234 OVstatus OVOneToAny_Pack(OVOneToAny * up)
235 {
236   if(!up) {
237     return_OVstatus_NULL_PTR;
238   } else {
239     if(up->n_inactive && up->elem) {
240       ov_uword new_size = 0;
241       up_element *src = up->elem, *dst = up->elem;
242       ov_uword a;
243 
244       for(a = 0; a < up->size; a++) {
245         if(src->active) {
246           if(src > dst) {
247             *dst = *src;
248           }
249           dst++;
250           new_size++;
251         }
252         src++;
253       }
254       up->n_inactive = 0;
255       up->next_inactive = 0;
256       if(new_size > 0 && new_size < up->size) {
257         if(!OVHeapArray_SET_SIZE(up->elem, up_element, new_size))
258           ov_utility_zero_range(up->elem + new_size, up->elem + up->size);
259       }
260       up->size = new_size;
261       return Recondition(up, new_size, OV_TRUE);
262     }
263     return_OVstatus_SUCCESS;
264   }
265 }
266 
OVOneToAny_GetSize(OVOneToAny * up)267 OVreturn_size OVOneToAny_GetSize(OVOneToAny * up)
268 {
269   if(!up) {
270     OVreturn_size result = { OVstatus_NULL_PTR };
271     return result;
272   } else {
273     OVreturn_size result = { OVstatus_SUCCESS };
274     result.size = up->size - up->n_inactive;
275     return result;
276   }
277 }
278 
OVOneToAny_DelKey(OVOneToAny * up,ov_word forward_value)279 OVstatus OVOneToAny_DelKey(OVOneToAny * up, ov_word forward_value)
280 {
281   if(!up) {
282     return_OVstatus_NULL_PTR;
283   } else {
284     ov_word mask = up->mask;
285     if(mask) {
286       ov_word fwd_hash = HASH(forward_value, mask);
287       ov_word fwd = up->forward[fwd_hash];
288       if(!fwd) {
289         return_OVstatus_NOT_FOUND;
290       } else {
291         up_element *fwd_elem = NULL;
292         up_element *elem = up->elem;
293         ov_word fwd_last = 0;
294 
295         while(fwd) {
296           fwd_elem = elem + (fwd - 1);
297           if(fwd_elem->forward_value == forward_value)
298             break;
299           fwd_last = fwd;
300           fwd = fwd_elem->forward_next;
301         }
302 
303         if(fwd_elem) {
304           if(fwd) {
305 
306             /* excise elements */
307 
308             if(fwd_last)
309               up->elem[fwd_last - 1].forward_next = fwd_elem->forward_next;
310             else
311               up->forward[fwd_hash] = fwd_elem->forward_next;
312 
313             /* store as inactive */
314 
315             fwd_elem->active = OV_FALSE;
316             fwd_elem->forward_next = up->next_inactive;
317             up->next_inactive = fwd;
318             up->n_inactive++;
319             if(up->n_inactive > (up->size >> 1))        /* over half of bits are inactive */
320               OVOneToAny_Pack(up);
321             return_OVstatus_SUCCESS;
322           }
323         }
324       }
325     }
326     return_OVstatus_NOT_FOUND;
327   }
328 }
329 
OVOneToAny_Stats(OVOneToAny * up)330 void OVOneToAny_Stats(OVOneToAny * up)
331 {
332   if(up && up->mask) {
333     int max_len = 0;
334     ov_uword a;
335     for(a = 0; a < up->mask; a++) {
336       {
337         ov_word index = up->forward[a];
338         up_element *elem = up->elem;
339         int cnt = 0;
340         if(index) {
341           up_element *cur_elem;
342           while(index) {
343             cur_elem = elem + (index - 1);
344             index = cur_elem->forward_next;
345             cnt++;
346           }
347           if(cnt > max_len)
348             max_len = cnt;
349         }
350       }
351 
352     }
353     fprintf(stderr, " OVOneToAny_Stats: MaxLen=%d ", (int) max_len);
354     fprintf(stderr, "active=%d n_inactive=%d ", (int) (up->size - up->n_inactive),
355             (int) up->n_inactive);
356     fprintf(stderr, "mask=0x%x n_alloc=%lu\n", (unsigned int) up->mask,
357             (unsigned long) OVHeapArray_GET_SIZE(up->elem));
358   }
359 }
360 
OVOneToAny_SetKey(OVOneToAny * up,ov_word forward_value,ov_word reverse_value)361 OVstatus OVOneToAny_SetKey(OVOneToAny * up, ov_word forward_value, ov_word reverse_value)
362 {
363 #ifdef DEBUG_OVOneToAny
364   fprintf(stderr, "OVOneToAnySetKey-Debug: %d,%d\n", forward_value, reverse_value);
365 #endif
366   if(!up) {
367     return_OVstatus_NULL_PTR;
368   } else {
369     ov_word mask = up->mask;
370     ov_word fwd_hash = HASH(forward_value, mask);
371     up_element *fwd_elem = NULL;
372     up_element *rev_elem = NULL;
373     ov_word fwd;
374     if(!mask) {
375       fwd = 0;
376     } else {
377 
378       fwd = up->forward[fwd_hash];
379 
380 #ifdef DEBUG_OVOneToAny
381       fprintf(stderr, "OVOneToAnySet-Debug: fwd_hash %d mask %d size %d\n",
382               fwd_hash, up->mask, up->size);
383       fprintf(stderr, "OVOneToAnySet-Debug: before search fwd %d \n", fwd);
384 #endif
385 
386       {                         /* find elements if they exist, and detect erroneous conditions */
387 
388         up_element *elem = up->elem;
389 
390 #ifdef DEBUG_OVOneToAny
391         {
392           int a;
393           for(a = 0; a < up->size; a++) {
394             fprintf(stderr, "OVOneToAnySet-Debug: on entry %d forward_next: %d\n",
395                     a + 1, elem[a].forward_next);
396           }
397 
398           for(a = 0; a <= up->mask; a++) {
399             fprintf(stderr,
400                     "OVOneToAnySet-Debug: on entry %d forward[%d]=%d:\n",
401                     a, a, up->forward[a]);
402           }
403         }
404 #endif
405 
406         while(fwd) {
407           fwd_elem = elem + (fwd - 1);
408           if(fwd_elem->forward_value == forward_value)
409             break;
410           fwd = fwd_elem->forward_next;
411         }
412       }
413 
414       if(fwd) {
415         return_OVstatus_DUPLICATE;
416       }
417     }
418     if(!(fwd)) {                /* new entry */
419       ov_size new_index;
420       /* new pair */
421 #ifdef DEBUG_OVOneToAny
422       fprintf(stderr, "OVOneToAnySet-Debug: New pair.\n");
423 #endif
424       if(up->n_inactive) {
425         new_index = up->next_inactive;
426         up->next_inactive = up->elem[new_index - 1].forward_next;
427         up->n_inactive--;
428       } else {
429         if(up->elem && (!OVHeapArray_CHECK(up->elem, up_element, up->size))) {
430           return_OVstatus_OUT_OF_MEMORY;
431         } else {
432           OVstatus result;
433           if(OVreturn_IS_ERROR(result = Recondition(up, up->size + 1, OV_FALSE))) {
434             return result;
435           } else {
436             /* guaranteed to succeed past this point, so we can increase size */
437             new_index = ++up->size;
438           }
439         }
440       }
441       {
442         up_element *elem = up->elem + (new_index - 1);
443         elem->forward_value = forward_value;
444         elem->reverse_value = reverse_value;
445         elem->active = OV_TRUE;
446 
447         /* regenerate new hashes */
448         mask = up->mask;
449         fwd_hash = HASH(forward_value, mask);
450 
451         {
452           ov_word *forward_start_index = up->forward + fwd_hash;
453 
454           elem->forward_next = *forward_start_index;
455           *forward_start_index = new_index;     /* note the +1 offset */
456         }
457 
458 #ifdef DEBUG_OVOneToAny
459         {
460           int a;
461           for(a = 0; a <= up->mask; a++) {
462             fprintf(stderr, "OVOneToAnySet-Debug: forward[%d]=%d\n", a, up->forward[a]);
463           }
464         }
465 #endif
466 
467       }
468 
469     } else if(fwd_elem != rev_elem) {
470       return_OVstatus_MISMATCH;
471     } else {
472       return_OVstatus_NO_EFFECT;
473       /* exists and matched, so do nothing */
474     }
475   }
476   return_OVstatus_SUCCESS;
477 }
478