1 /*
2 Copyright (C) 2011-2021, Dirk Krause
3 SPDX-License-Identifier: BSD-3-Clause
4 */
5
6 /*
7 WARNING: This file was generated by the dkct program (see
8 http://dktools.sourceforge.net/ for details).
9 Changes you make here will be lost if dkct is run again!
10 You should modify the original source and run dkct on it.
11 Original source: dk4sto.ctr
12 */
13
14 /** @file dk4sto.c The dk4sto module.
15 */
16
17
18 #include "dk4conf.h"
19
20 #if DK4_HAVE_ASSERT_H
21 #ifndef ASSERT_H_INCLUDED
22 #include <assert.h>
23 #define ASSERT_H_INCLUDED 1
24 #endif
25 #endif
26
27 #include <libdk4c/dk4sto.h>
28 #include <libdk4base/dk4mem.h>
29
30 #if 0
31 #ifndef STDLIB_H_INCLUDED
32 #include <stdlib.h>
33 #define STDLIB_H_INCLUDED 1
34 #endif
35 #endif
36
37 #if DK4_HAVE_ASSERT_H
38 #ifndef ASSERT_H_INCLUDED
39 #include <assert.h>
40 #define ASSERT_H_INCLUDED 1
41 #endif
42 #endif
43
44
45
46
47
48
49 /** Comparison criteria for comparing nodes.
50 */
51 enum {
52 DK4STO_COMPARE_NONE = 0, /**< Do not compare the objects (unsorted). */
53 DK4STO_COMPARE_FCT , /**< Use comparison function. */
54 DK4STO_COMPARE_CHAR , /**< Evaluate objects to char values. */
55 DK4STO_COMPARE_UCHAR , /**< Evaluate to unsigned char values. */
56 DK4STO_COMPARE_SHORT , /**< Evaluate to short values. */
57 DK4STO_COMPARE_USHORT , /**< Evaluate to unsigned short values. */
58 DK4STO_COMPARE_INT , /**< Evaluate to int values. */
59 DK4STO_COMPARE_UINT , /**< Evaluate to unsigned int values. */
60 DK4STO_COMPARE_LONG , /**< Evaluate to long values. */
61 DK4STO_COMPARE_ULONG , /**< Evaluate to unsigned long values. */
62 DK4STO_COMPARE_FLOAT , /**< Evaluate to float values. */
63 DK4STO_COMPARE_DOUBLE /**< Evaluate to double values. */
64 };
65
66
67
68 /*
69 GENERAL STATIC FUNCTIONS
70 */
71
72 /** Initialize storage node for object.
73 @param n Storage node.
74 @param o Object.
75 @param s Storage.
76 @param crit Comparison/evaluation criteria used by storage.
77 */
78 static void
dk4sto_node_init_for_object(dk4_sto_node_t * n,void * o,dk4_sto_t * s,int crit)79 dk4sto_node_init_for_object(
80 dk4_sto_node_t *n,
81 void *o,
82 dk4_sto_t *s,
83 int crit
84 )
85 {
86
87 n->p = n->l = n->r = NULL;
88 n->b = n->w = 0;
89 n->o = o;
90 switch(s->h) {
91 case DK4STO_COMPARE_CHAR: (n->v).c = (*((s->e).c))(o,crit); break;
92 case DK4STO_COMPARE_UCHAR: (n->v).uc = (*((s->e).uc))(o,crit); break;
93 case DK4STO_COMPARE_SHORT: (n->v).s = (*((s->e).s))(o,crit); break;
94 case DK4STO_COMPARE_USHORT: (n->v).us = (*((s->e).us))(o,crit); break;
95 case DK4STO_COMPARE_INT: (n->v).i = (*((s->e).i))(o,crit); break;
96 case DK4STO_COMPARE_UINT: (n->v).ui = (*((s->e).ui))(o,crit); break;
97 case DK4STO_COMPARE_LONG: (n->v).l = (*((s->e).l))(o,crit); break;
98 case DK4STO_COMPARE_ULONG: (n->v).ul = (*((s->e).ul))(o,crit); break;
99 case DK4STO_COMPARE_FLOAT: (n->v).f = (*((s->e).f))(o,crit); break;
100 case DK4STO_COMPARE_DOUBLE: (n->v).d = (*((s->e).d))(o,crit); break;
101 }
102 }
103
104
105
106 /** Copy data from one storage node to another.
107 @param d Destination node.
108 @param s Source node.
109 @param st Storage.
110 */
111 static void
dk4sto_node_data_copy(dk4_sto_node_t * d,dk4_sto_node_t const * s,dk4_sto_t * st)112 dk4sto_node_data_copy(
113 dk4_sto_node_t *d,
114 dk4_sto_node_t const *s,
115 dk4_sto_t *st
116 )
117 {
118
119 d->o = s->o;
120 switch(st->h) {
121 case DK4STO_COMPARE_CHAR: (d->v).c = (s->v).c ; break;
122 case DK4STO_COMPARE_UCHAR: (d->v).uc = (s->v).uc ; break;
123 case DK4STO_COMPARE_SHORT: (d->v).s = (s->v).s ; break;
124 case DK4STO_COMPARE_USHORT: (d->v).us = (s->v).us ; break;
125 case DK4STO_COMPARE_INT: (d->v).i = (s->v).i ; break;
126 case DK4STO_COMPARE_UINT: (d->v).ui = (s->v).ui ; break;
127 case DK4STO_COMPARE_LONG: (d->v).l = (s->v).l ; break;
128 case DK4STO_COMPARE_ULONG: (d->v).ul = (s->v).ul ; break;
129 case DK4STO_COMPARE_FLOAT: (d->v).f = (s->v).f ; break;
130 case DK4STO_COMPARE_DOUBLE: (d->v).d = (s->v).d ; break;
131 }
132
133 }
134
135
136
137 /** Compare two storage nodes.
138 @param l Left node.
139 @param r Right node.
140 @param s Storage.
141 @param c Comparison criteria.
142 @return Comparison result.
143 */
144 static
145 int
dk4sto_node_compare(dk4_sto_node_t const * l,dk4_sto_node_t const * r,dk4_sto_t const * s,int c)146 dk4sto_node_compare(
147 dk4_sto_node_t const *l,
148 dk4_sto_node_t const *r,
149 dk4_sto_t const *s,
150 int c
151 )
152 {
153 int back = 0;
154
155 /* Static code analysis: Result of operation is garbage or undefined.
156 Clang static code analysis complains the right operand in comparisons
157 (r->v).xxx could be garbage.
158 I think this is not correct.
159 It assumes the default branch is taken in dk4sto_node_init_for_object()
160 as s->h does not match any of the case values.
161 The same case values are are used here, and there is no change
162 of s->h meanwhile.
163 */
164 switch(s->h) {
165 case DK4STO_COMPARE_FCT: {
166 back = (*((s->e).comp))((void *)(l->o),(void *)(r->o),c);
167 if(back < 0) back = -1;
168 if(back > 0) back = 1;
169 } break;
170 case DK4STO_COMPARE_CHAR: {
171 if(((l->v).c) > ((r->v).c)) { back = 1; }
172 else { if(((l->v).c) < ((r->v).c)) { back = -1; } }
173 } break;
174 case DK4STO_COMPARE_UCHAR: {
175 if(((l->v).uc) > ((r->v).uc)) { back = 1; }
176 else { if(((l->v).uc) < ((r->v).uc)) { back = -1; } }
177 } break;
178 case DK4STO_COMPARE_SHORT: {
179 if(((l->v).s) > ((r->v).s)) { back = 1; }
180 else { if(((l->v).s) < ((r->v).s)) { back = -1; } }
181 } break;
182 case DK4STO_COMPARE_USHORT: {
183 if(((l->v).us) > ((r->v).us)) { back = 1; }
184 else { if(((l->v).us) < ((r->v).us)) { back = -1; } }
185 } break;
186 case DK4STO_COMPARE_INT: {
187 if(((l->v).i) > ((r->v).i)) { back = 1; }
188 else { if(((l->v).i) < ((r->v).i)) { back = -1; } }
189 } break;
190 case DK4STO_COMPARE_UINT: {
191 if(((l->v).ui) > ((r->v).ui)) { back = 1; }
192 else { if(((l->v).ui) < ((r->v).ui)) { back = -1; } }
193 } break;
194 case DK4STO_COMPARE_LONG: {
195 if(((l->v).l) > ((r->v).l)) { back = 1; }
196 else { if(((l->v).l) < ((r->v).l)) { back = -1; } }
197 } break;
198 case DK4STO_COMPARE_ULONG: {
199 if(((l->v).ul) > ((r->v).ul)) { back = 1; }
200 else { if(((l->v).ul) < ((r->v).ul)) { back = -1; } }
201 } break;
202 case DK4STO_COMPARE_FLOAT: {
203 if(((l->v).f) > ((r->v).f)) { back = 1; }
204 else { if(((l->v).f) < ((r->v).f)) { back = -1; } }
205 } break;
206 case DK4STO_COMPARE_DOUBLE: {
207 if(((l->v).d) > ((r->v).d)) { back = 1; }
208 else { if(((l->v).d) < ((r->v).d)) { back = -1; } }
209 } break;
210 }
211 return back;
212 }
213
214
215
216 /*
217 UNSORTED DATA HANDLING
218 */
219
220 /** Remove node from an unsorted storage.
221 @param ro Root node.
222 @param n Node to remove.
223 @return New root node.
224 */
225 static dk4_sto_node_t *
dk4sto_unsorted_remove(dk4_sto_node_t * ro,dk4_sto_node_t * n)226 dk4sto_unsorted_remove(dk4_sto_node_t *ro, dk4_sto_node_t *n)
227 {
228 dk4_sto_node_t *back = NULL;
229 dk4_sto_node_t *l = NULL; /* Left element. */
230 dk4_sto_node_t *r = NULL; /* Right element. */
231
232 back = ro;
233 l = n->l; r = n->r;
234 if(r) {
235 r->l = l;
236 }
237 if(l) {
238 l->r = r;
239 } else {
240 back = r;
241 }
242 return back;
243 }
244
245
246
247 /** Add node to an unsorted storage.
248 @param r Old root node.
249 @param n Node to add.
250 @return New root node or NULL.
251 */
252 static dk4_sto_node_t *
dk4sto_unsorted_add(dk4_sto_node_t * r,dk4_sto_node_t * n)253 dk4sto_unsorted_add(dk4_sto_node_t *r, dk4_sto_node_t *n)
254 {
255 dk4_sto_node_t *back;
256
257 back = n;
258 n->r = r;
259 if(r) {
260 r->l = n;
261 }
262 return back;
263 }
264
265
266
267 /** Release all nodes in an unsorted storage.
268 @param r Root node.
269 */
270 static void
dk4sto_unsorted_release_all_nodes(dk4_sto_node_t * r)271 dk4sto_unsorted_release_all_nodes(dk4_sto_node_t *r)
272 {
273 dk4_sto_node_t *c; /* Current element. */
274 dk4_sto_node_t *n; /* Next element. */
275
276 c = r;
277 while(c) {
278 n = c->r;
279 c->p = c->l = c->r = NULL;
280 c->o = NULL;
281 c->b = c->w = 0;
282 dk4mem_free(c) ;
283 c = n;
284 }
285
286 }
287
288
289
290 /** Find next node in an unsorted storage.
291 @param n Current node.
292 @param r Root node.
293 @return Pointer to next node or NULL.
294 */
295 static
296 dk4_sto_node_t *
dk4sto_unsorted_find_next_node(dk4_sto_node_t * n,dk4_sto_node_t * r)297 dk4sto_unsorted_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
298 {
299 dk4_sto_node_t *back = NULL;
300
301 if(n) {
302 back = n->r;
303 } else {
304 back = r;
305 }
306 return back;
307 }
308
309
310
311 /** Find last node in an unsorted storage.
312 @param n Root node.
313 @return Last node or NULL.
314 */
315 static dk4_sto_node_t *
dk4sto_unsorted_find_last_node(dk4_sto_node_t * n)316 dk4sto_unsorted_find_last_node(dk4_sto_node_t *n)
317 {
318 dk4_sto_node_t *back = NULL;
319
320 if(n) back = n->l;
321
322 return back;
323 }
324
325
326
327 /** Find node for an object in an unsorted storage.
328 @param r Root node.
329 @param o Object.
330 @return Node for object or NULL.
331 */
332 static dk4_sto_node_t *
dk4sto_unsorted_find_exact(dk4_sto_node_t * r,void const * o)333 dk4sto_unsorted_find_exact(dk4_sto_node_t *r, void const *o)
334 {
335 dk4_sto_node_t *back = NULL;
336 dk4_sto_node_t *c; /* Current node. */
337
338 c = r;
339 while(c && (!back)) {
340 if((c->o) == o) {
341 back = c;
342 }
343 c = c->r;
344 }
345 return back;
346 }
347
348
349
350 /*
351 SORTED DATA HANDLING
352 */
353
354
355
356 /** Direction to walk to.
357 */
358 enum {
359 DK4STO_WALK_LEFT = 1, /**< Go to left. */
360 DK4STO_WALK_RIGHT = 2 /**< Go to right. */
361 };
362
363
364
365 /** Perform left rotation at node.
366 @param p Subpath to modify.
367 @return New subpath root node or NULL.
368 */
369 static dk4_sto_node_t *
dk4sto_left_rotation(dk4_sto_node_t * p)370 dk4sto_left_rotation(dk4_sto_node_t *p)
371 {
372 dk4_sto_node_t *p1;
373
374 p1 = p->r;
375 p->r = p1->l;
376 if(p->r) (p->r)->p = p;
377 p1->l = p;
378 if(p) p->p = p1;
379
380 return p1;
381 }
382
383
384
385 /** Perform right rotation at node.
386 @param p Subpath to modify.
387 @return New subpath root node or NULL.
388 */
389 static dk4_sto_node_t *
dk4sto_right_rotation(dk4_sto_node_t * p)390 dk4sto_right_rotation(dk4_sto_node_t *p)
391 {
392 dk4_sto_node_t *p1;
393
394 p1 = p->l;
395 p->l = p1->r;
396 if(p->l) (p->l)->p = p;
397 p1->r = p;
398 if(p) p->p = p1;
399
400 return p1;
401 }
402
403
404
405 /** Increment balance field of a storage node.
406 @param p Node to modify.
407 */
408 static void
dk4sto_inc_balance(dk4_sto_node_t * p)409 dk4sto_inc_balance(dk4_sto_node_t *p)
410 {
411 short x; /* New balance value. */
412
413 x = p->b;
414 x++;
415 if(x > 3) x = 0;
416 p->b = x;
417 }
418
419
420
421 /** Decrement balance field of a storage node.
422 @param p Storage node.
423 */
424 static void
dk4sto_dec_balance(dk4_sto_node_t * p)425 dk4sto_dec_balance(dk4_sto_node_t *p)
426 {
427 short x; /* New balance value. */
428
429 x = p->b;
430 x--;
431 if(x < 0) x = 3;
432 p->b = x;
433 }
434
435
436
437
438 /** Set mark for "left node deleted".
439 @param p Node.
440 @param h Pointer to balance variable.
441 @return New root node for path behind \a p.
442 */
443 static dk4_sto_node_t *
dk4sto_left_deleted(dk4_sto_node_t * p,short * h)444 dk4sto_left_deleted(dk4_sto_node_t *p, short *h)
445 {
446
447 switch(p->b) {
448 case 0: *h = (short)(0 - *h);
449 /* fall-through */
450 case 3:
451
452 dk4sto_inc_balance(p);
453
454 break;
455 case 1: {
456 switch((p->r)->b) {
457 case 0:
458 (p->r)->b = 3;
459 *h = (short)(0 - *h);
460 p = dk4sto_left_rotation(p);
461 break;
462 case 1:
463 (p->r)->b = 0;
464 p->b = 0;
465 p = dk4sto_left_rotation(p);
466 break;
467 case 3:
468 p->b = (((((p->r)->l)->b) == 1) ? 3 : 0);
469 (p->r)->b = (((((p->r)->l)->b) == 3) ? 1 : 0);
470 p->r = dk4sto_right_rotation(p->r);
471 if(p->r) (p->r)->p = p;
472 p = dk4sto_left_rotation(p);
473 p->b = 0;
474 }
475 }
476 }
477
478 return p;
479 }
480
481
482
483 /** Set mark for "right node deleted".
484 @param p Node.
485 @param h Pointer to balance variable.
486 @return New root node for path behind \a p.
487 */
488 static dk4_sto_node_t *
dk4sto_right_deleted(dk4_sto_node_t * p,short * h)489 dk4sto_right_deleted(dk4_sto_node_t *p, short *h)
490 {
491
492 switch(p->b) {
493 case 0: *h = (short)(0 - *h);
494 /* fall-through */
495 case 1: dk4sto_dec_balance(p);
496 break;
497 case 3: {
498 switch((p->l)->b) {
499 case 0:
500 (p->l)->b = 1;
501 *h = (short)(0 - *h);
502 p = dk4sto_right_rotation(p);
503 break;
504 case 3:
505 (p->l)->b = 0;
506 p->b = 0;
507 p = dk4sto_right_rotation(p);
508 break;
509 case 1:
510 p->b = (((((p->l)->r)->b) == 3) ? 1 : 0);
511 (p->l)->b = (((((p->l)->r)->b) == 1) ? 3 : 0);
512 p->l = dk4sto_left_rotation(p->l);
513 if(p->l) (p->l)->p = p;
514 p = dk4sto_right_rotation(p);
515 p->b = 0;
516 }
517 }
518 }
519
520 return p;
521 }
522
523
524
525 /** Add node to tree storage.
526 @param root Root node.
527 @param newnode Node to add.
528 @param st Storage.
529 @return New root node or NULL.
530 */
531 static
532 dk4_sto_node_t *
dk4sto_avlt_add(dk4_sto_node_t * root,dk4_sto_node_t * newnode,dk4_sto_t * st)533 dk4sto_avlt_add(dk4_sto_node_t *root, dk4_sto_node_t *newnode, dk4_sto_t *st)
534 {
535 dk4_sto_node_t *back = NULL;
536 dk4_sto_node_t *p = NULL; /* Current node. */
537 dk4_sto_node_t *q = NULL; /* Father of p. */
538 dk4_sto_node_t *r = NULL; /* Critical node. */
539 dk4_sto_node_t *s = NULL; /* Father of r. */
540
541 back = root;
542 p = r = root; q = s = NULL;
543 /*
544 Search place for insertion, write direction into
545 the "w" field in each node.
546 The final new node has an empty "w" field.
547 */
548 while(p) {
549 /*
550 q is either NULL (in first pass) or the parent
551 of the current node in p.
552 */
553 if(p->b) {
554 s = q; r = p;
555 }
556 q = p;
557 if(dk4sto_node_compare(p,newnode,st,st->c) > 0) {
558 p->w = DK4STO_WALK_LEFT;
559 p = p->l;
560 } else {
561 p->w = DK4STO_WALK_RIGHT;
562 p = p->r;
563 }
564 }
565 /*
566 q is either NULL or the last node visited.
567 r is the last unbalanced node (critical node).
568 s is either NULL or the parent of the last unbalanced node.
569 */
570 p = newnode;
571 if(NULL == back) {
572 /*
573 When inserting into an empty tree we are done here.
574 */
575 back = p;
576 } else {
577 /*
578 The tree is not empty.
579 The new node p is concatenated to the parent q.
580 */
581 if(dk4sto_node_compare(q,newnode,st,st->c) > 0) {
582 q->l = p;
583 q->w = DK4STO_WALK_LEFT;
584 } else {
585 q->r = p;
586 q->w = DK4STO_WALK_RIGHT;
587 }
588 p->p = q;
589 /*
590 Now we must balance the tree again if necessary.
591 */
592 if(r) {
593 /*
594 There is a critical node.
595 */
596 p = r;
597 /*
598 Modify balance fields from critial node
599 until we find our new node.
600 */
601 while(p->w) {
602 if(p->w == DK4STO_WALK_LEFT) {
603 dk4sto_dec_balance(p);
604 p = p->l;
605 } else {
606 dk4sto_inc_balance(p);
607 p = p->r;
608 }
609 }
610 p = r;
611 /*
612 Now look whether we are dis-balanced,
613 correct if necessary.
614 */
615 if((p->b) == 2) {
616 /* We must balance */
617 if(p->w == DK4STO_WALK_LEFT) {
618 if((p->l)->b == 3) {
619 p->b = 0;
620 p = dk4sto_right_rotation(p);
621 } else {
622 /* Static code analyis: Potentially dereferencing NULL pointer.
623 I do not think so. We have to balance at p because the
624 left subtree is too deep. We did not add the new node to
625 the left childs left subtree, so we must have added it to the
626 left childs right subtree. So the left childs right child
627 can not be NULL.
628 */
629 #if DK4_USE_ASSERT
630 assert (NULL != (p->l)->r);
631 #endif
632 p->b = (((((p->l)->r)->b) == 3) ? 1 : 0);
633 (p->l)->b = (((((p->l)->r)->b) == 1) ? 3 : 0);
634 p->l = dk4sto_left_rotation(p->l);
635 if(p->l) (p->l)->p = p;
636 p = dk4sto_right_rotation(p);
637 }
638 } else {
639 if((p->r)->b == 1) {
640 p->b = 0;
641 p = dk4sto_left_rotation(p);
642 } else {
643 /* Static code analyis: Potentially dereferencing NULL pointer.
644 I do not think so. We have to balance at p because the
645 right subtree is too deep. We did not add the new node to
646 the right childs right subtree, so we must have added it to the
647 right childs left subtree. So the right childs left child
648 can not be NULL.
649 */
650 #if DK4_USE_ASSERT
651 assert(NULL != (p->r)->l);
652 #endif
653 p->b = (((((p->r)->l)->b) == 1) ? 3 : 0);
654 (p->r)->b = (((((p->r)->l)->b) == 3) ? 1 : 0);
655 p->r = dk4sto_right_rotation(p->r);
656 if(p->r) (p->r)->p = p;
657 p = dk4sto_left_rotation(p);
658 }
659 }
660 p->b = 0;
661 /*
662 Balance at the critical nodes father (if
663 there is one) or create new root.
664 */
665 if(s) {
666 if(s->w == DK4STO_WALK_LEFT) {
667 s->l = p;
668 } else {
669 s->r = p;
670 }
671 if(p) p->p = s;
672 } else {
673 back = p;
674 }
675 }
676 }
677 }
678 if(back) {
679 back->p = NULL;
680 }
681
682 return back;
683 }
684
685
686
687 /** Find last node in a tree storage.
688 @param n Node to start search from.
689 @return Last node or NULL.
690 */
691 static dk4_sto_node_t *
dk4sto_tree_find_last_node(dk4_sto_node_t * n)692 dk4sto_tree_find_last_node(dk4_sto_node_t *n)
693 {
694 dk4_sto_node_t *back = NULL;
695 dk4_sto_node_t *c; /* Current node. */
696 dk4_sto_node_t *p; /* Father of c. */
697
698 if(n->l) {
699 back = n->l;
700 while(back->r) { back = back->r; }
701 } else {
702 c = n; p = c->p;
703 while(p && (!back)) {
704 if((p->r) == c) {
705 back = p;
706 } else {
707 c = p; p = c->p;
708 }
709 }
710 }
711 return back;
712 }
713
714
715
716 /** Remove storage node from tree storage.
717 @param root Root object.
718 @param node Node to remove.
719 @param delpath Deletion path (used for tree balancing).
720 @param st Storage.
721 @param success_indicator Pointer to success variable.
722 @param toremove Node to remove.
723 @return New root object.
724 */
725 static dk4_sto_node_t *
dk4sto_avlt_delete(dk4_sto_node_t * root,dk4_sto_node_t * node,dk4_sto_node_t ** delpath,dk4_sto_t * st,int * success_indicator,dk4_sto_node_t ** toremove)726 dk4sto_avlt_delete(
727 dk4_sto_node_t *root, dk4_sto_node_t *node, dk4_sto_node_t **delpath,
728 dk4_sto_t *st, int *success_indicator, dk4_sto_node_t **toremove
729 )
730 {
731 dk4_sto_node_t *back = NULL;
732 dk4_sto_node_t *p = NULL; /* Current node. */
733 dk4_sto_node_t *q = NULL; /* Father of p. */
734 dk4_sto_node_t *r = NULL; /* Critical node. */
735 dk4_sto_node_t *todel = NULL; /* Node to delete. */
736 dk4_sto_node_t *itn = NULL; /* Iterator node. */
737 dk4_sto_it_t *iterat = NULL; /* Iterator */
738 short x1 = 0; /* Balance value. */
739 short delroot = 0; /* Flag: Delete tree node. */
740 int can_continue = 1; /* Flag: Can continue. */
741 back = root;
742 todel = node;
743
744 /*
745 Make sure the node to delete has max.
746 1 subtree.
747 */
748 if((todel->l) && (todel->r)) {
749
750 todel = todel->l;
751 while(todel->r) todel = todel->r;
752 dk4sto_node_data_copy(node,todel,st);
753 /*
754 2019-03-24 Change iterators again.
755 */
756 itn = dk4sto_tree_find_last_node(todel);
757 iterat = (dk4_sto_it_t *)(st->i);
758 while(NULL != iterat) {
759 if ((iterat->c) == todel) {
760 iterat->c = itn;
761 }
762 iterat = iterat->r;
763 }
764 }
765 if(!(todel->p)) {
766 delroot = 1;
767 }
768 /*
769 Mark the way in the "w" fields.
770 */
771 *toremove = todel;
772 todel->w = 0;
773 while(todel->p) {
774 if((todel->p)->l == todel) {
775
776 (todel->p)->w = DK4STO_WALK_LEFT;
777 } else {
778
779 (todel->p)->w = DK4STO_WALK_RIGHT;
780 }
781 todel = todel->p;
782 }
783 p = back;
784 q = r = NULL;
785 x1 = 0;
786 can_continue = 1;
787 while(can_continue) {
788
789 #if VERSION_BEFORE_20150821
790 if(p) {
791 #endif
792 if(p->w) {
793 if(p->b == 0) {
794 x1 = 0;
795 }
796 delpath[x1++] = p;
797 if(x1 >= st->l) {
798 /* x1 too large */
799 *success_indicator = 0;
800 goto error_mark;
801 }
802 if(p->w == DK4STO_WALK_LEFT) {
803 p = p->l;
804 } else {
805 p = p->r;
806 }
807 } else {
808 can_continue = 0;
809 }
810 #if VERSION_BEFORE_20150821
811 } else {
812 can_continue = 0;
813 }
814 #endif
815 }
816 #if VERSION_BEFORE_20150821
817 r = p;
818 #endif
819 /* 2015-08-21 Static code analysis complains p could be NULL.
820 I think it can not.
821 */
822 if(NULL != p->l) q = p->l;
823 else q = p->r;
824 if(x1 == 0) {
825 if(delroot) {
826 back = q;
827 }
828 }
829 while(x1 > 0) {
830 x1--;
831 p = delpath[x1];
832 if(p->w == DK4STO_WALK_LEFT) {
833
834 p->l = q; if(q) q->p = p;
835 q = dk4sto_left_deleted(p, &x1);
836
837 } else {
838
839 p->r = q; if(q) q->p = p;
840 q = dk4sto_right_deleted(p, &x1);
841
842 }
843 if(x1 == 0) {
844
845 if(delpath[x1] == back) {
846
847 back = q;
848 }
849 }
850 if(x1 < 0) {
851 p = delpath[0 - x1 - 1];
852 if(p->w == DK4STO_WALK_LEFT) {
853 p->l = q;
854 } else {
855 p->r = q;
856 }
857 if(q) q->p = p;
858 }
859 }
860 error_mark:
861 if(back) {
862 back->p = NULL;
863 }
864
865 return back;
866 }
867
868
869
870 /** Find storage node for an object evaluated like a given object.
871 @param root Root node.
872 @param testnode Node of the given object.
873 @param st Storage.
874 @param crit Comparison criteria.
875 @param cand Pointer for candidate.
876 @return Pointer to storage node or NULL.
877 */
878 static
879 dk4_sto_node_t *
dk4sto_tree_find_like(dk4_sto_node_t * root,dk4_sto_node_t * testnode,dk4_sto_t * st,int crit,dk4_sto_node_t ** cand)880 dk4sto_tree_find_like(
881 dk4_sto_node_t *root, dk4_sto_node_t *testnode, dk4_sto_t *st, int crit,
882 dk4_sto_node_t **cand
883 )
884 {
885 dk4_sto_node_t *back = NULL;
886 dk4_sto_node_t *c = NULL; /* Current node. */
887 int testval = 0; /* Comparison result. */
888
889 c = root;
890 while(c) {
891 testval = dk4sto_node_compare(c,testnode,st,crit);
892 switch(testval) {
893 case -1: {
894 if(cand) *cand = c;
895 c = c->r;
896 } break;
897 case 0: {
898 back = c; c = c->l;
899 } break;
900 default: {
901 c = c->l;
902 } break;
903 }
904 }
905 return back;
906 }
907
908
909
910 /** Add node to a tree.
911 @param r Root node.
912 @param n New node to add.
913 @param s Storage.
914 @return Node pointer on success, NULL on error.
915 */
916 static dk4_sto_node_t *
dk4sto_tree_add(dk4_sto_node_t * r,dk4_sto_node_t * n,dk4_sto_t * s)917 dk4sto_tree_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s)
918 {
919 dk4_sto_node_t *back;
920 back = dk4sto_avlt_add(r,n,s);
921 return back;
922 }
923
924
925
926 /** Release all nodes in a tree storage.
927 @param r Root node.
928 */
929 static void
dk4sto_tree_release_all_nodes(dk4_sto_node_t * r)930 dk4sto_tree_release_all_nodes(dk4_sto_node_t *r)
931 {
932
933 if(r) {
934 dk4sto_tree_release_all_nodes(r->l);
935 dk4sto_tree_release_all_nodes(r->r);
936 r->l = r->r = r->p = NULL;
937 r->o = NULL;
938 r->b = 0; r->w = 0;
939 dk4mem_free(r) ;
940 }
941 }
942
943
944
945 /** Find next node in a tree storage.
946 @param n Current node.
947 @param r Root node.
948 @return Pointer to next node or NULL.
949 */
950 static dk4_sto_node_t *
dk4sto_tree_find_next_node(dk4_sto_node_t * n,dk4_sto_node_t * r)951 dk4sto_tree_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
952 {
953 dk4_sto_node_t *back = NULL;
954 dk4_sto_node_t *c = NULL; /* Current node. */
955 dk4_sto_node_t *p = NULL; /* Parent of c. */
956
957 /*
958 if(n) {
959 if(n->r) {
960 back = n->r;
961 while(back->l) { back = back->l; }
962 } else {
963 c = n; p = c->p;
964 while(p && (!back)) {
965 if((p->l) == c) {
966 back = p;
967 } else {
968 c = p; p = c->p;
969 }
970 }
971 }
972 } else {
973 back = r;
974 if(back) { while(back->l) { back = back->l; } }
975 }
976 */
977 if(n) {
978 if(n->r) {
979 back = n->r;
980 while(back->l) back = back->l;
981 } else {
982 c = n; p = c->p;
983 while(p && (!back)) {
984 if(p->l == c) {
985 back = p;
986 } else {
987 c = p; p = c->p;
988 }
989 }
990 }
991 } else {
992 back = r;
993 if(back) {
994 while(back->l) back = back->l;
995 }
996 }
997
998 return back;
999 }
1000
1001
1002
1003 /** Find node for object in tree storage (exact search).
1004 @param r Root node.
1005 @param o Object to find node for.
1006 @param s Storage.
1007 @return Pointer to node or NULL.
1008 */
1009 static dk4_sto_node_t *
dk4sto_tree_find_exact(dk4_sto_node_t * r,void const * o,dk4_sto_t * s)1010 dk4sto_tree_find_exact(dk4_sto_node_t *r, void const *o, dk4_sto_t *s)
1011 {
1012 dk4_sto_node_t *back = NULL;
1013 dk4_sto_node_t testnode; /* Test node for comparisons. */
1014 dk4_sto_node_t *c; /* Current node to test. */
1015 dk4_sto_node_t *candidate; /* Candidate for found node. */
1016 int testval = 0; /* Comparison result. */
1017
1018 dk4sto_node_init_for_object(&testnode, (void *)o, s, s->c);
1019 c = dk4sto_tree_find_like(r, &testnode, s, s->c, &candidate);
1020 while(c && (!back)) {
1021 testval = dk4sto_node_compare(c, &testnode, s, s->c);
1022 if(testval == 0) {
1023 if((c->o) == o) {
1024 back = c;
1025 } else {
1026 c = dk4sto_tree_find_next_node(c, r);
1027 }
1028 } else {
1029 c = NULL;
1030 }
1031 }
1032 return back;
1033 }
1034
1035
1036
1037 /** Remove storage node from tree storage.
1038 @param ro Root node.
1039 @param n Node to delete.
1040 @param st Storage.
1041 @param sci ???
1042 @param toremove Node to remove.
1043 @return New root node.
1044 */
1045 static dk4_sto_node_t *
dk4sto_tree_remove(dk4_sto_node_t * ro,dk4_sto_node_t * n,dk4_sto_t * st,int * sci,dk4_sto_node_t ** toremove)1046 dk4sto_tree_remove(
1047 dk4_sto_node_t *ro, dk4_sto_node_t *n, dk4_sto_t *st, int *sci,
1048 dk4_sto_node_t **toremove
1049 )
1050 {
1051 dk4_sto_node_t *back;
1052 back = dk4sto_avlt_delete(ro,n,st->d,st,sci,toremove);
1053 return back;
1054 }
1055
1056
1057
1058 /*
1059 USE DOUBLE LINKED LIST
1060 */
1061
1062 /** Find node for an object evaluated like a given object in a list storage.
1063 @param root Root node.
1064 @param testnode Node with object for comparison.
1065 @param st Storage.
1066 @param crit Comparison criteria.
1067 @param cand Test candidate.
1068 @return Pointer to storage node or NULL.
1069 */
1070 static dk4_sto_node_t *
dk4sto_list_find_like(dk4_sto_node_t * root,dk4_sto_node_t * testnode,dk4_sto_t * st,int crit,dk4_sto_node_t ** cand)1071 dk4sto_list_find_like(
1072 dk4_sto_node_t *root, dk4_sto_node_t *testnode, dk4_sto_t *st, int crit,
1073 dk4_sto_node_t **cand
1074 )
1075 {
1076 dk4_sto_node_t *back = NULL;
1077 dk4_sto_node_t *c = NULL; /* Current node. */
1078 int testval = 0; /* Comparison result. */
1079
1080 c = root;
1081 while(c && (!back)) {
1082 testval = dk4sto_node_compare(c,testnode,st,crit);
1083 switch(testval) {
1084 case -1: {
1085 if(cand) *cand = c;
1086 c = c->r;
1087 } break;
1088 case 0: {
1089 back = c; c = NULL;
1090 } break;
1091 default : {
1092 c = NULL;
1093 } break;
1094 }
1095 }
1096 return back;
1097 }
1098
1099
1100
1101 /** Find node for an object (exact search).
1102 @param r Root node.
1103 @param o Object.
1104 @return Pointer to the objects node or NULL.
1105 */
1106 static dk4_sto_node_t *
dk4sto_list_find_exact(dk4_sto_node_t * r,void const * o)1107 dk4sto_list_find_exact(dk4_sto_node_t *r, void const *o)
1108 {
1109 dk4_sto_node_t *back;
1110
1111 back = dk4sto_unsorted_find_exact(r,o);
1112
1113 return back;
1114 }
1115
1116
1117
1118 /** Add node to list storage.
1119 @param r Root node.
1120 @param n New node.
1121 @param s Storage.
1122 @return Pointer on success, NULL on error.
1123 */
1124 static dk4_sto_node_t *
dk4sto_list_add(dk4_sto_node_t * r,dk4_sto_node_t * n,dk4_sto_t * s)1125 dk4sto_list_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s)
1126 {
1127 dk4_sto_node_t *back;
1128 dk4_sto_node_t *larger = NULL; /* Last found larger entry. */
1129 dk4_sto_node_t *current = NULL; /* Current node. */
1130 dk4_sto_node_t *smaller = NULL; /* Last found smaller entry. */
1131 int ende;
1132
1133 back = r;
1134 if(r) {
1135 larger = smaller = NULL;
1136 current = r;
1137 ende = 0;
1138 while(!ende) {
1139 if(dk4sto_node_compare(current,n,s,s->c) >= 0) {
1140 larger = current; ende = 1;
1141 } else {
1142 smaller = current;
1143 }
1144 if(current->r) {
1145 current = current->r;
1146 } else {
1147 ende = 1;
1148 }
1149 }
1150 if(larger) {
1151 n->r = larger;
1152 larger->l = n;
1153 if(smaller) {
1154 smaller->r = n;
1155 n->l = smaller;
1156 } else {
1157 back = n;
1158 }
1159 } else {
1160 if(smaller) {
1161 smaller->r = n;
1162 n->l = smaller;
1163 }
1164 }
1165 } else {
1166 back = n;
1167 }
1168 return back;
1169 }
1170
1171
1172
1173 /** Release all nodes of a list storage.
1174 @param r Root node.
1175 */
1176 static void
dk4sto_list_release_all_nodes(dk4_sto_node_t * r)1177 dk4sto_list_release_all_nodes(dk4_sto_node_t *r)
1178 {
1179
1180 dk4sto_unsorted_release_all_nodes(r);
1181
1182 }
1183
1184
1185
1186 /** Find next node.
1187 @param n Current node.
1188 @param r Root node.
1189 @return Pointer to next node or NULL.
1190 */
1191 static dk4_sto_node_t *
dk4sto_list_find_next_node(dk4_sto_node_t * n,dk4_sto_node_t * r)1192 dk4sto_list_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
1193 {
1194 dk4_sto_node_t *back;
1195
1196 back = dk4sto_unsorted_find_next_node(n,r);
1197
1198 return back;
1199 }
1200
1201
1202
1203 /** Find last (previous) node.
1204 @param n Current node.
1205 @return Pointer to previous node or NULL.
1206 */
1207 static dk4_sto_node_t *
dk4sto_list_find_last_node(dk4_sto_node_t * n)1208 dk4sto_list_find_last_node(dk4_sto_node_t *n)
1209 {
1210 dk4_sto_node_t *back;
1211
1212 back = dk4sto_unsorted_find_last_node(n);
1213
1214 return back;
1215 }
1216
1217
1218
1219 /** Remove storage node from list storage.
1220 @param ro Root node.
1221 @param n Node to remove.
1222 */
1223 static dk4_sto_node_t *
dk4sto_list_remove(dk4_sto_node_t * ro,dk4_sto_node_t * n)1224 dk4sto_list_remove(dk4_sto_node_t *ro, dk4_sto_node_t *n)
1225 {
1226 dk4_sto_node_t *back;
1227
1228 back = dk4sto_unsorted_remove(ro,n);
1229
1230 return back;
1231 }
1232
1233
1234 /*
1235 COMMON STATIC FUNCTIONS
1236 */
1237
1238
1239 /** Get object node (traverse storage).
1240 @param it Storage iterator.
1241 @param o Object to find storage node.
1242 @return Pointer to node or NULL.
1243 */
1244 static dk4_sto_node_t *
dk4sto_traverse_iterators_for(void * it,void * o)1245 dk4sto_traverse_iterators_for(void *it, void *o)
1246 {
1247 dk4_sto_node_t *back = NULL;
1248 dk4_sto_it_t *c = NULL; /* Current node. */
1249
1250 #if DK4_USE_ASSERT
1251 assert(NULL != it);
1252 assert(NULL != o);
1253 #endif
1254 if(it) {
1255 c = (dk4_sto_it_t *)it;
1256 while(c && (!back)) {
1257 if(c->c) {
1258 if(((c->c)->o) == o) {
1259 back = c->c;
1260 }
1261 }
1262 if(!back) c = c->r;
1263 }
1264 }
1265 return back;
1266 }
1267
1268
1269
1270 /** Find last storage node.
1271 @param n Current storage node.
1272 @param st Storage.
1273 @return Pointer to last node or NULL.
1274 */
1275 static dk4_sto_node_t *
dk4sto_find_last_node(dk4_sto_node_t * n,dk4_sto_t * st)1276 dk4sto_find_last_node(dk4_sto_node_t *n, dk4_sto_t *st)
1277 {
1278 dk4_sto_node_t *back = NULL;
1279
1280 #if DK4_USE_ASSERT
1281 assert(NULL != st);
1282 #endif
1283 if(st->h) {
1284 if(st->t) {
1285 back = dk4sto_tree_find_last_node(n);
1286 } else {
1287 back = dk4sto_list_find_last_node(n);
1288 }
1289 } else {
1290 back = dk4sto_unsorted_find_last_node(n);
1291 }
1292
1293 return back;
1294 }
1295
1296
1297
1298 /** Initialize storage.
1299 @param st Storage to initialize.
1300 @param erp Error report, may be NULL.
1301 @return 1 on success, 0 on error.
1302 */
1303 static int
dk4sto_storage_init(dk4_sto_t * st,dk4_er_t * erp)1304 dk4sto_storage_init(dk4_sto_t *st, dk4_er_t *erp)
1305 {
1306 int back = 0;
1307 short l = 0; /* Critical path length. */
1308
1309 #if DK4_USE_ASSERT
1310 assert(NULL != st);
1311 #endif
1312 /* delpath begin address and length */
1313 st->d = NULL; st->l = 0;
1314 /* root node */
1315 st->r = NULL;
1316 /* comparison method */
1317 st->h = 0;
1318 /* comparison criteria */
1319 st->c = 0;
1320 /* iterators list */
1321 st->i = NULL;
1322 st->l = l = 1536;
1323 st->d = dk4mem_new(dk4_sto_node_p,(size_t)l,erp);
1324 st->t = 1;
1325 if(st->d) {
1326 back = 1;
1327 }
1328 return back;
1329 }
1330
1331
1332
1333 /** Close the storage, release memory.
1334 @param st Storage to close.
1335 */
1336 static void
dk4sto_storage_end(dk4_sto_t * st)1337 dk4sto_storage_end(dk4_sto_t *st)
1338 {
1339
1340 #if DK4_USE_ASSERT
1341 assert(NULL != st);
1342 #endif
1343 /* release iterators */
1344 {
1345 dk4_sto_it_t *c = NULL; /* Current iterator. */
1346 dk4_sto_it_t *n = NULL; /* Next iterator. */
1347 c = (dk4_sto_it_t *)(st->i);
1348 st->i = NULL;
1349 while(c) {
1350
1351 n = c->r;
1352 c->r = NULL;
1353 c->l = NULL;
1354 c->c = NULL;
1355 c->s = NULL;
1356 dk4mem_free(c) ;
1357 c = n;
1358 }
1359 st->i = NULL;
1360 }
1361
1362 /* release nodes */
1363 {
1364 if(st->h) {
1365 if(st->t) {
1366 dk4sto_tree_release_all_nodes(st->r);
1367 } else {
1368 dk4sto_list_release_all_nodes(st->r);
1369 }
1370 } else {
1371 dk4sto_unsorted_release_all_nodes(st->r);
1372 }
1373 st->r = NULL;
1374 }
1375
1376 /* release delpath */
1377 {
1378 dk4_sto_node_p *p;
1379 p = st->d;
1380 dk4mem_free(p);
1381 st->d = NULL; st->l = 0;
1382 }
1383
1384 /* set pointers to NULL */
1385 {
1386 st->h = 0;
1387 st->c = 0;
1388 }
1389
1390
1391 }
1392
1393
1394
1395 /*
1396 PUBLIC INTERFACES
1397 */
1398
1399
1400 dk4_sto_t *
dk4sto_open(dk4_er_t * erp)1401 dk4sto_open(dk4_er_t *erp)
1402 {
1403 dk4_sto_t *back = NULL;
1404
1405 back = dk4mem_new(dk4_sto_t,1,erp) ;
1406 if(back) {
1407 if(!dk4sto_storage_init(back,erp)) {
1408 dk4mem_free(back);
1409 back = NULL;
1410 }
1411 }
1412 return back;
1413 }
1414
1415
1416
1417 void
dk4sto_close(dk4_sto_t * st)1418 dk4sto_close(dk4_sto_t *st)
1419 {
1420
1421 #if DK4_USE_ASSERT
1422 assert(NULL != st);
1423 #endif
1424 if(st) {
1425 dk4sto_storage_end(st);
1426 dk4mem_free(st) ;
1427 }
1428 }
1429
1430
1431
1432 void
dk4sto_remove_all(dk4_sto_t * st)1433 dk4sto_remove_all(dk4_sto_t *st)
1434 {
1435 #if DK4_USE_ASSERT
1436 assert(NULL != st);
1437 #endif
1438 if(st) {
1439 /* reset all iterators */
1440 dk4_sto_it_t *c = NULL; /* Curent iterator. */
1441 dk4_sto_it_t *n = NULL; /* Next iterator. */
1442 c = (dk4_sto_it_t *)(st->i);
1443 while(c) {
1444 n = c->r;
1445 c->c = NULL;
1446 c = n;
1447 }
1448 /* remove all nodes */
1449 if(st->r) {
1450 if(st->h) {
1451 if(st->t) {
1452 dk4sto_tree_release_all_nodes(st->r);
1453 } else {
1454 dk4sto_list_release_all_nodes(st->r);
1455 }
1456 } else {
1457 dk4sto_unsorted_release_all_nodes(st->r);
1458 }
1459 }
1460 st->r = NULL;
1461 }
1462 }
1463
1464
1465
1466 int
dk4sto_remove(dk4_sto_t * st,void * o,dk4_er_t * erp)1467 dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp)
1468 {
1469 int back = 0;
1470 dk4_sto_node_t *node_to_remove = NULL; /* Node to remove. */
1471 dk4_sto_node_t *ln = NULL; /* Last node. */
1472 dk4_sto_it_t *iterator = NULL; /* Traverse all iterators. */
1473
1474 #if DK4_USE_ASSERT
1475 assert(NULL != st);
1476 assert(NULL != o);
1477 #endif
1478 if((NULL != st) && (NULL != o)) {
1479 node_to_remove = dk4sto_traverse_iterators_for(st->i, o);
1480 if(!node_to_remove) {
1481 if(st->h) {
1482 if(st->t) {
1483 node_to_remove = dk4sto_tree_find_exact(st->r,o,st);
1484 } else {
1485 node_to_remove = dk4sto_list_find_exact(st->r,o);
1486 }
1487 } else {
1488 node_to_remove = dk4sto_unsorted_find_exact(st->r,o);
1489 }
1490 }
1491 if(node_to_remove) {
1492 back = 1;
1493 ln = dk4sto_find_last_node(node_to_remove,st);
1494 iterator = (dk4_sto_it_t *)(st->i);
1495 while(iterator) {
1496 if((iterator->c) == node_to_remove) {
1497 iterator->c = ln;
1498 }
1499 iterator = iterator->r;
1500 }
1501 if(st->h) {
1502 if(st->t) {
1503 st->r =
1504 dk4sto_tree_remove(st->r,node_to_remove,st,&back,&node_to_remove);
1505 } else {
1506 st->r =
1507 dk4sto_list_remove(st->r,node_to_remove);
1508 }
1509 } else {
1510 st->r = dk4sto_unsorted_remove(st->r,node_to_remove);
1511 }
1512 node_to_remove->l = node_to_remove->r = node_to_remove->p = NULL;
1513 node_to_remove->o = NULL;
1514 dk4mem_free(node_to_remove);
1515 } else {
1516 dk4error_set_simple_error_code(erp, DK4_E_NOT_FOUND);
1517 }
1518 } else {
1519 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
1520 }
1521 return back;
1522 }
1523
1524
1525
1526 int
dk4sto_add(dk4_sto_t * st,void * o,dk4_er_t * erp)1527 dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp)
1528 {
1529 int back = 0;
1530 dk4_sto_node_t *n = NULL; /* New node. */
1531
1532 #if DK4_USE_ASSERT
1533 assert(NULL != st);
1534 assert(NULL != o);
1535 #endif
1536 if((NULL != st) && (NULL != o)) {
1537 n = dk4mem_new(dk4_sto_node_t,1,erp);
1538 if(n) {
1539 dk4sto_node_init_for_object(n,o,st,st->c);
1540 if(st->h) {
1541 if(st->t) {
1542 st->r = dk4sto_tree_add(st->r, n, st);
1543 } else {
1544 st->r = dk4sto_list_add(st->r, n, st);
1545 }
1546 } else {
1547 st->r = dk4sto_unsorted_add(st->r, n);
1548 }
1549 back = 1;
1550 }
1551 } else {
1552 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
1553 }
1554 return back;
1555 }
1556
1557
1558
1559 dk4_sto_it_t *
dk4sto_it_open(dk4_sto_t * st,dk4_er_t * erp)1560 dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp)
1561 {
1562 dk4_sto_it_t *back = NULL;
1563
1564 #if DK4_USE_ASSERT
1565 assert(NULL != st);
1566 #endif
1567 if(st) {
1568 back = dk4mem_new(dk4_sto_it_t,1,erp);
1569 if(back) {
1570 back->s = st;
1571 back->l = NULL;
1572 back->r = (dk4_sto_it_t *)(st->i);
1573 back->c = NULL;
1574 st->i = (void *)back;
1575 }
1576 } else {
1577 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
1578 }
1579 return back;
1580 }
1581
1582
1583
1584 void
dk4sto_it_close(dk4_sto_it_t * it)1585 dk4sto_it_close(dk4_sto_it_t *it)
1586 {
1587 dk4_sto_it_t *l = NULL; /* Left iterator. */
1588 dk4_sto_it_t *r = NULL; /* Right iterator. */
1589 dk4_sto_t *s = NULL; /* The storage. */
1590
1591 #if DK4_USE_ASSERT
1592 assert(NULL != it);
1593 #endif
1594 if(it) {
1595 s = it->s;
1596 l = it->l;
1597 r = it->r;
1598 if(l) {
1599 l->r = r;
1600 } else {
1601 s->i = (void *)(r);
1602 }
1603 if(r) {
1604 r->l = l;
1605 }
1606 it->s = NULL;
1607 it->l = it->r = NULL;
1608 it->c = NULL;
1609 dk4mem_free(it) ;
1610 }
1611 }
1612
1613
1614
1615 void
dk4sto_it_reset(dk4_sto_it_t * it)1616 dk4sto_it_reset(dk4_sto_it_t *it)
1617 {
1618
1619 #if DK4_USE_ASSERT
1620 assert(NULL != it);
1621 #endif
1622 if(it) {
1623 it->c = NULL;
1624 }
1625 }
1626
1627
1628
1629 void *
dk4sto_it_next(dk4_sto_it_t * it)1630 dk4sto_it_next(dk4_sto_it_t *it)
1631 {
1632 void *back = NULL;
1633
1634 #if DK4_USE_ASSERT
1635 assert(NULL != it);
1636 #endif
1637 if(it) {
1638 if(it->s) {
1639 if((it->s)->h) {
1640 if((it->s)->t) {
1641 it->c = dk4sto_tree_find_next_node(it->c, (it->s)->r);
1642 } else {
1643 it->c = dk4sto_list_find_next_node(it->c, (it->s)->r);
1644 }
1645 } else {
1646 it->c = dk4sto_unsorted_find_next_node(it->c, (it->s)->r);
1647 }
1648 if(it->c) {
1649 back = (it->c)->o;
1650 }
1651 }
1652 }
1653 return back;
1654 }
1655
1656
1657
1658 void *
dk4sto_it_find_exact(dk4_sto_it_t * i,void const * o)1659 dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o)
1660 {
1661 void *back = NULL;
1662
1663 #if DK4_USE_ASSERT
1664 assert(NULL != i);
1665 assert(NULL != o);
1666 #endif
1667 if((NULL != i) && (NULL != o)) {
1668 if(i->s) {
1669 if((i->s)->h) {
1670 if((i->s)->t) {
1671 i->c = dk4sto_tree_find_exact((i->s)->r, o, i->s);
1672 } else {
1673 i->c = dk4sto_list_find_exact((i->s)->r, o);
1674 }
1675 } else {
1676 i->c = dk4sto_unsorted_find_exact((i->s)->r, o);
1677 }
1678 }
1679 if(i->c) {
1680 back = (i->c)->o;
1681 }
1682 }
1683 return back;
1684 }
1685
1686
1687
1688 void *
dk4sto_it_find_like(dk4_sto_it_t * i,void const * o,int cr)1689 dk4sto_it_find_like(dk4_sto_it_t *i, void const *o, int cr)
1690 {
1691 void *back = NULL;
1692 dk4_sto_node_t testnode; /* Test node for comparisons. */
1693 dk4_sto_node_t *candidate = NULL; /* Candicate node. */
1694
1695 #if DK4_USE_ASSERT
1696 assert(NULL != i);
1697 assert(NULL != o);
1698 #endif
1699 if((NULL != i) && (NULL != o)) {
1700 if(i->s) {
1701 candidate = NULL;
1702 if((i->s)->h) {
1703 dk4sto_node_init_for_object(&testnode, (void *)o, (i->s), cr);
1704 if((i->s)->t) {
1705 i->c =
1706 dk4sto_tree_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
1707 } else {
1708 i->c =
1709 dk4sto_list_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
1710 }
1711 } else {
1712 i->c = dk4sto_unsorted_find_exact((i->s)->r, o);
1713 }
1714 if(i->c) {
1715 back = (i->c)->o;
1716 } else {
1717 i->c = candidate;
1718 }
1719 }
1720 }
1721 return back;
1722 }
1723
1724
1725
1726 int
dk4sto_set_eval_c(dk4_sto_t * st,dk4_fct_eval_c_t * f,int cr)1727 dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr)
1728 {
1729 int back = 0;
1730
1731 #if DK4_USE_ASSERT
1732 assert(NULL != st);
1733 assert(NULL != f);
1734 #endif
1735 if(st) {
1736 if(!(st->r)) {
1737 back = 1;
1738 (st->e).c = f;
1739 st->c = cr;
1740 st->h = DK4STO_COMPARE_CHAR;
1741 }
1742 }
1743 return back;
1744 }
1745
1746
1747
1748 int
dk4sto_set_eval_uc(dk4_sto_t * st,dk4_fct_eval_uc_t * f,int cr)1749 dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr)
1750 {
1751 int back = 0;
1752
1753 #if DK4_USE_ASSERT
1754 assert(NULL != st);
1755 assert(NULL != f);
1756 #endif
1757 if(st) {
1758 if(!(st->r)) {
1759 back = 1;
1760 (st->e).uc = f;
1761 st->c = cr;
1762 st->h = DK4STO_COMPARE_UCHAR;
1763 }
1764 }
1765 return back;
1766 }
1767
1768
1769
1770 int
dk4sto_set_eval_s(dk4_sto_t * st,dk4_fct_eval_s_t * f,int cr)1771 dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr)
1772 {
1773 int back = 0;
1774
1775 #if DK4_USE_ASSERT
1776 assert(NULL != st);
1777 assert(NULL != f);
1778 #endif
1779 if(st) {
1780 if(!(st->r)) {
1781 back = 1;
1782 (st->e).s = f;
1783 st->c = cr;
1784 st->h = DK4STO_COMPARE_SHORT;
1785 }
1786 }
1787 return back;
1788 }
1789
1790
1791
1792 int
dk4sto_set_eval_us(dk4_sto_t * st,dk4_fct_eval_us_t * f,int cr)1793 dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr)
1794 {
1795 int back = 0;
1796
1797 #if DK4_USE_ASSERT
1798 assert(NULL != st);
1799 assert(NULL != f);
1800 #endif
1801 if(st) {
1802 if(!(st->r)) {
1803 back = 1;
1804 (st->e).us = f;
1805 st->c = cr;
1806 st->h = DK4STO_COMPARE_USHORT;
1807 }
1808 }
1809 return back;
1810 }
1811
1812
1813
1814 int
dk4sto_set_eval_i(dk4_sto_t * st,dk4_fct_eval_i_t * f,int cr)1815 dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr)
1816 {
1817 int back = 0;
1818
1819 #if DK4_USE_ASSERT
1820 assert(NULL != st);
1821 assert(NULL != f);
1822 #endif
1823 if(st) {
1824 if(!(st->r)) {
1825 back = 1;
1826 (st->e).i = f;
1827 st->c = cr;
1828 st->h = DK4STO_COMPARE_INT;
1829 }
1830 }
1831 return back;
1832 }
1833
1834
1835
1836 int
dk4sto_set_eval_ui(dk4_sto_t * st,dk4_fct_eval_ui_t * f,int cr)1837 dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr)
1838 {
1839 int back = 0;
1840
1841 #if DK4_USE_ASSERT
1842 assert(NULL != st);
1843 assert(NULL != f);
1844 #endif
1845 if(st) {
1846 if(!(st->r)) {
1847 back = 1;
1848 (st->e).ui = f;
1849 st->c = cr;
1850 st->h = DK4STO_COMPARE_UINT;
1851 }
1852 }
1853 return back;
1854 }
1855
1856
1857
1858 int
dk4sto_set_eval_l(dk4_sto_t * st,dk4_fct_eval_l_t * f,int cr)1859 dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr)
1860 {
1861 int back = 0;
1862
1863 #if DK4_USE_ASSERT
1864 assert(NULL != st);
1865 assert(NULL != f);
1866 #endif
1867 if(st) {
1868 if(!(st->r)) {
1869 back = 1;
1870 (st->e).l = f;
1871 st->c = cr;
1872 st->h = DK4STO_COMPARE_LONG;
1873 }
1874 }
1875 return back;
1876 }
1877
1878
1879
1880 int
dk4sto_set_eval_ul(dk4_sto_t * st,dk4_fct_eval_ul_t * f,int cr)1881 dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr)
1882 {
1883 int back = 0;
1884
1885 #if DK4_USE_ASSERT
1886 assert(NULL != st);
1887 assert(NULL != f);
1888 #endif
1889 if(st) {
1890 if(!(st->r)) {
1891 back = 1;
1892 (st->e).ul = f;
1893 st->c = cr;
1894 st->h = DK4STO_COMPARE_ULONG;
1895 }
1896 }
1897 return back;
1898 }
1899
1900
1901
1902 int
dk4sto_set_eval_f(dk4_sto_t * st,dk4_fct_eval_f_t * f,int cr)1903 dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr)
1904 {
1905 int back = 0;
1906
1907 #if DK4_USE_ASSERT
1908 assert(NULL != st);
1909 assert(NULL != f);
1910 #endif
1911 if(st) {
1912 if(!(st->r)) {
1913 back = 1;
1914 (st->e).f = f;
1915 st->c = cr;
1916 st->h = DK4STO_COMPARE_FLOAT;
1917 }
1918 }
1919 return back;
1920 }
1921
1922
1923
1924 int
dk4sto_set_eval_d(dk4_sto_t * st,dk4_fct_eval_d_t * f,int cr)1925 dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr)
1926 {
1927 int back = 0;
1928
1929 #if DK4_USE_ASSERT
1930 assert(NULL != st);
1931 assert(NULL != f);
1932 #endif
1933 if(st) {
1934 if(!(st->r)) {
1935 back = 1;
1936 (st->e).d = f;
1937 st->c = cr;
1938 st->h = DK4STO_COMPARE_DOUBLE;
1939 }
1940 }
1941 return back;
1942 }
1943
1944
1945
1946 int
dk4sto_set_comp(dk4_sto_t * st,dk4_fct_comp_t * f,int cr)1947 dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr)
1948 {
1949 int back = 0;
1950
1951 #if DK4_USE_ASSERT
1952 assert(NULL != st);
1953 assert(NULL != f);
1954 #endif
1955 if(st) {
1956 if(!(st->r)) {
1957 back = 1;
1958 (st->e).comp = f;
1959 st->c = cr;
1960 st->h = DK4STO_COMPARE_FCT;
1961 }
1962 }
1963 return back;
1964 }
1965
1966
1967
1968 int
dk4sto_use_trees(dk4_sto_t * st,int ok)1969 dk4sto_use_trees(dk4_sto_t *st,int ok)
1970 {
1971 int back = 0;
1972 #if DK4_USE_ASSERT
1973 assert(NULL != st);
1974 #endif
1975 if(st) {
1976 if(!(st->r)) {
1977 st->t = (ok ? 1 : 0);
1978 back = 1;
1979 }
1980 }
1981 return back;
1982 }
1983
1984
1985 void *
dk4sto_find_root(dk4_sto_t const * s)1986 dk4sto_find_root(dk4_sto_t const *s)
1987 {
1988 void *back = NULL;
1989 #if DK4_USE_ASSERT
1990 assert(NULL != s);
1991 #endif
1992 if(s) {
1993 if(s->r) {
1994 back = (s->r)->o;
1995 }
1996 }
1997 return back;
1998 }
1999
2000
2001
2002 void *
dk4sto_it_find_parent(dk4_sto_it_t const * i)2003 dk4sto_it_find_parent(dk4_sto_it_t const *i)
2004 {
2005 void *back = NULL;
2006 #if DK4_USE_ASSERT
2007 assert(NULL != i);
2008 #endif
2009 if(i) {
2010 if(i->c) {
2011 if((i->c)->p) {
2012 back = ((i->c)->p)->o;
2013 }
2014 }
2015 }
2016 return back;
2017 }
2018
2019
2020
2021 void *
dk4sto_it_find_left(dk4_sto_it_t const * i)2022 dk4sto_it_find_left(dk4_sto_it_t const *i)
2023 {
2024 void *back = NULL;
2025 #if DK4_USE_ASSERT
2026 assert(NULL != i);
2027 #endif
2028 if(i) {
2029 if(i->c) {
2030 if((i->c)->l) {
2031 back = ((i->c)->l)->o;
2032 }
2033 }
2034 }
2035 return back;
2036 }
2037
2038
2039
2040 void *
dk4sto_it_find_right(dk4_sto_it_t const * i)2041 dk4sto_it_find_right(dk4_sto_it_t const *i)
2042 {
2043 void *back = NULL;
2044 #if DK4_USE_ASSERT
2045 assert(NULL != i);
2046 #endif
2047 if(i) {
2048 if(i->c) {
2049 if((i->c)->r) {
2050 back = ((i->c)->r)->o;
2051 }
2052 }
2053 }
2054 return back;
2055 }
2056
2057
2058
2059 void *
dk4sto_it_find_root(dk4_sto_it_t const * i)2060 dk4sto_it_find_root(dk4_sto_it_t const *i)
2061 {
2062 void *back = NULL;
2063 #if DK4_USE_ASSERT
2064 assert(NULL != i);
2065 #endif
2066 if(i) {
2067 if(i->s) {
2068 back = dk4sto_find_root(i->s);
2069 }
2070 }
2071 return back;
2072 }
2073
2074
2075
2076 /* vim: set ai sw=2 : */
2077
2078