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