1 
2 #include "OVOneToOne.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 OneToOne */
10 
11 typedef struct {
12   int active;
13   ov_word forward_value, reverse_value;
14   ov_size forward_next, reverse_next;
15 } up_element;
16 
17 struct _OVOneToOne {
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   ov_word *reverse;
25 };
26 
OVOneToOne_Init(OVOneToOne * up,OVHeap * heap)27 OVstatus OVOneToOne_Init(OVOneToOne * up, OVHeap * heap)
28 {
29   ov_utility_zero_range(up, up + 1);
30   up->heap = heap;
31   return_OVstatus_SUCCESS;
32 }
33 
OVOneToOne_New(OVHeap * heap)34 OVOneToOne *OVOneToOne_New(OVHeap * heap)
35 {
36   OVOneToOne *up;
37   up = OVHeap_ALLOC(heap, OVOneToOne);
38   up->heap = heap;
39   return up;
40 }
41 
OVOneToOne_Purge(OVOneToOne * up)42 void OVOneToOne_Purge(OVOneToOne * up)
43 {
44   if(up) {
45     OVHeapArray_FREE_AUTO_NULL(up->elem);
46     OVHeap_FREE_AUTO_NULL(up->heap, up->forward);
47     OVHeap_FREE_AUTO_NULL(up->heap, up->reverse);
48   }
49 }
50 
OVOneToOne_Del(OVOneToOne * up)51 void OVOneToOne_Del(OVOneToOne * up)
52 {
53   if(up) {
54     OVOneToOne_Purge(up);
55     OVHeap_FREE_AUTO_NULL(up->heap, up);
56   }
57 }
58 
OVOneToOne_Reset(OVOneToOne * up)59 void OVOneToOne_Reset(OVOneToOne * up)
60 {
61   OVOneToOne_Purge(up);
62   OVOneToOne_Init(up, up->heap);
63 }
64 
OVOneToOne_Dump(OVOneToOne * up)65 void OVOneToOne_Dump(OVOneToOne * up)
66 {
67   ov_uword a;
68   ov_boolean empty = OV_TRUE;
69   if(up && up->mask) {
70     for(a = 0; a <= up->mask; a++) {
71       if(up->forward[a] || up->reverse[a]) {
72         fprintf(stderr,
73                 " OVOneToOne_Dump: Hashes forward[0x%02x]->%d    reverse[0x%02x]->%d\n",
74                 (unsigned int) a, (int) up->forward[a],
75                 (unsigned int) a, (int) up->reverse[a]);
76         empty = OV_FALSE;
77       }
78     }
79 
80     for(a = 0; a < up->size; a++)
81       if(up->elem[a].active) {
82         fprintf(stderr,
83                 " OVOneToOne_Dump: Elements %d:    %d (->%d)    %d (->%d)\n",
84                 (int) a + 1,
85                 (int) up->elem[a].forward_value,
86                 (int) up->elem[a].forward_next,
87                 (int) up->elem[a].reverse_value, (int) up->elem[a].reverse_next);
88         empty = OV_FALSE;
89       }
90   }
91   if(empty) {
92     fprintf(stderr, " OVOneToOne_Dump: Empty. \n");
93   }
94 }
95 
Reload(OVOneToOne * up)96 static void Reload(OVOneToOne * up)
97 {                               /* assumes hash tables are clean and initialized to zero */
98 #ifdef DEBUG_UP
99   fprintf(stderr, "Reload-Debug: entered\n");
100 #endif
101   ov_uword mask = up->mask;
102 
103   if(up->elem && mask) {
104     {
105       up_element *elem = up->elem;
106       ov_uword a;
107       for(a = 0; a < up->size; a++) {
108         if(elem->active) {
109           elem->forward_next = 0;       /* 0 is the sentinel for end of list */
110           elem->reverse_next = 0;
111         }
112         elem++;
113       }
114     }
115 
116     {
117       ov_uword a;
118       ov_word *forward = up->forward;
119       ov_word *reverse = up->reverse;
120       up_element *elem = up->elem;
121       {
122         ov_word fwd, rev;
123         ov_word fwd_val;
124         ov_word rev_val;
125         for(a = 0; a < up->size; a++) {
126           if(elem->active) {
127             fwd_val = elem->forward_value;
128             rev_val = elem->reverse_value;
129             fwd = HASH(fwd_val, mask);
130             rev = HASH(rev_val, mask);
131             elem->forward_next = forward[fwd];
132             forward[fwd] = a + 1;       /* NOTE: 1 based indices */
133             elem->reverse_next = reverse[rev];
134             reverse[rev] = a + 1;
135           }
136           elem++;
137         }
138       }
139     }
140   }
141 #ifdef DEBUG_UP
142   {
143     ov_uword a;
144     for(a = 0; a <= up->mask; a++) {
145       fprintf(stderr, "Reload-Debug: forward[%d]=%d, reverse[%d]=%d\n",
146               a, up->forward[a], a, up->reverse[a]);
147     }
148   }
149 #endif
150 
151 }
152 
OVOneToOne_GetReverse(OVOneToOne * up,ov_word reverse_value)153 OVreturn_word OVOneToOne_GetReverse(OVOneToOne * up, ov_word reverse_value)
154 {
155   if(!up) {
156     OVreturn_word result = { OVstatus_NULL_PTR };
157     return result;
158   } else {
159     if(up->mask) {
160       ov_word hash = HASH(reverse_value, up->mask);
161       up_element *elem = up->elem;
162       ov_word index = up->reverse[hash];
163       up_element *cur_elem = elem + (index - 1);
164 
165       while(index) {
166         if(cur_elem->reverse_value == reverse_value) {
167           OVreturn_word result = { OVstatus_SUCCESS };
168           result.word = cur_elem->forward_value;
169           return result;
170         }
171         index = cur_elem->reverse_next;
172         cur_elem = elem + (index - 1);
173       }
174     }
175     {
176       OVreturn_word result = { OVstatus_NOT_FOUND };
177       return result;
178     }
179   }
180 }
181 
OVOneToOne_IterateForward(OVOneToOne * up,ov_word * hidden)182 OVreturn_word OVOneToOne_IterateForward(OVOneToOne * up, ov_word * hidden)
183 {
184   if(!up) {
185     OVreturn_word result = { OVstatus_NULL_PTR };
186     return result;
187   } else {
188     OVreturn_word result = { OVstatus_YES };
189     unsigned int a;
190     up_element *cur_elem = up->elem + (*hidden);
191     for(a = *hidden; a < up->size; a++) {
192       if(cur_elem->active) {
193         result.word = cur_elem->forward_value;
194         *hidden = a + 1;
195         return result;
196       }
197       cur_elem++;
198     }
199     *hidden = 0;
200     result.status = OVstatus_NO;
201     return result;
202   }
203 }
204 
OVOneToOne_GetForward(OVOneToOne * up,ov_word forward_value)205 OVreturn_word OVOneToOne_GetForward(OVOneToOne * up, ov_word forward_value)
206 {
207   if(!up) {
208     OVreturn_word result = { OVstatus_NULL_PTR };
209     return result;
210   } else {
211     ov_uword mask = up->mask;
212     if(mask) {
213       ov_word hash = HASH(forward_value, mask);
214       up_element *elem = up->elem;
215       ov_word index = up->forward[hash];
216       up_element *cur_elem = elem + (index - 1);
217       while(index) {
218         if(cur_elem->forward_value == forward_value) {
219           OVreturn_word result = { OVstatus_SUCCESS };
220           result.word = cur_elem->reverse_value;
221           return result;
222         }
223         index = cur_elem->forward_next;
224         cur_elem = elem + (index - 1);
225       }
226     }
227     {
228       OVreturn_word result = { OVstatus_NOT_FOUND };
229       return result;
230     }
231   }
232 }
233 
Recondition(OVOneToOne * up,ov_uword size,int force)234 static OVstatus Recondition(OVOneToOne * up, ov_uword size, int force)
235 {
236   if(!up) {
237     return_OVstatus_NULL_PTR;
238   } else {
239     ov_uword mask = up->mask;
240 #ifdef DEBUG_UP
241     fprintf(stderr, "Recondition-Debug: entered for size %d.\n", size);
242 #endif
243     if((size > mask) || ((size << 2) < mask) || force) {
244 
245       while((size << 2) < mask) {
246         mask = mask >> 1;
247         if(mask < 2)
248           break;
249       }
250 
251       while(size > mask) {
252         mask = (mask << 1) + 1;
253       }
254 
255 #ifdef DEBUG_UP
256       fprintf(stderr, "Recondition-Debug: mask %d\n", mask);
257 #endif
258       {
259         if(!up->elem) {
260           up->elem = OVHeapArray_CALLOC(up->heap, up_element, size);
261           if(!up->elem) {
262             return_OVstatus_OUT_OF_MEMORY;
263           }
264         }
265         if(mask != up->mask) {
266           ov_word *tmp_forward = OVHeap_CALLOC(up->heap, ov_word, mask + 1);
267           ov_word *tmp_reverse = OVHeap_CALLOC(up->heap, ov_word, mask + 1);
268           if(!(tmp_forward && tmp_reverse)) {   /* validate */
269             OVHeap_FREE_AUTO_NULL(up->heap, tmp_forward);
270             OVHeap_FREE_AUTO_NULL(up->heap, tmp_reverse);
271             /* being unable to condition is not an error */
272           } else {
273             /* impossible to fail after here... */
274             OVHeap_FREE_AUTO_NULL(up->heap, up->forward);
275             OVHeap_FREE_AUTO_NULL(up->heap, up->reverse);
276             up->forward = tmp_forward;
277             up->reverse = tmp_reverse;
278             up->mask = mask;
279           }
280         } else {
281           ov_utility_zero_range(up->forward, up->forward + (up->mask + 1));
282           ov_utility_zero_range(up->reverse, up->reverse + (up->mask + 1));
283         }
284         Reload(up);
285       }
286     }
287   }
288   return_OVstatus_SUCCESS;
289 }
290 
OVOneToOne_Pack(OVOneToOne * up)291 OVstatus OVOneToOne_Pack(OVOneToOne * up)
292 {
293   if(!up) {
294     return_OVstatus_NULL_PTR;
295   } else {
296     if(up->n_inactive && up->elem) {
297       ov_uword new_size = 0;
298       up_element *src = up->elem, *dst = up->elem;
299       ov_uword a;
300 
301       for(a = 0; a < up->size; a++) {
302         if(src->active) {
303           if(src > dst) {
304             *dst = *src;
305           }
306           dst++;
307           new_size++;
308         }
309         src++;
310       }
311       up->n_inactive = 0;
312       up->next_inactive = 0;
313       if(new_size > 0 && new_size < up->size) {
314         if(!OVHeapArray_SET_SIZE(up->elem, up_element, new_size))
315           ov_utility_zero_range(up->elem + new_size, up->elem + up->size);
316       }
317       up->size = new_size;
318       return Recondition(up, new_size, OV_TRUE);
319     }
320     return_OVstatus_SUCCESS;
321   }
322 }
323 
OVOneToOne_GetSize(OVOneToOne * up)324 OVreturn_size OVOneToOne_GetSize(OVOneToOne * up)
325 {
326   if(!up) {
327     OVreturn_size result = { OVstatus_NULL_PTR };
328     return result;
329   } else {
330     OVreturn_size result = { OVstatus_SUCCESS };
331     result.size = up->size - up->n_inactive;
332     return result;
333   }
334 }
335 
OVOneToOne_DelReverse(OVOneToOne * up,ov_word reverse_value)336 OVstatus OVOneToOne_DelReverse(OVOneToOne * up, ov_word reverse_value)
337 {
338   if(!up) {
339     return_OVstatus_NULL_PTR;
340   } else {
341     ov_word mask = up->mask;
342     if(mask) {
343       ov_word rev_hash = HASH(reverse_value, mask);
344       ov_word rev = up->reverse[rev_hash];
345 
346       if(!rev) {
347         return_OVstatus_NOT_FOUND;
348       } else {
349         up_element *rev_elem = NULL;
350         up_element *elem = up->elem;
351         ov_word rev_last = 0;
352 
353         while(rev) {
354           rev_elem = elem + (rev - 1);
355           if(rev_elem->reverse_value == reverse_value)
356             break;
357           rev_last = rev;
358           rev = rev_elem->reverse_next;
359         }
360 
361         if(rev_elem) {
362           ov_word rev_fwd_val = rev_elem->forward_value;
363           ov_word fwd_hash = HASH(rev_fwd_val, mask);
364           ov_word fwd = up->forward[fwd_hash];
365           ov_word fwd_last = 0;
366           up_element *fwd_elem = NULL;
367 
368           while(fwd) {
369             fwd_elem = elem + (fwd - 1);
370             if(fwd_elem == rev_elem)
371               break;
372             fwd_last = fwd;
373             fwd = fwd_elem->forward_next;
374           }
375 
376           if(rev && (rev == fwd)) {
377 
378             /* excise element */
379 
380             if(rev_last)
381               up->elem[rev_last - 1].reverse_next = rev_elem->reverse_next;
382             else
383               up->reverse[rev_hash] = rev_elem->reverse_next;
384 
385             if(fwd_last)
386               up->elem[fwd_last - 1].forward_next = fwd_elem->forward_next;
387             else
388               up->forward[fwd_hash] = fwd_elem->forward_next;
389 
390             /* store as inactive */
391 
392             rev_elem->active = OV_FALSE;
393             rev_elem->forward_next = up->next_inactive;
394             up->next_inactive = rev;
395             up->n_inactive++;
396             if(up->n_inactive > (up->size >> 1))        /* over half of bits are inactive */
397               OVOneToOne_Pack(up);
398             return_OVstatus_SUCCESS;
399           }
400         }
401       }
402     }
403     return_OVstatus_NOT_FOUND;
404   }
405 }
406 
OVOneToOne_DelForward(OVOneToOne * up,ov_word forward_value)407 OVstatus OVOneToOne_DelForward(OVOneToOne * up, ov_word forward_value)
408 {
409   if(!up) {
410     return_OVstatus_NULL_PTR;
411   } else {
412     ov_word mask = up->mask;
413     if(mask) {
414       ov_word fwd_hash = HASH(forward_value, mask);
415       ov_word fwd = up->forward[fwd_hash];
416       if(!fwd) {
417         return_OVstatus_NOT_FOUND;
418       } else {
419         up_element *fwd_elem = NULL;
420         up_element *elem = up->elem;
421         ov_word fwd_last = 0;
422 
423         while(fwd) {
424           fwd_elem = elem + (fwd - 1);
425           if(fwd_elem->forward_value == forward_value)
426             break;
427           fwd_last = fwd;
428           fwd = fwd_elem->forward_next;
429         }
430 
431         if(fwd_elem) {
432           ov_word fwd_rev_val = fwd_elem->reverse_value;
433           ov_word rev_hash = HASH(fwd_rev_val, mask);
434           ov_word rev = up->reverse[rev_hash];
435           ov_word rev_last = 0;
436           up_element *rev_elem = NULL;
437 
438           while(rev) {
439             rev_elem = elem + (rev - 1);
440             if(rev_elem == fwd_elem)
441               break;
442             rev_last = rev;
443             rev = rev_elem->reverse_next;
444           }
445 
446           if(fwd && (fwd == rev)) {
447 
448             /* excise elements */
449 
450             if(fwd_last)
451               up->elem[fwd_last - 1].forward_next = fwd_elem->forward_next;
452             else
453               up->forward[fwd_hash] = fwd_elem->forward_next;
454 
455             if(rev_last)
456               up->elem[rev_last - 1].reverse_next = rev_elem->reverse_next;
457             else
458               up->reverse[rev_hash] = rev_elem->reverse_next;
459 
460             /* store as inactive */
461 
462             fwd_elem->active = OV_FALSE;
463             fwd_elem->forward_next = up->next_inactive;
464             up->next_inactive = fwd;
465             up->n_inactive++;
466             if(up->n_inactive > (up->size >> 1))        /* over half of bits are inactive */
467               OVOneToOne_Pack(up);
468             return_OVstatus_SUCCESS;
469           }
470         }
471       }
472     }
473     return_OVstatus_NOT_FOUND;
474   }
475 }
476 
OVOneToOne_Stats(OVOneToOne * up)477 void OVOneToOne_Stats(OVOneToOne * up)
478 {
479   if(up && up->mask) {
480     int max_len = 0;
481     ov_uword a;
482     for(a = 0; a < up->mask; a++) {
483       {
484         ov_word index = up->forward[a];
485         up_element *elem = up->elem;
486         int cnt = 0;
487         if(index) {
488           up_element *cur_elem;
489           while(index) {
490             cur_elem = elem + (index - 1);
491             index = cur_elem->forward_next;
492             cnt++;
493           }
494           if(cnt > max_len)
495             max_len = cnt;
496         }
497       }
498 
499       {
500         ov_word index = up->reverse[a];
501         up_element *elem = up->elem;
502         int cnt = 0;
503         if(index) {
504           up_element *cur_elem;
505           while(index) {
506             cur_elem = elem + (index - 1);
507             index = cur_elem->reverse_next;
508             cnt++;
509           }
510           if(cnt > max_len)
511             max_len = cnt;
512         }
513       }
514 
515     }
516     fprintf(stderr, " OVOneToOne_Stats: MaxLen=%d ", max_len);
517     fprintf(stderr, "active=%d n_inactive=%d ", (int)( up->size - up->n_inactive),
518             (int) up->n_inactive);
519     fprintf(stderr, "mask=0x%x n_alloc=%lu\n", (unsigned int) up->mask,
520             (unsigned long) OVHeapArray_GET_SIZE(up->elem));
521   }
522 }
523 
OVOneToOne_Set(OVOneToOne * up,ov_word forward_value,ov_word reverse_value)524 OVstatus OVOneToOne_Set(OVOneToOne * up, ov_word forward_value, ov_word reverse_value)
525 {
526   if(!up) {
527     return_OVstatus_NULL_PTR;
528   } else {
529     ov_word mask = up->mask;
530     ov_word fwd_hash = HASH(forward_value, mask);
531     ov_word rev_hash = HASH(reverse_value, mask);
532     up_element *fwd_elem = NULL;
533     up_element *rev_elem = NULL;
534     ov_word fwd;
535     ov_word rev;
536     if(!mask) {
537       fwd = 0;
538       rev = 0;
539     } else {
540 
541       fwd = up->forward[fwd_hash];
542       rev = up->reverse[rev_hash];
543 
544 #ifdef DEBUG_OVOneToOne
545       fprintf(stderr, "OVOneToOneSet-Debug: set %d,%d\n", forward_value, reverse_value);
546       fprintf(stderr, "OVOneToOneSet-Debug: fwd_hash %d rev_hash %d mask %d size %d\n",
547               fwd_hash, rev_hash, up->mask, up->size);
548       fprintf(stderr, "OVOneToOneSet-Debug: before search fwd rev %d %d\n", fwd, rev);
549 #endif
550 
551       {                         /* find elements if they exist, and detect erroneous conditions */
552 
553         up_element *elem = up->elem;
554 
555 #ifdef DEBUG_OVOneToOne
556         {
557           int a;
558           for(a = 0; a < up->size; a++) {
559             fprintf(stderr, "OVOneToOneSet-Debug: on entry %d forward_next: %d\n",
560                     a + 1, elem[a].forward_next);
561           }
562 
563           for(a = 0; a <= up->mask; a++) {
564             fprintf(stderr,
565                     "OVOneToOneSet-Debug: on entry %d forward hash %d: reverse_hash: %d\n",
566                     a, up->forward[a], up->reverse[a]);
567           }
568         }
569 #endif
570 
571         while(fwd) {
572           fwd_elem = elem + (fwd - 1);
573           if(fwd_elem->forward_value == forward_value)
574             break;
575           fwd = fwd_elem->forward_next;
576         }
577         while(rev) {
578           rev_elem = elem + (rev - 1);
579           if(rev_elem->reverse_value == reverse_value)
580             break;
581           rev = rev_elem->reverse_next;
582         }
583       }
584 
585       if((fwd && (!rev)) || (rev && (!fwd))) {
586         return_OVstatus_DUPLICATE;
587       }
588     }
589     if(!(fwd || rev)) {
590       ov_size new_index;
591       /* new pair */
592 #ifdef DEBUG_OVOneToOne
593       fprintf(stderr, "OVOneToOneSet-Debug: New pair.\n");
594 #endif
595       if(up->n_inactive) {
596         new_index = up->next_inactive;
597         up->next_inactive = up->elem[new_index - 1].forward_next;
598         up->n_inactive--;
599       } else {
600         if(up->elem && (!OVHeapArray_CHECK(up->elem, up_element, up->size))) {
601           return_OVstatus_OUT_OF_MEMORY;
602         } else {
603           OVstatus result;
604           if(OVreturn_IS_ERROR(result = Recondition(up, up->size + 1, OV_FALSE))) {
605             return result;
606           } else {
607             /* guaranteed to succeed past this point, so we can increase size */
608             new_index = ++up->size;
609           }
610         }
611       }
612       {
613         up_element *elem = up->elem + (new_index - 1);
614         elem->forward_value = forward_value;
615         elem->reverse_value = reverse_value;
616         elem->active = OV_TRUE;
617 
618         /* regenerate new hashes */
619         mask = up->mask;
620         fwd_hash = HASH(forward_value, mask);
621         rev_hash = HASH(reverse_value, mask);
622 
623         {
624           ov_word *forward_start_index = up->forward + fwd_hash;
625           ov_word *reverse_start_index = up->reverse + rev_hash;
626 
627           elem->forward_next = *forward_start_index;
628           *forward_start_index = new_index;     /* note the +1 offset */
629           elem->reverse_next = *reverse_start_index;
630           *reverse_start_index = new_index;     /* note the +1 offset */
631         }
632 
633 #ifdef DEBUG_OVOneToOne
634         {
635           int a;
636           for(a = 0; a <= up->mask; a++) {
637             fprintf(stderr, "OVOneToOneSet-Debug: forward[%d]=%d, reverse[%d]=%d\n",
638                     a, up->forward[a], a, up->reverse[a]);
639           }
640         }
641 #endif
642 
643       }
644 
645     } else if(fwd_elem != rev_elem) {
646       return_OVstatus_MISMATCH;
647     } else {
648       return_OVstatus_NO_EFFECT;
649       /* exists and matched, so do nothing */
650     }
651   }
652   return_OVstatus_SUCCESS;
653 }
654