/* Copyright (C) 2011-2020, Dirk Krause SPDX-License-Identifier: BSD-3-Clause */ /* WARNING: This file was generated by the dkct program (see http://dktools.sourceforge.net/ for details). Changes you make here will be lost if dkct is run again! You should modify the original source and run dkct on it. Original source: dk4sto.ctr */ /** @file dk4sto.c The dk4sto module. */ #line 466 "dk4sto.ctr" #include "dk4conf.h" #if DK4_HAVE_ASSERT_H #ifndef ASSERT_H_INCLUDED #include #define ASSERT_H_INCLUDED 1 #endif #endif #include "dk4sto.h" #include "dk4mem.h" #if 0 #ifndef STDLIB_H_INCLUDED #include #define STDLIB_H_INCLUDED 1 #endif #endif #if DK4_HAVE_ASSERT_H #ifndef ASSERT_H_INCLUDED #include #define ASSERT_H_INCLUDED 1 #endif #endif #line 494 "dk4sto.ctr" /** Comparison criteria for comparing nodes. */ enum { DK4STO_COMPARE_NONE = 0, /**< Do not compare the objects (unsorted). */ DK4STO_COMPARE_FCT , /**< Use comparison function. */ DK4STO_COMPARE_CHAR , /**< Evaluate objects to char values. */ DK4STO_COMPARE_UCHAR , /**< Evaluate to unsigned char values. */ DK4STO_COMPARE_SHORT , /**< Evaluate to short values. */ DK4STO_COMPARE_USHORT , /**< Evaluate to unsigned short values. */ DK4STO_COMPARE_INT , /**< Evaluate to int values. */ DK4STO_COMPARE_UINT , /**< Evaluate to unsigned int values. */ DK4STO_COMPARE_LONG , /**< Evaluate to long values. */ DK4STO_COMPARE_ULONG , /**< Evaluate to unsigned long values. */ DK4STO_COMPARE_FLOAT , /**< Evaluate to float values. */ DK4STO_COMPARE_DOUBLE /**< Evaluate to double values. */ }; /* GENERAL STATIC FUNCTIONS */ /** Initialize storage node for object. @param n Storage node. @param o Object. @param s Storage. @param crit Comparison/evaluation criteria used by storage. */ static void dk4sto_node_init_for_object( dk4_sto_node_t *n, void *o, dk4_sto_t *s, int crit ) { #line 535 "dk4sto.ctr" n->p = n->l = n->r = NULL; n->b = n->w = 0; n->o = o; switch(s->h) { case DK4STO_COMPARE_CHAR: (n->v).c = (*((s->e).c))(o,crit); break; case DK4STO_COMPARE_UCHAR: (n->v).uc = (*((s->e).uc))(o,crit); break; case DK4STO_COMPARE_SHORT: (n->v).s = (*((s->e).s))(o,crit); break; case DK4STO_COMPARE_USHORT: (n->v).us = (*((s->e).us))(o,crit); break; case DK4STO_COMPARE_INT: (n->v).i = (*((s->e).i))(o,crit); break; case DK4STO_COMPARE_UINT: (n->v).ui = (*((s->e).ui))(o,crit); break; case DK4STO_COMPARE_LONG: (n->v).l = (*((s->e).l))(o,crit); break; case DK4STO_COMPARE_ULONG: (n->v).ul = (*((s->e).ul))(o,crit); break; case DK4STO_COMPARE_FLOAT: (n->v).f = (*((s->e).f))(o,crit); break; case DK4STO_COMPARE_DOUBLE: (n->v).d = (*((s->e).d))(o,crit); break; } #line 550 "dk4sto.ctr" } /** Copy data from one storage node to another. @param d Destination node. @param s Source node. @param st Storage. */ static void dk4sto_node_data_copy( dk4_sto_node_t *d, dk4_sto_node_t const *s, dk4_sto_t *st ) { #line 567 "dk4sto.ctr" d->o = s->o; switch(st->h) { case DK4STO_COMPARE_CHAR: (d->v).c = (s->v).c ; break; case DK4STO_COMPARE_UCHAR: (d->v).uc = (s->v).uc ; break; case DK4STO_COMPARE_SHORT: (d->v).s = (s->v).s ; break; case DK4STO_COMPARE_USHORT: (d->v).us = (s->v).us ; break; case DK4STO_COMPARE_INT: (d->v).i = (s->v).i ; break; case DK4STO_COMPARE_UINT: (d->v).ui = (s->v).ui ; break; case DK4STO_COMPARE_LONG: (d->v).l = (s->v).l ; break; case DK4STO_COMPARE_ULONG: (d->v).ul = (s->v).ul ; break; case DK4STO_COMPARE_FLOAT: (d->v).f = (s->v).f ; break; case DK4STO_COMPARE_DOUBLE: (d->v).d = (s->v).d ; break; } #line 581 "dk4sto.ctr" } /** Compare two storage nodes. @param l Left node. @param r Right node. @param s Storage. @param c Comparison criteria. @return Comparison result. */ static int dk4sto_node_compare( dk4_sto_node_t const *l, dk4_sto_node_t const *r, dk4_sto_t const *s, int c ) { int back = 0; #line 603 "dk4sto.ctr" /* Static code analysis: Result of operation is garbage or undefined. Clang static code analysis complains the right operand in comparisons (r->v).xxx could be garbage. I think this is not correct. It assumes the default branch is taken in dk4sto_node_init_for_object() as s->h does not match any of the case values. The same case values are are used here, and there is no change of s->h meanwhile. */ switch(s->h) { case DK4STO_COMPARE_FCT: { #line 614 "dk4sto.ctr" back = (*((s->e).comp))((void *)(l->o),(void *)(r->o),c); if(back < 0) back = -1; if(back > 0) back = 1; } break; case DK4STO_COMPARE_CHAR: { #line 619 "dk4sto.ctr" if(((l->v).c) > ((r->v).c)) { back = 1; } else { if(((l->v).c) < ((r->v).c)) { back = -1; } } } break; case DK4STO_COMPARE_UCHAR: { #line 623 "dk4sto.ctr" if(((l->v).uc) > ((r->v).uc)) { back = 1; } else { if(((l->v).uc) < ((r->v).uc)) { back = -1; } } } break; case DK4STO_COMPARE_SHORT: { #line 627 "dk4sto.ctr" if(((l->v).s) > ((r->v).s)) { back = 1; } else { if(((l->v).s) < ((r->v).s)) { back = -1; } } } break; case DK4STO_COMPARE_USHORT: { #line 631 "dk4sto.ctr" if(((l->v).us) > ((r->v).us)) { back = 1; } else { if(((l->v).us) < ((r->v).us)) { back = -1; } } } break; case DK4STO_COMPARE_INT: { #line 635 "dk4sto.ctr" if(((l->v).i) > ((r->v).i)) { back = 1; } else { if(((l->v).i) < ((r->v).i)) { back = -1; } } } break; case DK4STO_COMPARE_UINT: { #line 639 "dk4sto.ctr" if(((l->v).ui) > ((r->v).ui)) { back = 1; } else { if(((l->v).ui) < ((r->v).ui)) { back = -1; } } } break; case DK4STO_COMPARE_LONG: { #line 643 "dk4sto.ctr" if(((l->v).l) > ((r->v).l)) { back = 1; } else { if(((l->v).l) < ((r->v).l)) { back = -1; } } } break; case DK4STO_COMPARE_ULONG: { #line 647 "dk4sto.ctr" if(((l->v).ul) > ((r->v).ul)) { back = 1; } else { if(((l->v).ul) < ((r->v).ul)) { back = -1; } } } break; case DK4STO_COMPARE_FLOAT: { #line 651 "dk4sto.ctr" if(((l->v).f) > ((r->v).f)) { back = 1; } else { if(((l->v).f) < ((r->v).f)) { back = -1; } } } break; case DK4STO_COMPARE_DOUBLE: { #line 655 "dk4sto.ctr" if(((l->v).d) > ((r->v).d)) { back = 1; } else { if(((l->v).d) < ((r->v).d)) { back = -1; } } } break; } #line 659 "dk4sto.ctr" return back; } /* UNSORTED DATA HANDLING */ /** Remove node from an unsorted storage. @param ro Root node. @param n Node to remove. @return New root node. */ static dk4_sto_node_t * dk4sto_unsorted_remove(dk4_sto_node_t *ro, dk4_sto_node_t *n) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *l = NULL; /* Left element. */ dk4_sto_node_t *r = NULL; /* Right element. */ #line 680 "dk4sto.ctr" back = ro; l = n->l; r = n->r; if(r) { r->l = l; } if(l) { l->r = r; } else { back = r; } #line 690 "dk4sto.ctr" return back; } /** Add node to an unsorted storage. @param r Old root node. @param n Node to add. @return New root node or NULL. */ static dk4_sto_node_t * dk4sto_unsorted_add(dk4_sto_node_t *r, dk4_sto_node_t *n) { dk4_sto_node_t *back; #line 705 "dk4sto.ctr" back = n; n->r = r; if(r) { r->l = n; } #line 710 "dk4sto.ctr" return back; } /** Release all nodes in an unsorted storage. @param r Root node. */ static void dk4sto_unsorted_release_all_nodes(dk4_sto_node_t *r) { dk4_sto_node_t *c; /* Current element. */ dk4_sto_node_t *n; /* Next element. */ #line 724 "dk4sto.ctr" c = r; while(c) { n = c->r; c->p = c->l = c->r = NULL; c->o = NULL; c->b = c->w = 0; dk4mem_free(c) ; c = n; } #line 734 "dk4sto.ctr" } /** Find next node in an unsorted storage. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk4_sto_node_t * dk4sto_unsorted_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r) { dk4_sto_node_t *back = NULL; #line 749 "dk4sto.ctr" if(n) { back = n->r; } else { back = r; } #line 754 "dk4sto.ctr" return back; } /** Find last node in an unsorted storage. @param n Root node. @return Last node or NULL. */ static dk4_sto_node_t * dk4sto_unsorted_find_last_node(dk4_sto_node_t *n) { dk4_sto_node_t *back = NULL; #line 768 "dk4sto.ctr" if(n) back = n->l; #line 770 "dk4sto.ctr" return back; } /** Find node for an object in an unsorted storage. @param r Root node. @param o Object. @return Node for object or NULL. */ static dk4_sto_node_t * dk4sto_unsorted_find_exact(dk4_sto_node_t *r, void const *o) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *c; /* Current node. */ #line 786 "dk4sto.ctr" c = r; while(c && (!back)) { if((c->o) == o) { back = c; } c = c->r; } #line 793 "dk4sto.ctr" return back; } /* SORTED DATA HANDLING */ /** Direction to walk to. */ enum { DK4STO_WALK_LEFT = 1, /**< Go to left. */ DK4STO_WALK_RIGHT = 2 /**< Go to right. */ }; /** Perform left rotation at node. @param p Subpath to modify. @return New subpath root node or NULL. */ static dk4_sto_node_t * dk4sto_left_rotation(dk4_sto_node_t *p) { dk4_sto_node_t *p1; #line 822 "dk4sto.ctr" p1 = p->r; p->r = p1->l; if(p->r) (p->r)->p = p; p1->l = p; if(p) p->p = p1; #line 828 "dk4sto.ctr" return p1; } /** Perform right rotation at node. @param p Subpath to modify. @return New subpath root node or NULL. */ static dk4_sto_node_t * dk4sto_right_rotation(dk4_sto_node_t *p) { dk4_sto_node_t *p1; #line 842 "dk4sto.ctr" p1 = p->l; p->l = p1->r; if(p->l) (p->l)->p = p; p1->r = p; if(p) p->p = p1; #line 848 "dk4sto.ctr" return p1; } /** Increment balance field of a storage node. @param p Node to modify. */ static void dk4sto_inc_balance(dk4_sto_node_t *p) { short x; /* New balance value. */ #line 861 "dk4sto.ctr" x = p->b; #line 862 "dk4sto.ctr" x++; if(x > 3) x = 0; p->b = x; #line 865 "dk4sto.ctr" } /** Decrement balance field of a storage node. @param p Storage node. */ static void dk4sto_dec_balance(dk4_sto_node_t *p) { short x; /* New balance value. */ #line 877 "dk4sto.ctr" x = p->b; #line 878 "dk4sto.ctr" x--; if(x < 0) x = 3; p->b = x; #line 881 "dk4sto.ctr" } /** Set mark for "left node deleted". @param p Node. @param h Pointer to balance variable. @return New root node for path behind \a p. */ static dk4_sto_node_t * dk4sto_left_deleted(dk4_sto_node_t *p, short *h) { #line 895 "dk4sto.ctr" switch(p->b) { case 0: *h = - *h; /* fall-through */ case 3: #line 900 "dk4sto.ctr" dk4sto_inc_balance(p); #line 902 "dk4sto.ctr" break; case 1: { switch((p->r)->b) { case 0: (p->r)->b = 3; *h = - *h; p = dk4sto_left_rotation(p); break; case 1: (p->r)->b = 0; p->b = 0; p = dk4sto_left_rotation(p); break; case 3: p->b = (((((p->r)->l)->b) == 1) ? 3 : 0); (p->r)->b = (((((p->r)->l)->b) == 3) ? 1 : 0); p->r = dk4sto_right_rotation(p->r); if(p->r) (p->r)->p = p; p = dk4sto_left_rotation(p); p->b = 0; } } } #line 926 "dk4sto.ctr" return p; } /** Set mark for "right node deleted". @param p Node. @param h Pointer to balance variable. @return New root node for path behind \a p. */ static dk4_sto_node_t * dk4sto_right_deleted(dk4_sto_node_t *p, short *h) { #line 940 "dk4sto.ctr" switch(p->b) { case 0: *h = - *h; /* fall-through */ case 1: dk4sto_dec_balance(p); break; case 3: { switch((p->l)->b) { case 0: (p->l)->b = 1; *h = - *h; p = dk4sto_right_rotation(p); break; case 3: (p->l)->b = 0; p->b = 0; p = dk4sto_right_rotation(p); break; case 1: p->b = (((((p->l)->r)->b) == 3) ? 1 : 0); (p->l)->b = (((((p->l)->r)->b) == 1) ? 3 : 0); p->l = dk4sto_left_rotation(p->l); if(p->l) (p->l)->p = p; p = dk4sto_right_rotation(p); p->b = 0; } } } #line 968 "dk4sto.ctr" return p; } /** Add node to tree storage. @param root Root node. @param newnode Node to add. @param st Storage. @return New root node or NULL. */ static dk4_sto_node_t * dk4sto_avlt_add(dk4_sto_node_t *root, dk4_sto_node_t *newnode, dk4_sto_t *st) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *p = NULL; /* Current node. */ dk4_sto_node_t *q = NULL; /* Father of p. */ dk4_sto_node_t *r = NULL; /* Critical node. */ dk4_sto_node_t *s = NULL; /* Father of r. */ #line 989 "dk4sto.ctr" back = root; p = r = root; q = s = NULL; /* Search place for insertion, write direction into the "w" field in each node. The final new node has an empty "w" field. */ while(p) { /* q is either NULL (in first pass) or the parent of the current node in p. */ if(p->b) { s = q; r = p; } q = p; if(dk4sto_node_compare(p,newnode,st,st->c) > 0) { p->w = DK4STO_WALK_LEFT; p = p->l; } else { p->w = DK4STO_WALK_RIGHT; p = p->r; } } /* q is either NULL or the last node visited. r is the last unbalanced node (critical node). s is either NULL or the parent of the last unbalanced node. */ p = newnode; if(NULL == back) { /* When inserting into an empty tree we are done here. */ back = p; } else { /* The tree is not empty. The new node p is concatenated to the parent q. */ if(dk4sto_node_compare(q,newnode,st,st->c) > 0) { q->l = p; q->w = DK4STO_WALK_LEFT; } else { q->r = p; q->w = DK4STO_WALK_RIGHT; } p->p = q; /* Now we must balance the tree again if necessary. */ if(r) { /* There is a critical node. */ p = r; /* Modify balance fields from critial node until we find our new node. */ while(p->w) { if(p->w == DK4STO_WALK_LEFT) { dk4sto_dec_balance(p); p = p->l; } else { dk4sto_inc_balance(p); p = p->r; } } p = r; /* Now look whether we are dis-balanced, correct if necessary. */ if((p->b) == 2) { /* We must balance */ if(p->w == DK4STO_WALK_LEFT) { if((p->l)->b == 3) { p->b = 0; p = dk4sto_right_rotation(p); } else { /* Static code analyis: Potentially dereferencing NULL pointer. I do not think so. We have to balance at p because the left subtree is too deep. We did not add the new node to the left childs left subtree, so we must have added it to the left childs right subtree. So the left childs right child can not be NULL. */ #if DK4_USE_ASSERT assert (NULL != (p->l)->r); #endif p->b = (((((p->l)->r)->b) == 3) ? 1 : 0); (p->l)->b = (((((p->l)->r)->b) == 1) ? 3 : 0); p->l = dk4sto_left_rotation(p->l); if(p->l) (p->l)->p = p; p = dk4sto_right_rotation(p); } } else { if((p->r)->b == 1) { p->b = 0; p = dk4sto_left_rotation(p); } else { /* Static code analyis: Potentially dereferencing NULL pointer. I do not think so. We have to balance at p because the right subtree is too deep. We did not add the new node to the right childs right subtree, so we must have added it to the right childs left subtree. So the right childs left child can not be NULL. */ #if DK4_USE_ASSERT assert(NULL != (p->r)->l); #endif p->b = (((((p->r)->l)->b) == 1) ? 3 : 0); (p->r)->b = (((((p->r)->l)->b) == 3) ? 1 : 0); p->r = dk4sto_right_rotation(p->r); if(p->r) (p->r)->p = p; p = dk4sto_left_rotation(p); } } p->b = 0; /* Balance at the critical nodes father (if there is one) or create new root. */ if(s) { if(s->w == DK4STO_WALK_LEFT) { s->l = p; } else { s->r = p; } if(p) p->p = s; } else { back = p; } } } } if(back) { back->p = NULL; } #line 1130 "dk4sto.ctr" return back; } /** Find last node in a tree storage. @param n Node to start search from. @return Last node or NULL. */ static dk4_sto_node_t * dk4sto_tree_find_last_node(dk4_sto_node_t *n) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *c; /* Current node. */ dk4_sto_node_t *p; /* Father of c. */ #line 1146 "dk4sto.ctr" if(n->l) { back = n->l; while(back->r) { back = back->r; } } else { c = n; p = c->p; while(p && (!back)) { if((p->r) == c) { back = p; } else { c = p; p = c->p; } } } #line 1159 "dk4sto.ctr" return back; } /** Remove storage node from tree storage. @param root Root object. @param node Node to remove. @param delpath Deletion path (used for tree balancing). @param st Storage. @param success_indicator Pointer to success variable. @param toremove Node to remove. @return New root object. */ 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 ) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *p = NULL; /* Current node. */ dk4_sto_node_t *q = NULL; /* Father of p. */ dk4_sto_node_t *r = NULL; /* Critical node. */ dk4_sto_node_t *todel = NULL; /* Node to delete. */ dk4_sto_node_t *itn = NULL; /* Iterator node. */ dk4_sto_it_t *iterat = NULL; /* Iterator */ short x1 = 0; /* Balance value. */ short delroot = 0; /* Flag: Delete tree node. */ int can_continue = 1; /* Flag: Can continue. */ back = root; todel = node; #line 1192 "dk4sto.ctr" /* Make sure the node to delete has max. 1 subtree. */ if((todel->l) && (todel->r)) { #line 1198 "dk4sto.ctr" todel = todel->l; while(todel->r) todel = todel->r; dk4sto_node_data_copy(node,todel,st); /* 2019-03-24 Change iterators again. */ itn = dk4sto_tree_find_last_node(todel); iterat = (dk4_sto_it_t *)(st->i); while(NULL != iterat) { if ((iterat->c) == todel) { iterat->c = itn; } iterat = iterat->r; } } if(!(todel->p)) { #line 1214 "dk4sto.ctr" delroot = 1; } /* Mark the way in the "w" fields. */ *toremove = todel; todel->w = 0; while(todel->p) { if((todel->p)->l == todel) { #line 1224 "dk4sto.ctr" (todel->p)->w = DK4STO_WALK_LEFT; } else { #line 1227 "dk4sto.ctr" (todel->p)->w = DK4STO_WALK_RIGHT; } todel = todel->p; } p = back; q = r = NULL; x1 = 0; can_continue = 1; while(can_continue) { #line 1237 "dk4sto.ctr" #if VERSION_BEFORE_20150821 if(p) { #line 1239 "dk4sto.ctr" #endif if(p->w) { #line 1241 "dk4sto.ctr" if(p->b == 0) { x1 = 0; #line 1243 "dk4sto.ctr" } delpath[x1++] = p; #line 1245 "dk4sto.ctr" if(x1 >= st->l) { #line 1246 "dk4sto.ctr" /* x1 too large */ *success_indicator = 0; goto error_mark; } if(p->w == DK4STO_WALK_LEFT) { #line 1251 "dk4sto.ctr" p = p->l; } else { #line 1253 "dk4sto.ctr" p = p->r; } } else { can_continue = 0; #line 1257 "dk4sto.ctr" } #if VERSION_BEFORE_20150821 } else { can_continue = 0; #line 1261 "dk4sto.ctr" } #endif } #if VERSION_BEFORE_20150821 r = p; #endif /* 2015-08-21 Static code analysis complains p could be NULL. I think it can not. */ if(NULL != p->l) q = p->l; else q = p->r; if(x1 == 0) { if(delroot) { #line 1274 "dk4sto.ctr" back = q; } } while(x1 > 0) { #line 1278 "dk4sto.ctr" x1--; p = delpath[x1]; if(p->w == DK4STO_WALK_LEFT) { #line 1282 "dk4sto.ctr" p->l = q; if(q) q->p = p; q = dk4sto_left_deleted(p, &x1); #line 1285 "dk4sto.ctr" } else { #line 1287 "dk4sto.ctr" p->r = q; if(q) q->p = p; q = dk4sto_right_deleted(p, &x1); #line 1290 "dk4sto.ctr" } if(x1 == 0) { #line 1293 "dk4sto.ctr" if(delpath[x1] == back) { #line 1295 "dk4sto.ctr" back = q; } } if(x1 < 0) { #line 1299 "dk4sto.ctr" p = delpath[0 - x1 - 1]; if(p->w == DK4STO_WALK_LEFT) { p->l = q; } else { p->r = q; } if(q) q->p = p; } } error_mark: if(back) { back->p = NULL; } #line 1313 "dk4sto.ctr" return back; } /** Find storage node for an object evaluated like a given object. @param root Root node. @param testnode Node of the given object. @param st Storage. @param crit Comparison criteria. @param cand Pointer for candidate. @return Pointer to storage node or NULL. */ static 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 ) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *c = NULL; /* Current node. */ int testval = 0; /* Comparison result. */ #line 1337 "dk4sto.ctr" c = root; while(c) { testval = dk4sto_node_compare(c,testnode,st,crit); switch(testval) { case -1: { if(cand) *cand = c; c = c->r; } break; case 0: { back = c; c = c->l; } break; default: { c = c->l; } break; } } #line 1353 "dk4sto.ctr" return back; } /** Add node to a tree. @param r Root node. @param n New node to add. @param s Storage. @return Node pointer on success, NULL on error. */ static dk4_sto_node_t * dk4sto_tree_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s) { dk4_sto_node_t *back; back = dk4sto_avlt_add(r,n,s); return back; } /** Release all nodes in a tree storage. @param r Root node. */ static void dk4sto_tree_release_all_nodes(dk4_sto_node_t *r) { #line 1381 "dk4sto.ctr" if(r) { dk4sto_tree_release_all_nodes(r->l); dk4sto_tree_release_all_nodes(r->r); r->l = r->r = r->p = NULL; r->o = NULL; r->b = 0; r->w = 0; dk4mem_free(r) ; } #line 1389 "dk4sto.ctr" } /** Find next node in a tree storage. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk4_sto_node_t * dk4sto_tree_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *c = NULL; /* Current node. */ dk4_sto_node_t *p = NULL; /* Parent of c. */ #line 1405 "dk4sto.ctr" /* if(n) { if(n->r) { back = n->r; while(back->l) { back = back->l; } } else { c = n; p = c->p; while(p && (!back)) { if((p->l) == c) { back = p; } else { c = p; p = c->p; } } } } else { back = r; if(back) { while(back->l) { back = back->l; } } } */ if(n) { if(n->r) { back = n->r; while(back->l) back = back->l; } else { c = n; p = c->p; while(p && (!back)) { if(p->l == c) { back = p; } else { c = p; p = c->p; } } } } else { back = r; if(back) { while(back->l) back = back->l; } } #line 1446 "dk4sto.ctr" return back; } /** Find node for object in tree storage (exact search). @param r Root node. @param o Object to find node for. @param s Storage. @return Pointer to node or NULL. */ static dk4_sto_node_t * dk4sto_tree_find_exact(dk4_sto_node_t *r, void const *o, dk4_sto_t *s) { dk4_sto_node_t *back = NULL; dk4_sto_node_t testnode; /* Test node for comparisons. */ dk4_sto_node_t *c; /* Current node to test. */ dk4_sto_node_t *candidate; /* Candidate for found node. */ int testval = 0; /* Comparison result. */ #line 1466 "dk4sto.ctr" dk4sto_node_init_for_object(&testnode, (void *)o, s, s->c); c = dk4sto_tree_find_like(r, &testnode, s, s->c, &candidate); while(c && (!back)) { testval = dk4sto_node_compare(c, &testnode, s, s->c); if(testval == 0) { if((c->o) == o) { back = c; } else { c = dk4sto_tree_find_next_node(c, r); } } else { c = NULL; } } #line 1480 "dk4sto.ctr" return back; } /** Remove storage node from tree storage. @param ro Root node. @param n Node to delete. @param st Storage. @param sci ??? @param toremove Node to remove. @return New root node. */ 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 ) { dk4_sto_node_t *back; back = dk4sto_avlt_delete(ro,n,st->d,st,sci,toremove); return back; } /* USE DOUBLE LINKED LIST */ /** Find node for an object evaluated like a given object in a list storage. @param root Root node. @param testnode Node with object for comparison. @param st Storage. @param crit Comparison criteria. @param cand Test candidate. @return Pointer to storage node or NULL. */ 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 ) { dk4_sto_node_t *back = NULL; dk4_sto_node_t *c = NULL; /* Current node. */ int testval = 0; /* Comparison result. */ #line 1528 "dk4sto.ctr" c = root; while(c && (!back)) { testval = dk4sto_node_compare(c,testnode,st,crit); switch(testval) { case -1: { if(cand) *cand = c; c = c->r; } break; case 0: { back = c; c = NULL; } break; default : { c = NULL; } break; } } #line 1544 "dk4sto.ctr" return back; } /** Find node for an object (exact search). @param r Root node. @param o Object. @return Pointer to the objects node or NULL. */ static dk4_sto_node_t * dk4sto_list_find_exact(dk4_sto_node_t *r, void const *o) { dk4_sto_node_t *back; #line 1559 "dk4sto.ctr" back = dk4sto_unsorted_find_exact(r,o); #line 1561 "dk4sto.ctr" return back; } /** Add node to list storage. @param r Root node. @param n New node. @param s Storage. @return Pointer on success, NULL on error. */ static dk4_sto_node_t * dk4sto_list_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s) { dk4_sto_node_t *back; dk4_sto_node_t *larger = NULL; /* Last found larger entry. */ dk4_sto_node_t *current = NULL; /* Current node. */ dk4_sto_node_t *smaller = NULL; /* Last found smaller entry. */ int ende; #line 1581 "dk4sto.ctr" back = r; if(r) { larger = smaller = NULL; current = r; ende = 0; while(!ende) { if(dk4sto_node_compare(current,n,s,s->c) >= 0) { larger = current; ende = 1; } else { smaller = current; } if(current->r) { current = current->r; } else { ende = 1; } } if(larger) { n->r = larger; larger->l = n; if(smaller) { smaller->r = n; n->l = smaller; } else { back = n; } } else { if(smaller) { smaller->r = n; n->l = smaller; } } } else { back = n; } #line 1616 "dk4sto.ctr" return back; } /** Release all nodes of a list storage. @param r Root node. */ static void dk4sto_list_release_all_nodes(dk4_sto_node_t *r) { #line 1628 "dk4sto.ctr" dk4sto_unsorted_release_all_nodes(r); #line 1630 "dk4sto.ctr" } /** Find next node. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk4_sto_node_t * dk4sto_list_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r) { dk4_sto_node_t *back; #line 1644 "dk4sto.ctr" back = dk4sto_unsorted_find_next_node(n,r); #line 1646 "dk4sto.ctr" return back; } /** Find last (previous) node. @param n Current node. @return Pointer to previous node or NULL. */ static dk4_sto_node_t * dk4sto_list_find_last_node(dk4_sto_node_t *n) { dk4_sto_node_t *back; #line 1660 "dk4sto.ctr" back = dk4sto_unsorted_find_last_node(n); #line 1662 "dk4sto.ctr" return back; } /** Remove storage node from list storage. @param ro Root node. @param n Node to remove. */ static dk4_sto_node_t * dk4sto_list_remove(dk4_sto_node_t *ro, dk4_sto_node_t *n) { dk4_sto_node_t *back; #line 1676 "dk4sto.ctr" back = dk4sto_unsorted_remove(ro,n); #line 1678 "dk4sto.ctr" return back; } /* COMMON STATIC FUNCTIONS */ /** Get object node (traverse storage). @param it Storage iterator. @param o Object to find storage node. @return Pointer to node or NULL. */ static dk4_sto_node_t * dk4sto_traverse_iterators_for(void *it, void *o) { dk4_sto_node_t *back = NULL; dk4_sto_it_t *c = NULL; /* Current node. */ #line 1698 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != it); assert(NULL != o); #endif if(it) { c = (dk4_sto_it_t *)it; while(c && (!back)) { if(c->c) { if(((c->c)->o) == o) { back = c->c; } } if(!back) c = c->r; } } #line 1713 "dk4sto.ctr" return back; } /** Find last storage node. @param n Current storage node. @param st Storage. @return Pointer to last node or NULL. */ static dk4_sto_node_t * dk4sto_find_last_node(dk4_sto_node_t *n, dk4_sto_t *st) { dk4_sto_node_t *back = NULL; #line 1728 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); #endif if(st->h) { if(st->t) { back = dk4sto_tree_find_last_node(n); } else { back = dk4sto_list_find_last_node(n); } } else { back = dk4sto_unsorted_find_last_node(n); } #line 1741 "dk4sto.ctr" return back; } /** Initialize storage. @param st Storage to initialize. @param erp Error report, may be NULL. @return 1 on success, 0 on error. */ static int dk4sto_storage_init(dk4_sto_t *st, dk4_er_t *erp) { int back = 0; short l = 0; /* Critical path length. */ #line 1757 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); #endif /* delpath begin address and length */ st->d = NULL; st->l = 0; /* root node */ st->r = NULL; /* comparison method */ st->h = 0; /* comparison criteria */ st->c = 0; /* iterators list */ st->i = NULL; st->l = l = 1536; st->d = dk4mem_new(dk4_sto_node_p,l,erp); st->t = 1; if(st->d) { back = 1; } #line 1776 "dk4sto.ctr" return back; } /** Close the storage, release memory. @param st Storage to close. */ static void dk4sto_storage_end(dk4_sto_t *st) { #line 1788 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); #endif /* release iterators */ { dk4_sto_it_t *c = NULL; /* Current iterator. */ dk4_sto_it_t *n = NULL; /* Next iterator. */ c = (dk4_sto_it_t *)(st->i); st->i = NULL; while(c) { #line 1799 "dk4sto.ctr" n = c->r; c->r = NULL; c->l = NULL; c->c = NULL; c->s = NULL; dk4mem_free(c) ; c = n; } st->i = NULL; } #line 1810 "dk4sto.ctr" /* release nodes */ { if(st->h) { if(st->t) { dk4sto_tree_release_all_nodes(st->r); } else { dk4sto_list_release_all_nodes(st->r); } } else { dk4sto_unsorted_release_all_nodes(st->r); } st->r = NULL; } #line 1824 "dk4sto.ctr" /* release delpath */ { dk4_sto_node_p *p; p = st->d; dk4mem_free(p); st->d = NULL; st->l = 0; } #line 1832 "dk4sto.ctr" /* set pointers to NULL */ { st->h = 0; st->c = 0; } #line 1838 "dk4sto.ctr" #line 1839 "dk4sto.ctr" } /* PUBLIC INTERFACES */ dk4_sto_t * dk4sto_open(dk4_er_t *erp) { dk4_sto_t *back = NULL; #line 1853 "dk4sto.ctr" back = dk4mem_new(dk4_sto_t,1,erp) ; if(back) { if(!dk4sto_storage_init(back,erp)) { dk4mem_free(back); back = NULL; } } #line 1860 "dk4sto.ctr" return back; } void dk4sto_close(dk4_sto_t *st) { #line 1869 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); #endif if(st) { dk4sto_storage_end(st); dk4mem_free(st) ; } #line 1876 "dk4sto.ctr" } void dk4sto_remove_all(dk4_sto_t *st) { #if DK4_USE_ASSERT assert(NULL != st); #endif if(st) { /* reset all iterators */ dk4_sto_it_t *c = NULL; /* Curent iterator. */ dk4_sto_it_t *n = NULL; /* Next iterator. */ c = (dk4_sto_it_t *)(st->i); while(c) { n = c->r; c->c = NULL; c = n; } /* remove all nodes */ if(st->r) { if(st->h) { if(st->t) { dk4sto_tree_release_all_nodes(st->r); } else { dk4sto_list_release_all_nodes(st->r); } } else { dk4sto_unsorted_release_all_nodes(st->r); } } st->r = NULL; } } int dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp) { int back = 0; dk4_sto_node_t *node_to_remove = NULL; /* Node to remove. */ dk4_sto_node_t *ln = NULL; /* Last node. */ dk4_sto_it_t *iterator = NULL; /* Traverse all iterators. */ #line 1922 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != o); #endif if((NULL != st) && (NULL != o)) { node_to_remove = dk4sto_traverse_iterators_for(st->i, o); if(!node_to_remove) { if(st->h) { if(st->t) { node_to_remove = dk4sto_tree_find_exact(st->r,o,st); } else { node_to_remove = dk4sto_list_find_exact(st->r,o); } } else { node_to_remove = dk4sto_unsorted_find_exact(st->r,o); } } if(node_to_remove) { back = 1; ln = dk4sto_find_last_node(node_to_remove,st); iterator = (dk4_sto_it_t *)(st->i); while(iterator) { if((iterator->c) == node_to_remove) { iterator->c = ln; } iterator = iterator->r; } if(st->h) { if(st->t) { st->r = dk4sto_tree_remove(st->r,node_to_remove,st,&back,&node_to_remove); } else { st->r = dk4sto_list_remove(st->r,node_to_remove); } } else { st->r = dk4sto_unsorted_remove(st->r,node_to_remove); } node_to_remove->l = node_to_remove->r = node_to_remove->p = NULL; node_to_remove->o = NULL; dk4mem_free(node_to_remove); } else { dk4error_set_simple_error_code(erp, DK4_E_NOT_FOUND); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 1969 "dk4sto.ctr" return back; } int dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp) { int back = 0; dk4_sto_node_t *n = NULL; /* New node. */ #line 1980 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != o); #endif if((NULL != st) && (NULL != o)) { n = dk4mem_new(dk4_sto_node_t,1,erp); if(n) { dk4sto_node_init_for_object(n,o,st,st->c); if(st->h) { if(st->t) { st->r = dk4sto_tree_add(st->r, n, st); } else { st->r = dk4sto_list_add(st->r, n, st); } } else { st->r = dk4sto_unsorted_add(st->r, n); } back = 1; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 2002 "dk4sto.ctr" return back; } dk4_sto_it_t * dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp) { dk4_sto_it_t *back = NULL; #line 2012 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); #endif if(st) { back = dk4mem_new(dk4_sto_it_t,1,erp); if(back) { back->s = st; back->l = NULL; back->r = (dk4_sto_it_t *)(st->i); back->c = NULL; st->i = (void *)back; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 2027 "dk4sto.ctr" return back; } void dk4sto_it_close(dk4_sto_it_t *it) { dk4_sto_it_t *l = NULL; /* Left iterator. */ dk4_sto_it_t *r = NULL; /* Right iterator. */ dk4_sto_t *s = NULL; /* The storage. */ #line 2039 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != it); #endif if(it) { s = it->s; l = it->l; r = it->r; if(l) { l->r = r; } else { s->i = (void *)(r); } if(r) { r->l = l; } it->s = NULL; it->l = it->r = NULL; it->c = NULL; dk4mem_free(it) ; } #line 2059 "dk4sto.ctr" } void dk4sto_it_reset(dk4_sto_it_t *it) { #line 2067 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != it); #endif if(it) { it->c = NULL; } #line 2073 "dk4sto.ctr" } void * dk4sto_it_next(dk4_sto_it_t *it) { void *back = NULL; #line 2082 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != it); #endif if(it) { if(it->s) { if((it->s)->h) { if((it->s)->t) { it->c = dk4sto_tree_find_next_node(it->c, (it->s)->r); } else { it->c = dk4sto_list_find_next_node(it->c, (it->s)->r); } } else { it->c = dk4sto_unsorted_find_next_node(it->c, (it->s)->r); } if(it->c) { back = (it->c)->o; } } } #line 2101 "dk4sto.ctr" return back; } void * dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o) { void *back = NULL; #line 2111 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != i); assert(NULL != o); #endif if((NULL != i) && (NULL != o)) { if(i->s) { if((i->s)->h) { if((i->s)->t) { i->c = dk4sto_tree_find_exact((i->s)->r, o, i->s); } else { i->c = dk4sto_list_find_exact((i->s)->r, o); } } else { i->c = dk4sto_unsorted_find_exact((i->s)->r, o); } } if(i->c) { back = (i->c)->o; } } #line 2131 "dk4sto.ctr" return back; } void * dk4sto_it_find_like(dk4_sto_it_t *i, void const *o, int cr) { void *back = NULL; dk4_sto_node_t testnode; /* Test node for comparisons. */ dk4_sto_node_t *candidate = NULL; /* Candicate node. */ #line 2143 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != i); assert(NULL != o); #endif if((NULL != i) && (NULL != o)) { if(i->s) { candidate = NULL; if((i->s)->h) { dk4sto_node_init_for_object(&testnode, (void *)o, (i->s), cr); if((i->s)->t) { i->c = dk4sto_tree_find_like((i->s)->r, &testnode, i->s, cr, &candidate); } else { i->c = dk4sto_list_find_like((i->s)->r, &testnode, i->s, cr, &candidate); } } else { i->c = dk4sto_unsorted_find_exact((i->s)->r, o); } if(i->c) { back = (i->c)->o; } else { i->c = candidate; } } } #line 2169 "dk4sto.ctr" return back; } int dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr) { int back = 0; #line 2179 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).c = f; st->c = cr; st->h = DK4STO_COMPARE_CHAR; } } #line 2191 "dk4sto.ctr" return back; } int dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr) { int back = 0; #line 2201 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).uc = f; st->c = cr; st->h = DK4STO_COMPARE_UCHAR; } } #line 2213 "dk4sto.ctr" return back; } int dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr) { int back = 0; #line 2223 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).s = f; st->c = cr; st->h = DK4STO_COMPARE_SHORT; } } #line 2235 "dk4sto.ctr" return back; } int dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr) { int back = 0; #line 2245 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).us = f; st->c = cr; st->h = DK4STO_COMPARE_USHORT; } } #line 2257 "dk4sto.ctr" return back; } int dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr) { int back = 0; #line 2267 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).i = f; st->c = cr; st->h = DK4STO_COMPARE_INT; } } #line 2279 "dk4sto.ctr" return back; } int dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr) { int back = 0; #line 2289 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).ui = f; st->c = cr; st->h = DK4STO_COMPARE_UINT; } } #line 2301 "dk4sto.ctr" return back; } int dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr) { int back = 0; #line 2311 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).l = f; st->c = cr; st->h = DK4STO_COMPARE_LONG; } } #line 2323 "dk4sto.ctr" return back; } int dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr) { int back = 0; #line 2333 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).ul = f; st->c = cr; st->h = DK4STO_COMPARE_ULONG; } } #line 2345 "dk4sto.ctr" return back; } int dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr) { int back = 0; #line 2355 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).f = f; st->c = cr; st->h = DK4STO_COMPARE_FLOAT; } } #line 2367 "dk4sto.ctr" return back; } int dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr) { int back = 0; #line 2377 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).d = f; st->c = cr; st->h = DK4STO_COMPARE_DOUBLE; } } #line 2389 "dk4sto.ctr" return back; } int dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr) { int back = 0; #line 2399 "dk4sto.ctr" #if DK4_USE_ASSERT assert(NULL != st); assert(NULL != f); #endif if(st) { if(!(st->r)) { back = 1; (st->e).comp = f; st->c = cr; st->h = DK4STO_COMPARE_FCT; } } #line 2411 "dk4sto.ctr" return back; } int dk4sto_use_trees(dk4_sto_t *st,int ok) { int back = 0; #if DK4_USE_ASSERT assert(NULL != st); #endif if(st) { if(!(st->r)) { st->t = (ok ? 1 : 0); back = 1; } } return back; } void * dk4sto_find_root(dk4_sto_t const *s) { void *back = NULL; #if DK4_USE_ASSERT assert(NULL != s); #endif if(s) { if(s->r) { back = (s->r)->o; } } return back; } void * dk4sto_it_find_parent(dk4_sto_it_t const *i) { void *back = NULL; #if DK4_USE_ASSERT assert(NULL != i); #endif if(i) { if(i->c) { if((i->c)->p) { back = ((i->c)->p)->o; } } } return back; } void * dk4sto_it_find_left(dk4_sto_it_t const *i) { void *back = NULL; #if DK4_USE_ASSERT assert(NULL != i); #endif if(i) { if(i->c) { if((i->c)->l) { back = ((i->c)->l)->o; } } } return back; } void * dk4sto_it_find_right(dk4_sto_it_t const *i) { void *back = NULL; #if DK4_USE_ASSERT assert(NULL != i); #endif if(i) { if(i->c) { if((i->c)->r) { back = ((i->c)->r)->o; } } } return back; } void * dk4sto_it_find_root(dk4_sto_it_t const *i) { void *back = NULL; #if DK4_USE_ASSERT assert(NULL != i); #endif if(i) { if(i->s) { back = dk4sto_find_root(i->s); } } return back; } /* vim: set ai sw=2 : */