1 // store.c
2 // ipdb / ipup / geod
3 //
4 // Created by Dr. Rolf Jansen on 2016-07-10.
5 // Copyright (c) 2016 projectworld.net. All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without modification,
8 // are permitted provided that the following conditions are met:
9 //
10 // 1. Redistributions of source code must retain the above copyright notice,
11 // this list of conditions and the following disclaimer.
12 //
13 // 2. Redistributions in binary form must reproduce the above copyright notice,
14 // this list of conditions and the following disclaimer in the documentation
15 // and/or other materials provided with the distribution.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
18 // OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
19 // AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
20 // OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
23 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
24 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <stdbool.h>
30 #include <stdint.h>
31 #include <math.h>
32 #include <string.h>
33
34 #include "binutils.h"
35 #include "store.h"
36
37
38 #pragma mark ••• AVL Tree of IPv4-Ranges •••
39
balanceIP4Node(IP4Node ** node)40 static int balanceIP4Node(IP4Node **node)
41 {
42 int change = 0;
43 IP4Node *o = *node;
44 IP4Node *p, *q;
45
46 if (o->B == -2)
47 {
48 if (p = o->L) // make the static analyzer happy
49 if (p->B == +1)
50 {
51 change = 1; // double left-right rotation
52 q = p->R; // left rotation
53 p->R = q->L;
54 q->L = p;
55 o->L = q->R; // right rotation
56 q->R = o;
57 o->B = +(q->B < 0);
58 p->B = -(q->B > 0);
59 q->B = 0;
60 *node = q;
61 }
62
63 else
64 {
65 change = p->B; // single right rotation
66 o->L = p->R;
67 p->R = o;
68 o->B = -(++p->B);
69 *node = p;
70 }
71 }
72
73 else if (o->B == +2)
74 {
75 if (q = o->R) // make the static analyzer happy
76 if (q->B == -1)
77 {
78 change = 1; // double right-left rotation
79 p = q->L; // right rotation
80 q->L = p->R;
81 p->R = q;
82 o->R = p->L; // left rotation
83 p->L = o;
84 o->B = -(p->B > 0);
85 q->B = +(p->B < 0);
86 p->B = 0;
87 *node = p;
88 }
89
90 else
91 {
92 change = q->B; // single left rotation
93 o->R = q->L;
94 q->L = o;
95 o->B = -(--q->B);
96 *node = q;
97 }
98 }
99
100 return change != 0;
101 }
102
103
pickPrevIP4Node(IP4Node ** node,IP4Node ** exch)104 static int pickPrevIP4Node(IP4Node **node, IP4Node **exch)
105 { // *exch on entry = parent node
106 IP4Node *o = *node; // *exch on exit = picked previous value node
107
108 if (o->R)
109 {
110 *exch = o;
111 int change = -pickPrevIP4Node(&o->R, exch);
112 if (change)
113 if (abs(o->B += change) > 1)
114 return balanceIP4Node(node);
115 else
116 return o->B == 0;
117 else
118 return 0;
119 }
120
121 else if (o->L)
122 {
123 IP4Node *p = o->L;
124 o->L = NULL;
125 (*exch)->R = p;
126 *exch = o;
127 return p->B == 0;
128 }
129
130 else
131 {
132 (*exch)->R = NULL;
133 *exch = o;
134 return 1;
135 }
136 }
137
138
pickNextIP4Node(IP4Node ** node,IP4Node ** exch)139 static int pickNextIP4Node(IP4Node **node, IP4Node **exch)
140 { // *exch on entry = parent node
141 IP4Node *o = *node; // *exch on exit = picked next value node
142
143 if (o->L)
144 {
145 *exch = o;
146 int change = +pickNextIP4Node(&o->L, exch);
147 if (change)
148 if (abs(o->B += change) > 1)
149 return balanceIP4Node(node);
150 else
151 return o->B == 0;
152 else
153 return 0;
154 }
155
156 else if (o->R)
157 {
158 IP4Node *q = o->R;
159 o->R = NULL;
160 (*exch)->L = q;
161 *exch = o;
162 return q->B == 0;
163 }
164
165 else
166 {
167 (*exch)->L = NULL;
168 *exch = o;
169 return 1;
170 }
171 }
172
173
findIP4Node(uint32_t ip,IP4Node * node)174 IP4Node *findIP4Node(uint32_t ip, IP4Node *node)
175 {
176 if (node)
177 {
178 if (node->lo <= ip && ip <= node->hi)
179 return node;
180
181 else if (ip < node->lo)
182 return findIP4Node(ip, node->L);
183
184 else // (ip > node->hi)
185 return findIP4Node(ip, node->R);
186 }
187 else
188 return NULL;
189 }
190
191
findNet4Node(uint32_t lo,uint32_t hi,uint32_t cc,IP4Node * node)192 IP4Node *findNet4Node(uint32_t lo, uint32_t hi, uint32_t cc, IP4Node *node)
193 {
194 if (node)
195 {
196 int ofs = (cc == node->cc);
197
198 if (node->lo <= lo && lo-ofs <= node->hi || node->lo <= hi+ofs && hi <= node->hi || lo <= node->lo && node->hi <= hi)
199 return node;
200
201 else if (lo < node->lo)
202 return findNet4Node(lo, hi, cc, node->L);
203
204 else // ([lo|hi] > node->hi)
205 return findNet4Node(lo, hi, cc, node->R);
206 }
207 else
208 return NULL;
209 }
210
211
addIP4Node(uint32_t lo,uint32_t hi,uint32_t cc,IP4Node ** node)212 int addIP4Node(uint32_t lo, uint32_t hi, uint32_t cc, IP4Node **node)
213 {
214 IP4Node *o = *node;
215
216 if (o != NULL)
217 {
218 int change;
219
220 if (lo < o->lo)
221 change = -addIP4Node(lo, hi, cc, &o->L);
222
223 else if (lo > o->lo)
224 change = +addIP4Node(lo, hi, cc, &o->R);
225
226 else // (lo == o->lo) // this case must not happen !!!
227 return 0;
228
229 if (change)
230 if (abs(o->B += change) > 1)
231 return 1 - balanceIP4Node(node);
232 else
233 return o->B != 0;
234 else
235 return 0;
236 }
237
238 else // (o == NULL) // if the IP4Node is not in the tree
239 { // then add it into a new leaf
240 if (o = allocate(sizeof(IP4Node), true))
241 {
242 o->lo = lo;
243 o->hi = hi;
244 o->cc = cc;
245 *node = o; // report back the new node
246 return 1; // add the weight of 1 leaf onto the balance
247 }
248
249 return 0; // Out of Memory situation, nothing changed
250 }
251 }
252
253
removeIP4Node(uint32_t ip,IP4Node ** node)254 int removeIP4Node(uint32_t ip, IP4Node **node)
255 {
256 IP4Node *o = *node;
257
258 if (o != NULL)
259 {
260 int change;
261
262 if (ip < o->lo)
263 change = +removeIP4Node(ip, &o->L);
264
265 else if (ip > o->lo)
266 change = -removeIP4Node(ip, &o->R);
267
268 else // (o->lo <= ip && ip <= o->lo)
269 {
270 int b = o->B;
271 IP4Node *p = o->L;
272 IP4Node *q = o->R;
273
274 if (!p || !q)
275 {
276 deallocate(VPR(*node), false);
277 *node = (p > q) ? p : q;
278 return 1; // remove the weight of 1 leaf from the balance
279 }
280
281 else
282 {
283 if (b == -1)
284 {
285 if (!p->R)
286 {
287 change = +1;
288 o = p;
289 o->R = q;
290 }
291 else
292 {
293 change = +pickPrevIP4Node(&p, &o);
294 o->L = p;
295 o->R = q;
296 }
297 }
298
299 else
300 {
301 if (!q->L)
302 {
303 change = -1;
304 o = q;
305 o->L = p;
306 }
307 else
308 {
309 change = -pickNextIP4Node(&q, &o);
310 o->L = p;
311 o->R = q;
312 }
313 }
314
315 o->B = b;
316 deallocate(VPR(*node), false);
317 *node = o;
318 }
319 }
320
321 if (change)
322 if (abs(o->B += change) > 1)
323 return balanceIP4Node(node);
324 else
325 return o->B == 0;
326 else
327 return 0;
328 }
329
330 else // (o == NULL)
331 return 0; // not found -> recursively do nothing
332 }
333
334
serializeIP4Tree(FILE * out,IP4Node * node)335 void serializeIP4Tree(FILE *out, IP4Node *node)
336 {
337 if (node)
338 {
339 if (node->L)
340 serializeIP4Tree(out, node->L);
341
342 IP4Set set = {node->lo, node->hi, node->cc};
343 fwrite(set, sizeof(IP4Set), 1, out);
344
345 if (node->R)
346 serializeIP4Tree(out, node->R);
347 }
348 }
349
350
releaseIP4Tree(IP4Node * node)351 void releaseIP4Tree(IP4Node *node)
352 {
353 if (node)
354 {
355 if (node->L)
356 releaseIP4Tree(node->L);
357
358 if (node->R)
359 releaseIP4Tree(node->R);
360
361 deallocate(VPR(node), false);
362 }
363 }
364
365
366 #pragma mark ••• AVL Tree of IPv6-Ranges •••
367
balanceIP6Node(IP6Node ** node)368 static int balanceIP6Node(IP6Node **node)
369 {
370 int change = 0;
371 IP6Node *o = *node;
372 IP6Node *p, *q;
373
374 if (o->B == -2)
375 {
376 if (p = o->L) // make the static analyzer happy
377 if (p->B == +1)
378 {
379 change = 1; // double left-right rotation
380 q = p->R; // left rotation
381 p->R = q->L;
382 q->L = p;
383 o->L = q->R; // right rotation
384 q->R = o;
385 o->B = +(q->B < 0);
386 p->B = -(q->B > 0);
387 q->B = 0;
388 *node = q;
389 }
390
391 else
392 {
393 change = p->B; // single right rotation
394 o->L = p->R;
395 p->R = o;
396 o->B = -(++p->B);
397 *node = p;
398 }
399 }
400
401 else if (o->B == +2)
402 {
403 if (q = o->R) // make the static analyzer happy
404 if (q->B == -1)
405 {
406 change = 1; // double right-left rotation
407 p = q->L; // right rotation
408 q->L = p->R;
409 p->R = q;
410 o->R = p->L; // left rotation
411 p->L = o;
412 o->B = -(p->B > 0);
413 q->B = +(p->B < 0);
414 p->B = 0;
415 *node = p;
416 }
417
418 else
419 {
420 change = q->B; // single left rotation
421 o->R = q->L;
422 q->L = o;
423 o->B = -(--q->B);
424 *node = q;
425 }
426 }
427
428 return change != 0;
429 }
430
431
pickPrevIP6Node(IP6Node ** node,IP6Node ** exch)432 static int pickPrevIP6Node(IP6Node **node, IP6Node **exch)
433 { // *exch on entry = parent node
434 IP6Node *o = *node; // *exch on exit = picked previous value node
435
436 if (o->R)
437 {
438 *exch = o;
439 int change = -pickPrevIP6Node(&o->R, exch);
440 if (change)
441 if (abs(o->B += change) > 1)
442 return balanceIP6Node(node);
443 else
444 return o->B == 0;
445 else
446 return 0;
447 }
448
449 else if (o->L)
450 {
451 IP6Node *p = o->L;
452 o->L = NULL;
453 (*exch)->R = p;
454 *exch = o;
455 return p->B == 0;
456 }
457
458 else
459 {
460 (*exch)->R = NULL;
461 *exch = o;
462 return 1;
463 }
464 }
465
466
pickNextIP6Node(IP6Node ** node,IP6Node ** exch)467 static int pickNextIP6Node(IP6Node **node, IP6Node **exch)
468 { // *exch on entry = parent node
469 IP6Node *o = *node; // *exch on exit = picked next value node
470
471 if (o->L)
472 {
473 *exch = o;
474 int change = +pickNextIP6Node(&o->L, exch);
475 if (change)
476 if (abs(o->B += change) > 1)
477 return balanceIP6Node(node);
478 else
479 return o->B == 0;
480 else
481 return 0;
482 }
483
484 else if (o->R)
485 {
486 IP6Node *q = o->R;
487 o->R = NULL;
488 (*exch)->L = q;
489 *exch = o;
490 return q->B == 0;
491 }
492
493 else
494 {
495 (*exch)->L = NULL;
496 *exch = o;
497 return 1;
498 }
499 }
500
501
findIP6Node(uint128t ip,IP6Node * node)502 IP6Node *findIP6Node(uint128t ip, IP6Node *node)
503 {
504 if (node)
505 {
506 if (le_u128(node->lo, ip) && le_u128(ip, node->hi))
507 return node;
508
509 else if (lt_u128(ip, node->lo))
510 return findIP6Node(ip, node->L);
511
512 else // (gt_u128(ip, node->hi))
513 return findIP6Node(ip, node->R);
514 }
515 else
516 return NULL;
517 }
518
519
findNet6Node(uint128t lo,uint128t hi,uint32_t cc,IP6Node * node)520 IP6Node *findNet6Node(uint128t lo, uint128t hi, uint32_t cc, IP6Node *node)
521 {
522 if (node)
523 {
524 uint128t ofs = u64_to_u128t(cc == node->cc);
525
526 if (le_u128(node->lo, lo) && le_u128(sub_u128(lo,ofs), node->hi) || le_u128(node->lo, add_u128(hi,ofs)) && le_u128(hi, node->hi) || le_u128(lo, node->lo) && le_u128(node->hi, hi))
527 return node;
528
529 else if (lt_u128(lo, node->lo))
530 return findNet6Node(lo, hi, cc, node->L);
531
532 else // (gt_u128([lo|hi], node->hi))
533 return findNet6Node(lo, hi, cc, node->R);
534 }
535 else
536 return NULL;
537 }
538
539
addIP6Node(uint128t lo,uint128t hi,uint32_t cc,IP6Node ** node)540 int addIP6Node(uint128t lo, uint128t hi, uint32_t cc, IP6Node **node)
541 {
542 IP6Node *o = *node;
543
544 if (o != NULL)
545 {
546 int change;
547
548 if (lt_u128(lo, o->lo))
549 change = -addIP6Node(lo, hi, cc, &o->L);
550
551 else if (gt_u128(lo, o->lo))
552 change = +addIP6Node(lo, hi, cc, &o->R);
553
554 else // (eq_u128(lo, o->lo)) // this case must not happen !!!
555 return 0;
556
557 if (change)
558 if (abs(o->B += change) > 1)
559 return 1 - balanceIP6Node(node);
560 else
561 return o->B != 0;
562 else
563 return 0;
564 }
565
566 else // (o == NULL) // if the IP6Node is not in the tree
567 { // then add it into a new leaf
568 if (o = allocate(sizeof(IP6Node), true))
569 {
570 o->lo = lo;
571 o->hi = hi;
572 o->cc = cc;
573 *node = o; // report back the new node
574 return 1; // add the weight of 1 leaf onto the balance
575 }
576
577 return 0; // Out of Memory situation, nothing changed
578 }
579 }
580
581
removeIP6Node(uint128t ip,IP6Node ** node)582 int removeIP6Node(uint128t ip, IP6Node **node)
583 {
584 IP6Node *o = *node;
585
586 if (o != NULL)
587 {
588 int change;
589
590 if (lt_u128(ip, o->lo))
591 change = +removeIP6Node(ip, &o->L);
592
593 else if (gt_u128(ip, o->lo))
594 change = -removeIP6Node(ip, &o->R);
595
596 else // (le_u128(o->lo, ip) && le_u128(ip, o->lo))
597 {
598 int b = o->B;
599 IP6Node *p = o->L;
600 IP6Node *q = o->R;
601
602 if (!p || !q)
603 {
604 deallocate(VPR(*node), false);
605 *node = (p > q) ? p : q;
606 return 1; // remove the weight of 1 leaf from the balance
607 }
608
609 else
610 {
611 if (b == -1)
612 {
613 if (!p->R)
614 {
615 change = +1;
616 o = p;
617 o->R = q;
618 }
619 else
620 {
621 change = +pickPrevIP6Node(&p, &o);
622 o->L = p;
623 o->R = q;
624 }
625 }
626
627 else
628 {
629 if (!q->L)
630 {
631 change = -1;
632 o = q;
633 o->L = p;
634 }
635 else
636 {
637 change = -pickNextIP6Node(&q, &o);
638 o->L = p;
639 o->R = q;
640 }
641 }
642
643 o->B = b;
644 deallocate(VPR(*node), false);
645 *node = o;
646 }
647 }
648
649 if (change)
650 if (abs(o->B += change) > 1)
651 return balanceIP6Node(node);
652 else
653 return o->B == 0;
654 else
655 return 0;
656 }
657
658 else // (o == NULL)
659 return 0; // not found -> recursively do nothing
660 }
661
662
serializeIP6Tree(FILE * out,IP6Node * node)663 void serializeIP6Tree(FILE *out, IP6Node *node)
664 {
665 if (node)
666 {
667 if (node->L)
668 serializeIP6Tree(out, node->L);
669
670 IP6Set set = {node->lo, node->hi, node->cc};
671 fwrite(set, sizeof(IP6Set), 1, out);
672
673 if (node->R)
674 serializeIP6Tree(out, node->R);
675 }
676 }
677
678
releaseIP6Tree(IP6Node * node)679 void releaseIP6Tree(IP6Node *node)
680 {
681 if (node)
682 {
683 if (node->L)
684 releaseIP6Tree(node->L);
685
686 if (node->R)
687 releaseIP6Tree(node->R);
688
689 deallocate(VPR(node), false);
690 }
691 }
692
693
694 #pragma mark ••• AVL Tree of Country Codes •••
695
balanceCCNode(CCNode ** node)696 static int balanceCCNode(CCNode **node)
697 {
698 int change = 0;
699 CCNode *o = *node;
700 CCNode *p, *q;
701
702 if (o->B == -2)
703 {
704 if (p = o->L) // make the static analyzer happy
705 if (p->B == +1)
706 {
707 change = 1; // double left-right rotation
708 q = p->R; // left rotation
709 p->R = q->L;
710 q->L = p;
711 o->L = q->R; // right rotation
712 q->R = o;
713 o->B = +(q->B < 0);
714 p->B = -(q->B > 0);
715 q->B = 0;
716 *node = q;
717 }
718
719 else
720 {
721 change = p->B; // single right rotation
722 o->L = p->R;
723 p->R = o;
724 o->B = -(++p->B);
725 *node = p;
726 }
727 }
728
729 else if (o->B == +2)
730 {
731 if (q = o->R) // make the static analyzer happy
732 if (q->B == -1)
733 {
734 change = 1; // double right-left rotation
735 p = q->L; // right rotation
736 q->L = p->R;
737 p->R = q;
738 o->R = p->L; // left rotation
739 p->L = o;
740 o->B = -(p->B > 0);
741 q->B = +(p->B < 0);
742 p->B = 0;
743 *node = p;
744 }
745
746 else
747 {
748 change = q->B; // single left rotation
749 o->R = q->L;
750 q->L = o;
751 o->B = -(--q->B);
752 *node = q;
753 }
754 }
755
756 return change != 0;
757 }
758
759
pickPrevCCNode(CCNode ** node,CCNode ** exch)760 static int pickPrevCCNode(CCNode **node, CCNode **exch)
761 { // *exch on entry = parent node
762 CCNode *o = *node; // *exch on exit = picked previous value node
763
764 if (o->R)
765 {
766 *exch = o;
767 int change = -pickPrevCCNode(&o->R, exch);
768 if (change)
769 if (abs(o->B += change) > 1)
770 return balanceCCNode(node);
771 else
772 return o->B == 0;
773 else
774 return 0;
775 }
776
777 else if (o->L)
778 {
779 CCNode *p = o->L;
780 o->L = NULL;
781 (*exch)->R = p;
782 *exch = o;
783 return p->B == 0;
784 }
785
786 else
787 {
788 (*exch)->R = NULL;
789 *exch = o;
790 return 1;
791 }
792 }
793
794
pickNextCCNode(CCNode ** node,CCNode ** exch)795 static int pickNextCCNode(CCNode **node, CCNode **exch)
796 { // *exch on entry = parent node
797 CCNode *o = *node; // *exch on exit = picked next value node
798
799 if (o->L)
800 {
801 *exch = o;
802 int change = +pickNextCCNode(&o->L, exch);
803 if (change)
804 if (abs(o->B += change) > 1)
805 return balanceCCNode(node);
806 else
807 return o->B == 0;
808 else
809 return 0;
810 }
811
812 else if (o->R)
813 {
814 CCNode *q = o->R;
815 o->R = NULL;
816 (*exch)->L = q;
817 *exch = o;
818 return q->B == 0;
819 }
820
821 else
822 {
823 (*exch)->L = NULL;
824 *exch = o;
825 return 1;
826 }
827 }
828
829
findCCNode(uint32_t cc,CCNode * node)830 CCNode *findCCNode(uint32_t cc, CCNode *node)
831 {
832 if (node)
833 {
834 if (cc < node->cc)
835 return findCCNode(cc, node->L);
836
837 else if (cc > node->cc)
838 return findCCNode(cc, node->R);
839
840 else // (cc == node->cc)
841 return node;
842 }
843 else
844 return NULL;
845 }
846
847
addCCNode(uint32_t cc,uint32_t ui,CCNode ** node)848 int addCCNode(uint32_t cc, uint32_t ui, CCNode **node)
849 {
850 CCNode *o = *node;
851
852 if (o != NULL)
853 {
854 int change;
855
856 if (cc < o->cc)
857 change = -addCCNode(cc, ui, &o->L);
858
859 else if (cc > o->cc)
860 change = +addCCNode(cc, ui, &o->R);
861
862 else // (cc == o->cc) // already in the list, do nothing
863 return 0;
864
865 if (change)
866 if (abs(o->B += change) > 1)
867 return 1 - balanceCCNode(node);
868 else
869 return o->B != 0;
870 else
871 return 0;
872 }
873
874 else // (o == NULL) // if the CCNode is not in the tree
875 { // then add it into a new leaf
876 if (o = allocate(sizeof(CCNode), true))
877 {
878 o->cc = cc;
879 o->ui = ui;
880 *node = o; // report back the new node
881 return 1; // add the weight of 1 leaf onto the balance
882 }
883
884 return 0; // Out of Memory situation, nothing changed
885 }
886 }
887
888
removeCCNode(uint32_t cc,CCNode ** node)889 int removeCCNode(uint32_t cc, CCNode **node)
890 {
891 CCNode *o = *node;
892
893 if (o != NULL)
894 {
895 int change;
896
897 if (cc < o->cc)
898 change = +removeCCNode(cc, &o->L);
899
900 else if (cc > o->cc)
901 change = -removeCCNode(cc, &o->R);
902
903 else // (cc == o->cc)
904 {
905 int b = o->B;
906 CCNode *p = o->L;
907 CCNode *q = o->R;
908
909 if (!p || !q)
910 {
911 deallocate(VPR(*node), false);
912 *node = (p > q) ? p : q;
913 return 1; // remove the weight of 1 leaf from the balance
914 }
915
916 else
917 {
918 if (b == -1)
919 {
920 if (!p->R)
921 {
922 change = +1;
923 o = p;
924 o->R = q;
925 }
926 else
927 {
928 change = +pickPrevCCNode(&p, &o);
929 o->L = p;
930 o->R = q;
931 }
932 }
933
934 else
935 {
936 if (!q->L)
937 {
938 change = -1;
939 o = q;
940 o->L = p;
941 }
942 else
943 {
944 change = -pickNextCCNode(&q, &o);
945 o->L = p;
946 o->R = q;
947 }
948 }
949
950 o->B = b;
951 deallocate(VPR(*node), false);
952 *node = o;
953 }
954 }
955
956 if (change)
957 if (abs(o->B += change) > 1)
958 return balanceCCNode(node);
959 else
960 return o->B == 0;
961 else
962 return 0;
963 }
964
965 else // (o == NULL)
966 return 0; // not found -> recursively do nothing
967 }
968
969
releaseCCTree(CCNode * node)970 void releaseCCTree(CCNode *node)
971 {
972 if (node)
973 {
974 if (node->L)
975 releaseCCTree(node->L);
976
977 if (node->R)
978 releaseCCTree(node->R);
979
980 deallocate(VPR(node), false);
981 }
982 }
983
984
985 #pragma mark ••• Pseudo Hash Table of Country Codes •••
986
987
988 // Table creation and release
createCCTable(void)989 CCNode **createCCTable(void)
990 {
991 return allocate(ccTableSize*sizeof(CCNode *), true);
992 }
993
releaseCCTable(CCNode * table[])994 void releaseCCTable(CCNode *table[])
995 {
996 if (table)
997 {
998 for (uint32_t i = 0; i < ccTableSize; i++)
999 releaseCCTree(table[i]);
1000 deallocate(VPR(table), false);
1001 }
1002 }
1003
1004
1005 // finding/storing/removing country codes
1006
cci(uint32_t cc)1007 static inline uint32_t cci(uint32_t cc)
1008 {
1009 return (cc = cce((uint16_t)cc) < ccTableSize) ? cc : 0; // the resulting index MUST FIT into the hash table
1010 }
1011
findCC(CCNode * table[],uint32_t cc)1012 CCNode *findCC(CCNode *table[], uint32_t cc)
1013 {
1014 return findCCNode(cc, table[cci(cc)]);
1015 }
1016
storeCC(CCNode * table[],char * ccui)1017 void storeCC(CCNode *table[], char *ccui)
1018 {
1019 int len = strvlen(ccui = trim(ccui));
1020 if (len >= 2)
1021 {
1022 uint16_t cc;
1023 int64_t ui = 0;
1024 cc = *(uint16_t *)uppercase(ccui, 2);
1025 if (len > 2)
1026 {
1027 for (ccui += 2; *ccui && *ccui != '='; ccui++);
1028 if (*ccui)
1029 ui = strtol(ccui+1, NULL, 10);
1030 }
1031
1032 addCCNode(cc, (0 < ui && ui < 4294967295) ? (uint32_t)ui : 0, &table[cci(cc)]);
1033 }
1034 }
1035
removeCC(CCNode * table[],uint32_t cc)1036 void removeCC(CCNode *table[], uint32_t cc)
1037 {
1038 CCNode *node;
1039 uint32_t idx = cci(cc);
1040 if (node = table[idx])
1041 if (!node->L && !node->R)
1042 deallocate(VPR(table[idx]), false);
1043 else
1044 removeCCNode(cc, &table[idx]);
1045 }
1046