/* WARNING: This file was generated by dkct. 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 */ /* Copyright (C) 2011-2017, Dirk Krause Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above opyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of the author nor the names of contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** @file dk4sto.c The dk4sto module. */ #line 451 "dk4sto.ctr" #include "dk4sto.h" #include "dk4mem.h" #if 0 #ifndef STDLIB_H_INCLUDED #include #define STDLIB_H_INCLUDED 1 #endif #endif #line 464 "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 505 "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 520 "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 537 "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 551 "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 573 "dk4sto.ctr" switch(s->h) { case DK4STO_COMPARE_FCT: { #line 575 "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 580 "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 584 "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 588 "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 592 "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 596 "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 600 "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 604 "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 608 "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 612 "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 616 "dk4sto.ctr" if(((l->v).d) > ((r->v).d)) { back = 1; } else { if(((l->v).d) < ((r->v).d)) { back = -1; } } } break; } #line 620 "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 641 "dk4sto.ctr" back = ro; l = n->l; r = n->r; if(r) { r->l = l; } if(l) { l->r = r; } else { back = r; } #line 651 "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 666 "dk4sto.ctr" back = n; n->r = r; if(r) { r->l = n; } #line 671 "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 685 "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 695 "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 710 "dk4sto.ctr" if(n) { back = n->r; } else { back = r; } #line 715 "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 729 "dk4sto.ctr" if(n) back = n->l; #line 731 "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 747 "dk4sto.ctr" c = r; while(c && (!back)) { if((c->o) == o) { back = c; } c = c->r; } #line 754 "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 783 "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 789 "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 803 "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 809 "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 822 "dk4sto.ctr" x = p->b; #line 823 "dk4sto.ctr" x++; if(x > 3) x = 0; p->b = x; #line 826 "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 838 "dk4sto.ctr" x = p->b; #line 839 "dk4sto.ctr" x--; if(x < 0) x = 3; p->b = x; #line 842 "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 856 "dk4sto.ctr" switch(p->b) { case 0: *h = - *h; case 3: #line 860 "dk4sto.ctr" dk4sto_inc_balance(p); #line 862 "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 886 "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 900 "dk4sto.ctr" switch(p->b) { case 0: *h = - *h; 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 927 "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 948 "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) { 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; } } p = newnode; if(!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; } /* Now we must balance the tree again if necessary. */ p->p = q; 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 { 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 { 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 1060 "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. */ short x1 = 0; /* Balance value. */ short delroot = 0; /* Flag: Delete tree node. */ int can_continue = 1; /* Flag: Can continue. */ back = root; todel = node; #line 1091 "dk4sto.ctr" /* Make sure the node to delete has max. 1 subtree. */ if((todel->l) && (todel->r)) { #line 1097 "dk4sto.ctr" todel = todel->l; while(todel->r) todel = todel->r; dk4sto_node_data_copy(node,todel,st); } if(!(todel->p)) { #line 1102 "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 1112 "dk4sto.ctr" (todel->p)->w = DK4STO_WALK_LEFT; } else { #line 1115 "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 1125 "dk4sto.ctr" #if VERSION_BEFORE_20150821 if(p) { #line 1127 "dk4sto.ctr" #endif if(p->w) { #line 1129 "dk4sto.ctr" if(p->b == 0) { x1 = 0; #line 1131 "dk4sto.ctr" } delpath[x1++] = p; #line 1133 "dk4sto.ctr" if(x1 >= st->l) { #line 1134 "dk4sto.ctr" /* x1 too large */ *success_indicator = 0; goto error_mark; } if(p->w == DK4STO_WALK_LEFT) { #line 1139 "dk4sto.ctr" p = p->l; } else { #line 1141 "dk4sto.ctr" p = p->r; } } else { can_continue = 0; #line 1145 "dk4sto.ctr" } #if VERSION_BEFORE_20150821 } else { can_continue = 0; #line 1149 "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 1162 "dk4sto.ctr" back = q; } } while(x1 > 0) { #line 1166 "dk4sto.ctr" x1--; p = delpath[x1]; if(p->w == DK4STO_WALK_LEFT) { #line 1170 "dk4sto.ctr" p->l = q; if(q) q->p = p; q = dk4sto_left_deleted(p, &x1); #line 1173 "dk4sto.ctr" } else { #line 1175 "dk4sto.ctr" p->r = q; if(q) q->p = p; q = dk4sto_right_deleted(p, &x1); #line 1178 "dk4sto.ctr" } if(x1 == 0) { #line 1181 "dk4sto.ctr" if(delpath[x1] == back) { #line 1183 "dk4sto.ctr" back = q; } } if(x1 < 0) { #line 1187 "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 1201 "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 1225 "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 1241 "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 1269 "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 1277 "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 1293 "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 1334 "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 1350 "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 1363 "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 1383 "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 1397 "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 1445 "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 1461 "dk4sto.ctr" return back; } /** Find node for an object (exact search). @param r Root node. @param o Object. @param s Storage. @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_t *s) { dk4_sto_node_t *back; #line 1477 "dk4sto.ctr" back = dk4sto_unsorted_find_exact(r,o); #line 1479 "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 1499 "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 1534 "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 1546 "dk4sto.ctr" dk4sto_unsorted_release_all_nodes(r); #line 1548 "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 1562 "dk4sto.ctr" back = dk4sto_unsorted_find_next_node(n,r); #line 1564 "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 1578 "dk4sto.ctr" back = dk4sto_unsorted_find_last_node(n); #line 1580 "dk4sto.ctr" return back; } /** Remove storage node from list storage. @param ro Root node. @param n Node to remove. @param st Storage. @param sci ??? @param toremove ??? */ static dk4_sto_node_t * dk4sto_list_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; #line 1600 "dk4sto.ctr" back = dk4sto_unsorted_remove(ro,n); #line 1602 "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 1622 "dk4sto.ctr" 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 1633 "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 1648 "dk4sto.ctr" 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 1658 "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 1674 "dk4sto.ctr" /* 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 1690 "dk4sto.ctr" return back; } /** Close the storage, release memory. @param st Storage to close. */ static void dk4sto_storage_end(dk4_sto_t *st) { #line 1702 "dk4sto.ctr" /* 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 1710 "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 1721 "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 1735 "dk4sto.ctr" /* release delpath */ { dk4_sto_node_p *p; p = st->d; dk4mem_free(p); st->d = NULL; st->l = 0; } #line 1743 "dk4sto.ctr" /* set pointers to NULL */ { st->h = 0; st->c = 0; } #line 1749 "dk4sto.ctr" #line 1750 "dk4sto.ctr" } /* PUBLIC INTERFACES */ dk4_sto_t * dk4sto_open(dk4_er_t *erp) { dk4_sto_t *back = NULL; #line 1764 "dk4sto.ctr" back = dk4mem_new(dk4_sto_t,1,erp) ; if(back) { if(!dk4sto_storage_init(back,erp)) { dk4mem_free(back); back = NULL; } } #line 1771 "dk4sto.ctr" return back; } void dk4sto_close(dk4_sto_t *st) { #line 1780 "dk4sto.ctr" if(st) { dk4sto_storage_end(st); dk4mem_free(st) ; } #line 1784 "dk4sto.ctr" } void dk4sto_remove_all(dk4_sto_t *st) { 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 1827 "dk4sto.ctr" if(st && 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,st); } } 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,st,&back,&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 1870 "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 1881 "dk4sto.ctr" if(st && 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 1899 "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 1909 "dk4sto.ctr" 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 1921 "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 1933 "dk4sto.ctr" 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 1950 "dk4sto.ctr" } void dk4sto_it_reset(dk4_sto_it_t *it) { #line 1958 "dk4sto.ctr" if(it) { it->c = NULL; } #line 1961 "dk4sto.ctr" } void * dk4sto_it_next(dk4_sto_it_t *it) { void *back = NULL; #line 1970 "dk4sto.ctr" 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 1986 "dk4sto.ctr" return back; } void * dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o) { void *back = NULL; #line 1996 "dk4sto.ctr" if(i && 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, i->s); } } else { i->c = dk4sto_unsorted_find_exact((i->s)->r, o); } } if(i->c) { back = (i->c)->o; } } #line 2012 "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 2024 "dk4sto.ctr" if(i && 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 2046 "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 2056 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).c = f; st->c = cr; st->h = DK4STO_COMPARE_CHAR; } } #line 2064 "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 2074 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).uc = f; st->c = cr; st->h = DK4STO_COMPARE_UCHAR; } } #line 2082 "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 2092 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).s = f; st->c = cr; st->h = DK4STO_COMPARE_SHORT; } } #line 2100 "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 2110 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).us = f; st->c = cr; st->h = DK4STO_COMPARE_USHORT; } } #line 2118 "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 2128 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).i = f; st->c = cr; st->h = DK4STO_COMPARE_INT; } } #line 2136 "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 2146 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).ui = f; st->c = cr; st->h = DK4STO_COMPARE_UINT; } } #line 2154 "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 2164 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).l = f; st->c = cr; st->h = DK4STO_COMPARE_LONG; } } #line 2172 "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 2182 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).ul = f; st->c = cr; st->h = DK4STO_COMPARE_ULONG; } } #line 2190 "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 2200 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).f = f; st->c = cr; st->h = DK4STO_COMPARE_FLOAT; } } #line 2208 "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 2218 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).d = f; st->c = cr; st->h = DK4STO_COMPARE_DOUBLE; } } #line 2226 "dk4sto.ctr" return back; } int dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr) { int back = 0; #line 2236 "dk4sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).comp = f; st->c = cr; st->h = DK4STO_COMPARE_FCT; } } #line 2244 "dk4sto.ctr" return back; } int dk4sto_use_trees(dk4_sto_t *st,int ok) { int back = 0; if(st) { if(!(st->r)) { st->t = (ok ? 1 : 0); back = 1; } } return back; } void * dk4sto_find_root(dk4_sto_t *s) { void *back = NULL; if(s) { if(s->r) { back = (s->r)->o; } } return back; } void * dk4sto_it_find_parent(dk4_sto_it_t *i) { void *back = NULL; 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 *i) { void *back = NULL; 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 *i) { void *back = NULL; 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 *i) { void *back = NULL; if(i) { if(i->s) { back = dk4sto_find_root(i->s); } } return back; } /* vim: set ai sw=2 : */