/* 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: dk3sto.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 dk3sto.c The dk3sto module. */ #line 255 "dk3sto.ctr" #include "dk3all.h" #line 261 "dk3sto.ctr" /** Comparison criteria: Do not compare the objects (unsorted storage). */ #define DK3STO_COMPARE_NONE 0 /** Comparison criteria: Use comparison function. */ #define DK3STO_COMPARE_FCT 1 /** Comparison criteria: Evaluate objects to char values. */ #define DK3STO_COMPARE_CHAR 2 /** Comparison criteria: Evaluate objects to unsigned char values. */ #define DK3STO_COMPARE_UCHAR 3 /** Comparison criteria: Evaluate objects to short values. */ #define DK3STO_COMPARE_SHORT 4 /** Comparison criteria: Evaluate objects to unsigned short values. */ #define DK3STO_COMPARE_USHORT 5 /** Comparison criteria: Evaluate objects to int values. */ #define DK3STO_COMPARE_INT 6 /** Comparison criteria: Evaluate objects to unsigned int values. */ #define DK3STO_COMPARE_UINT 7 /** Comparison criteria: Evaluate objects to long values. */ #define DK3STO_COMPARE_LONG 8 /** Comparison criteria: Evaluate objects to unsigned long values. */ #define DK3STO_COMPARE_ULONG 9 /** Comparison criteria: Evaluate objects to float values. */ #define DK3STO_COMPARE_FLOAT 10 /** Comparison criteria: Evaluate objects to double values. */ #define DK3STO_COMPARE_DOUBLE 11 /* 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 dk3sto_node_init_for_object(dk3_sto_node_t *n, void *o, dk3_sto_t *s, int crit) { #line 328 "dk3sto.ctr" n->p = n->l = n->r = NULL; n->b = n->w = 0; n->o = o; switch(s->h) { case DK3STO_COMPARE_CHAR: (n->v).c = (*((s->e).c))(o,crit); break; case DK3STO_COMPARE_UCHAR: (n->v).uc = (*((s->e).uc))(o,crit); break; case DK3STO_COMPARE_SHORT: (n->v).s = (*((s->e).s))(o,crit); break; case DK3STO_COMPARE_USHORT: (n->v).us = (*((s->e).us))(o,crit); break; case DK3STO_COMPARE_INT: (n->v).i = (*((s->e).i))(o,crit); break; case DK3STO_COMPARE_UINT: (n->v).ui = (*((s->e).ui))(o,crit); break; case DK3STO_COMPARE_LONG: (n->v).l = (*((s->e).l))(o,crit); break; case DK3STO_COMPARE_ULONG: (n->v).ul = (*((s->e).ul))(o,crit); break; case DK3STO_COMPARE_FLOAT: (n->v).f = (*((s->e).f))(o,crit); break; case DK3STO_COMPARE_DOUBLE: (n->v).d = (*((s->e).d))(o,crit); break; } #line 343 "dk3sto.ctr" } /** Copy data from one storage node to another. @param d Destination node. @param s Source node. @param st Storage. */ static void dk3sto_node_data_copy(dk3_sto_node_t *d, dk3_sto_node_t *s, dk3_sto_t *st) { #line 356 "dk3sto.ctr" d->o = s->o; switch(st->h) { case DK3STO_COMPARE_CHAR: (d->v).c = (s->v).c ; break; case DK3STO_COMPARE_UCHAR: (d->v).uc = (s->v).uc ; break; case DK3STO_COMPARE_SHORT: (d->v).s = (s->v).s ; break; case DK3STO_COMPARE_USHORT: (d->v).us = (s->v).us ; break; case DK3STO_COMPARE_INT: (d->v).i = (s->v).i ; break; case DK3STO_COMPARE_UINT: (d->v).ui = (s->v).ui ; break; case DK3STO_COMPARE_LONG: (d->v).l = (s->v).l ; break; case DK3STO_COMPARE_ULONG: (d->v).ul = (s->v).ul ; break; case DK3STO_COMPARE_FLOAT: (d->v).f = (s->v).f ; break; case DK3STO_COMPARE_DOUBLE: (d->v).d = (s->v).d ; break; } #line 370 "dk3sto.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 dk3sto_node_compare(dk3_sto_node_t *l, dk3_sto_node_t *r, dk3_sto_t *s, int c) { int back = 0; #line 386 "dk3sto.ctr" switch(s->h) { case DK3STO_COMPARE_FCT: { #line 388 "dk3sto.ctr" back = (*((s->e).comp))((void *)(l->o),(void *)(r->o),c); if(back < 0) back = -1; if(back > 0) back = 1; } break; case DK3STO_COMPARE_CHAR: { #line 393 "dk3sto.ctr" if(((l->v).c) > ((r->v).c)) { back = 1; } else { if(((l->v).c) < ((r->v).c)) { back = -1; } } } break; case DK3STO_COMPARE_UCHAR: { #line 397 "dk3sto.ctr" if(((l->v).uc) > ((r->v).uc)) { back = 1; } else { if(((l->v).uc) < ((r->v).uc)) { back = -1; } } } break; case DK3STO_COMPARE_SHORT: { #line 401 "dk3sto.ctr" if(((l->v).s) > ((r->v).s)) { back = 1; } else { if(((l->v).s) < ((r->v).s)) { back = -1; } } } break; case DK3STO_COMPARE_USHORT: { #line 405 "dk3sto.ctr" if(((l->v).us) > ((r->v).us)) { back = 1; } else { if(((l->v).us) < ((r->v).us)) { back = -1; } } } break; case DK3STO_COMPARE_INT: { #line 409 "dk3sto.ctr" if(((l->v).i) > ((r->v).i)) { back = 1; } else { if(((l->v).i) < ((r->v).i)) { back = -1; } } } break; case DK3STO_COMPARE_UINT: { #line 413 "dk3sto.ctr" if(((l->v).ui) > ((r->v).ui)) { back = 1; } else { if(((l->v).ui) < ((r->v).ui)) { back = -1; } } } break; case DK3STO_COMPARE_LONG: { #line 417 "dk3sto.ctr" if(((l->v).l) > ((r->v).l)) { back = 1; } else { if(((l->v).l) < ((r->v).l)) { back = -1; } } } break; case DK3STO_COMPARE_ULONG: { #line 421 "dk3sto.ctr" if(((l->v).ul) > ((r->v).ul)) { back = 1; } else { if(((l->v).ul) < ((r->v).ul)) { back = -1; } } } break; case DK3STO_COMPARE_FLOAT: { #line 425 "dk3sto.ctr" if(((l->v).f) > ((r->v).f)) { back = 1; } else { if(((l->v).f) < ((r->v).f)) { back = -1; } } } break; case DK3STO_COMPARE_DOUBLE: { #line 429 "dk3sto.ctr" if(((l->v).d) > ((r->v).d)) { back = 1; } else { if(((l->v).d) < ((r->v).d)) { back = -1; } } } break; } #line 433 "dk3sto.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 dk3_sto_node_t * dk3sto_unsorted_remove(dk3_sto_node_t *ro, dk3_sto_node_t *n) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *l = NULL; /* Left element. */ dk3_sto_node_t *r = NULL; /* Right element. */ #line 454 "dk3sto.ctr" back = ro; l = n->l; r = n->r; if(r) { r->l = l; } if(l) { l->r = r; } else { back = r; } #line 464 "dk3sto.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 dk3_sto_node_t * dk3sto_unsorted_add(dk3_sto_node_t *r, dk3_sto_node_t *n) { dk3_sto_node_t *back; #line 479 "dk3sto.ctr" back = n; n->r = r; if(r) { r->l = n; } #line 484 "dk3sto.ctr" return back; } /** Release all nodes in an unsorted storage. @param r Root node. */ static void dk3sto_unsorted_release_all_nodes(dk3_sto_node_t *r) { dk3_sto_node_t *c; /* Current element. */ dk3_sto_node_t *n; /* Next element. */ #line 498 "dk3sto.ctr" c = r; while(c) { n = c->r; c->p = c->l = c->r = NULL; c->o = NULL; c->b = c->w = 0; dk3_delete(c) ; c = n; } #line 508 "dk3sto.ctr" } /** Find next node in an unsorted storage. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk3_sto_node_t * dk3sto_unsorted_find_next_node(dk3_sto_node_t *n, dk3_sto_node_t *r) { dk3_sto_node_t *back = NULL; #line 522 "dk3sto.ctr" if(n) { back = n->r; } else { back = r; } #line 527 "dk3sto.ctr" return back; } /** Find last node in an unsorted storage. @param n Root node. @return Last node or NULL. */ static dk3_sto_node_t * dk3sto_unsorted_find_last_node(dk3_sto_node_t *n) { dk3_sto_node_t *back = NULL; #line 541 "dk3sto.ctr" if(n) back = n->l; #line 543 "dk3sto.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 dk3_sto_node_t * dk3sto_unsorted_find_exact(dk3_sto_node_t *r, void const *o) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *c; /* Current node. */ #line 559 "dk3sto.ctr" c = r; while(c && (!back)) { if((c->o) == o) { back = c; } c = c->r; } #line 566 "dk3sto.ctr" return back; } /* SORTED DATA HANDLING */ /** Go to direction: Left. */ #define DK3STO_WALK_LEFT 1 /** Go to direction: Right. */ #define DK3STO_WALK_RIGHT 2 /** Perform left rotation at node. @param p Subpath to modify. @return New subpath root node or NULL. */ static dk3_sto_node_t * dk3sto_left_rotation(dk3_sto_node_t *p) { dk3_sto_node_t *p1; #line 596 "dk3sto.ctr" p1 = p->r; p->r = p1->l; if(p->r) (p->r)->p = p; p1->l = p; if(p) p->p = p1; #line 602 "dk3sto.ctr" return p1; } /** Perform right rotation at node. @param p Subpath to modify. @return New subpath root node or NULL. */ static dk3_sto_node_t * dk3sto_right_rotation(dk3_sto_node_t *p) { dk3_sto_node_t *p1; #line 616 "dk3sto.ctr" p1 = p->l; p->l = p1->r; if(p->l) (p->l)->p = p; p1->r = p; if(p) p->p = p1; #line 622 "dk3sto.ctr" return p1; } /** Increment balance field of a storage node. @param p Node to modify. */ static void dk3sto_inc_balance(dk3_sto_node_t *p) { short x; /* New balance value. */ #line 635 "dk3sto.ctr" x = p->b; #line 636 "dk3sto.ctr" x++; if(x > 3) x = 0; p->b = x; #line 639 "dk3sto.ctr" } /** Decrement balance field of a storage node. @param p Storage node. */ static void dk3sto_dec_balance(dk3_sto_node_t *p) { short x; /* New balance value. */ #line 651 "dk3sto.ctr" x = p->b; #line 652 "dk3sto.ctr" x--; if(x < 0) x = 3; p->b = x; #line 655 "dk3sto.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 dk3_sto_node_t * dk3sto_left_deleted(dk3_sto_node_t *p, short *h) { #line 669 "dk3sto.ctr" switch(p->b) { case 0: *h = - *h; case 3: #line 673 "dk3sto.ctr" dk3sto_inc_balance(p); #line 675 "dk3sto.ctr" break; case 1: { switch((p->r)->b) { case 0: (p->r)->b = 3; *h = - *h; p = dk3sto_left_rotation(p); break; case 1: (p->r)->b = 0; p->b = 0; p = dk3sto_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 = dk3sto_right_rotation(p->r); if(p->r) (p->r)->p = p; p = dk3sto_left_rotation(p); p->b = 0; } } } #line 699 "dk3sto.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 dk3_sto_node_t * dk3sto_right_deleted(dk3_sto_node_t *p, short *h) { #line 713 "dk3sto.ctr" switch(p->b) { case 0: *h = - *h; case 1: dk3sto_dec_balance(p); break; case 3: { switch((p->l)->b) { case 0: (p->l)->b = 1; *h = - *h; p = dk3sto_right_rotation(p); break; case 3: (p->l)->b = 0; p->b = 0; p = dk3sto_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 = dk3sto_left_rotation(p->l); if(p->l) (p->l)->p = p; p = dk3sto_right_rotation(p); p->b = 0; } } } #line 740 "dk3sto.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 dk3_sto_node_t * dk3sto_avlt_add(dk3_sto_node_t *root, dk3_sto_node_t *newnode, dk3_sto_t *st) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *p = NULL; /* Current node. */ dk3_sto_node_t *q = NULL; /* Father of p. */ dk3_sto_node_t *r = NULL; /* Critical node. */ dk3_sto_node_t *s = NULL; /* Father of r. */ #line 760 "dk3sto.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(dk3sto_node_compare(p,newnode,st,st->c) > 0) { p->w = DK3STO_WALK_LEFT; p = p->l; } else { p->w = DK3STO_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(dk3sto_node_compare(q,newnode,st,st->c) > 0) { q->l = p; q->w = DK3STO_WALK_LEFT; } else { q->r = p; q->w = DK3STO_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 == DK3STO_WALK_LEFT) { dk3sto_dec_balance(p); p = p->l; } else { dk3sto_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 == DK3STO_WALK_LEFT) { if((p->l)->b == 3) { p->b = 0; p = dk3sto_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 = dk3sto_left_rotation(p->l); if(p->l) (p->l)->p = p; p = dk3sto_right_rotation(p); } } else { if((p->r)->b == 1) { p->b = 0; p = dk3sto_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 = dk3sto_right_rotation(p->r); if(p->r) (p->r)->p = p; p = dk3sto_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 == DK3STO_WALK_LEFT) { s->l = p; } else { s->r = p; } if(p) p->p = s; } else { back = p; } } } } if(back) { back->p = NULL; } #line 872 "dk3sto.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 dk3_sto_node_t * dk3sto_avlt_delete( dk3_sto_node_t *root, dk3_sto_node_t *node, dk3_sto_node_t **delpath, dk3_sto_t *st, int *success_indicator, dk3_sto_node_t **toremove ) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *p = NULL; /* Current node. */ dk3_sto_node_t *q = NULL; /* Father of p. */ dk3_sto_node_t *r = NULL; /* Critical node. */ dk3_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 903 "dk3sto.ctr" /* Make sure the node to delete has max. 1 subtree. */ if((todel->l) && (todel->r)) { #line 909 "dk3sto.ctr" todel = todel->l; while(todel->r) todel = todel->r; dk3sto_node_data_copy(node,todel,st); } if(!(todel->p)) { #line 914 "dk3sto.ctr" delroot = 1; } /* Mark the way in the "w" fields. */ *toremove = todel; todel->w = 0; while(todel->p) { if((todel->p)->l == todel) { #line 924 "dk3sto.ctr" (todel->p)->w = DK3STO_WALK_LEFT; } else { #line 927 "dk3sto.ctr" (todel->p)->w = DK3STO_WALK_RIGHT; } todel = todel->p; } p = back; q = r = NULL; x1 = 0; can_continue = 1; while(can_continue) { #line 937 "dk3sto.ctr" #if VERSION_BEFORE_20151002 if(p) { #line 939 "dk3sto.ctr" #endif if(p->w) { #line 941 "dk3sto.ctr" if(p->b == 0) { x1 = 0; #line 943 "dk3sto.ctr" } delpath[x1++] = p; #line 945 "dk3sto.ctr" if(x1 >= st->l) { #line 946 "dk3sto.ctr" /* x1 too large */ *success_indicator = 0; goto error_mark; } if(p->w == DK3STO_WALK_LEFT) { #line 951 "dk3sto.ctr" p = p->l; } else { #line 953 "dk3sto.ctr" p = p->r; } } else { can_continue = 0; #line 957 "dk3sto.ctr" } #if VERSION_BEFORE_20151002 } else { can_continue = 0; #line 961 "dk3sto.ctr" } #endif } #if VERSION_BEFORE_20151002 r = p; #endif /* Static code analysis: Dereference potential NULL pointer p */ /* I think p can not be NULL. */ if(p->l) q = p->l; else q = p->r; if(x1 == 0) { if(delroot) { #line 973 "dk3sto.ctr" back = q; } } while(x1 > 0) { #line 977 "dk3sto.ctr" x1--; p = delpath[x1]; if(p->w == DK3STO_WALK_LEFT) { #line 981 "dk3sto.ctr" p->l = q; if(q) q->p = p; q = dk3sto_left_deleted(p, &x1); #line 984 "dk3sto.ctr" } else { #line 986 "dk3sto.ctr" p->r = q; if(q) q->p = p; q = dk3sto_right_deleted(p, &x1); #line 989 "dk3sto.ctr" } if(x1 == 0) { #line 992 "dk3sto.ctr" if(delpath[x1] == back) { #line 994 "dk3sto.ctr" back = q; } } if(x1 < 0) { #line 998 "dk3sto.ctr" p = delpath[0 - x1 - 1]; if(p->w == DK3STO_WALK_LEFT) { p->l = q; } else { p->r = q; } if(q) q->p = p; } } error_mark: if(back) { back->p = NULL; } #line 1012 "dk3sto.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 dk3_sto_node_t * dk3sto_tree_find_like( dk3_sto_node_t *root, dk3_sto_node_t *testnode, dk3_sto_t *st, int crit, dk3_sto_node_t **cand ) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *c = NULL; /* Current node. */ int testval = 0; /* Comparison result. */ #line 1035 "dk3sto.ctr" c = root; while(c) { testval = dk3sto_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 1051 "dk3sto.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 dk3_sto_node_t * dk3sto_tree_add(dk3_sto_node_t *r, dk3_sto_node_t *n, dk3_sto_t *s) { dk3_sto_node_t *back; back = dk3sto_avlt_add(r,n,s); return back; } /** Release all nodes in a tree storage. @param r Root node. */ static void dk3sto_tree_release_all_nodes(dk3_sto_node_t *r) { #line 1079 "dk3sto.ctr" if(r) { dk3sto_tree_release_all_nodes(r->l); dk3sto_tree_release_all_nodes(r->r); r->l = r->r = r->p = NULL; r->o = NULL; r->b = 0; r->w = 0; dk3_delete(r) ; } #line 1087 "dk3sto.ctr" } /** Find next node in a tree storage. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk3_sto_node_t * dk3sto_tree_find_next_node(dk3_sto_node_t *n, dk3_sto_node_t *r) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *c = NULL; /* Current node. */ dk3_sto_node_t *p = NULL; /* Parent of c. */ #line 1103 "dk3sto.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 1144 "dk3sto.ctr" return back; } /** Find last node in a tree storage. @param n Node to start search from. @return Last node or NULL. */ static dk3_sto_node_t * dk3sto_tree_find_last_node(dk3_sto_node_t *n) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *c; /* Current node. */ dk3_sto_node_t *p; /* Father of c. */ #line 1160 "dk3sto.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 1173 "dk3sto.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 dk3_sto_node_t * dk3sto_tree_find_exact(dk3_sto_node_t *r, void const *o, dk3_sto_t *s) { dk3_sto_node_t *back = NULL; dk3_sto_node_t testnode; /* Test node for comparisons. */ dk3_sto_node_t *c; /* Current node to test. */ dk3_sto_node_t *candidate; /* Candidate for found node. */ int testval = 0; /* Comparison result. */ #line 1193 "dk3sto.ctr" dk3sto_node_init_for_object(&testnode, (void *)o, s, s->c); c = dk3sto_tree_find_like(r, &testnode, s, s->c, &candidate); while(c && (!back)) { testval = dk3sto_node_compare(c, &testnode, s, s->c); if(testval == 0) { if((c->o) == o) { back = c; } else { c = dk3sto_tree_find_next_node(c, r); } } else { c = NULL; } } #line 1207 "dk3sto.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 dk3_sto_node_t * dk3sto_tree_remove( dk3_sto_node_t *ro, dk3_sto_node_t *n, dk3_sto_t *st, int *sci, dk3_sto_node_t **toremove ) { dk3_sto_node_t *back; back = dk3sto_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 dk3_sto_node_t * dk3sto_list_find_like( dk3_sto_node_t *root, dk3_sto_node_t *testnode, dk3_sto_t *st, int crit, dk3_sto_node_t **cand ) { dk3_sto_node_t *back = NULL; dk3_sto_node_t *c = NULL; /* Current node. */ int testval = 0; /* Comparison result. */ #line 1255 "dk3sto.ctr" c = root; while(c && (!back)) { testval = dk3sto_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 1271 "dk3sto.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 dk3_sto_node_t * dk3sto_list_find_exact(dk3_sto_node_t *r, void const *o, dk3_sto_t *s) { dk3_sto_node_t *back; #line 1287 "dk3sto.ctr" back = dk3sto_unsorted_find_exact(r,o); #line 1289 "dk3sto.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 dk3_sto_node_t * dk3sto_list_add(dk3_sto_node_t *r, dk3_sto_node_t *n, dk3_sto_t *s) { dk3_sto_node_t *back; dk3_sto_node_t *larger = NULL; /* Last found larger entry. */ dk3_sto_node_t *current = NULL; /* Current node. */ dk3_sto_node_t *smaller = NULL; /* Last found smaller entry. */ int ende; #line 1309 "dk3sto.ctr" back = r; if(r) { larger = smaller = NULL; current = r; ende = 0; while(!ende) { if(dk3sto_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 1344 "dk3sto.ctr" return back; } /** Release all nodes of a list storage. @param r Root node. */ static void dk3sto_list_release_all_nodes(dk3_sto_node_t *r) { #line 1356 "dk3sto.ctr" dk3sto_unsorted_release_all_nodes(r); #line 1358 "dk3sto.ctr" } /** Find next node. @param n Current node. @param r Root node. @return Pointer to next node or NULL. */ static dk3_sto_node_t * dk3sto_list_find_next_node(dk3_sto_node_t *n, dk3_sto_node_t *r) { dk3_sto_node_t *back; #line 1372 "dk3sto.ctr" back = dk3sto_unsorted_find_next_node(n,r); #line 1374 "dk3sto.ctr" return back; } /** Find last (previous) node. @param n Current node. @return Pointer to previous node or NULL. */ static dk3_sto_node_t * dk3sto_list_find_last_node(dk3_sto_node_t *n) { dk3_sto_node_t *back; #line 1388 "dk3sto.ctr" back = dk3sto_unsorted_find_last_node(n); #line 1390 "dk3sto.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 dk3_sto_node_t * dk3sto_list_remove( dk3_sto_node_t *ro, dk3_sto_node_t *n, dk3_sto_t *st, int *sci, dk3_sto_node_t **toremove ) { dk3_sto_node_t *back; #line 1410 "dk3sto.ctr" back = dk3sto_unsorted_remove(ro,n); #line 1412 "dk3sto.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 dk3_sto_node_t * dk3sto_traverse_iterators_for(void *it, void *o) { dk3_sto_node_t *back = NULL; dk3_sto_it_t *c = NULL; /* Current node. */ #line 1432 "dk3sto.ctr" if(it) { c = (dk3_sto_it_t *)it; while(c && (!back)) { if(c->c) { if(((c->c)->o) == o) { back = c->c; } } if(!back) c = c->r; } } #line 1443 "dk3sto.ctr" return back; } /** Find last storage node. @param n Current storage node. @param st Storage. @return Pointer to last node or NULL. */ static dk3_sto_node_t * dk3sto_find_last_node(dk3_sto_node_t *n, dk3_sto_t *st) { dk3_sto_node_t *back = NULL; #line 1458 "dk3sto.ctr" if(st->h) { if(st->t) { back = dk3sto_tree_find_last_node(n); } else { back = dk3sto_list_find_last_node(n); } } else { back = dk3sto_unsorted_find_last_node(n); } #line 1468 "dk3sto.ctr" return back; } /** Initialize storage. @param st Storage to initialize. @param app Application structure for diagnostics, may be NULL. @return 1 on success, 0 on error. */ static int dk3sto_storage_init(dk3_sto_t *st, dk3_app_t *app) { int back = 0; short l = 0; /* Critical path length. */ #line 1484 "dk3sto.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->app = app; st->d = dk3_new_app(dk3_sto_node_p,l,app); st->t = 1; if(st->d) { back = 1; } #line 1501 "dk3sto.ctr" return back; } /** Close the storage, release memory. @param st Storage to close. */ static void dk3sto_storage_end(dk3_sto_t *st) { #line 1513 "dk3sto.ctr" /* release iterators */ { dk3_sto_it_t *c = NULL; /* Current iterator. */ dk3_sto_it_t *n = NULL; /* Next iterator. */ c = (dk3_sto_it_t *)(st->i); st->i = NULL; while(c) { #line 1521 "dk3sto.ctr" n = c->r; c->r = NULL; c->l = NULL; c->c = NULL; c->s = NULL; dk3_delete(c) ; c = n; } st->i = NULL; } #line 1532 "dk3sto.ctr" /* release nodes */ { if(st->h) { if(st->t) { dk3sto_tree_release_all_nodes(st->r); } else { dk3sto_list_release_all_nodes(st->r); } } else { dk3sto_unsorted_release_all_nodes(st->r); } st->r = NULL; } #line 1546 "dk3sto.ctr" /* release delpath */ { dk3_sto_node_p *p; p = st->d; dk3_delete(p); st->d = NULL; st->l = 0; } #line 1554 "dk3sto.ctr" /* set pointers to NULL */ { st->h = 0; st->c = 0; } #line 1560 "dk3sto.ctr" #line 1561 "dk3sto.ctr" } /* PUBLIC INTERFACES */ dk3_sto_t * dk3sto_open_app(dk3_app_t *app) { dk3_sto_t *back = NULL; #line 1575 "dk3sto.ctr" back = dk3_new_app(dk3_sto_t,1,app) ; if(back) { if(!dk3sto_storage_init(back,app)) { dk3_delete(back); back = NULL; } } #line 1582 "dk3sto.ctr" return back; } void dk3sto_close(dk3_sto_t *st) { #line 1591 "dk3sto.ctr" if(st) { dk3sto_storage_end(st); dk3_delete(st) ; } #line 1595 "dk3sto.ctr" } void dk3sto_remove_all(dk3_sto_t *st) { if(st) { /* reset all iterators */ dk3_sto_it_t *c = NULL; /* Curent iterator. */ dk3_sto_it_t *n = NULL; /* Next iterator. */ c = (dk3_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) { dk3sto_tree_release_all_nodes(st->r); } else { dk3sto_list_release_all_nodes(st->r); } } else { dk3sto_unsorted_release_all_nodes(st->r); } } st->r = NULL; } } int dk3sto_remove(dk3_sto_t *st, void *o) { int back = 0; dk3_sto_node_t *node_to_remove = NULL; /* Node to remove. */ dk3_sto_node_t *ln = NULL; /* Last node. */ dk3_sto_it_t *iterator = NULL; /* Traverse all iterators. */ #line 1638 "dk3sto.ctr" if(st && o) { node_to_remove = dk3sto_traverse_iterators_for(st->i, o); if(!node_to_remove) { if(st->h) { if(st->t) { node_to_remove = dk3sto_tree_find_exact(st->r,o,st); } else { node_to_remove = dk3sto_list_find_exact(st->r,o,st); } } else { node_to_remove = dk3sto_unsorted_find_exact(st->r,o); } } if(node_to_remove) { back = 1; ln = dk3sto_find_last_node(node_to_remove,st); iterator = (dk3_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 = dk3sto_tree_remove(st->r,node_to_remove,st,&back,&node_to_remove); } else { st->r = dk3sto_list_remove(st->r,node_to_remove,st,&back,&node_to_remove); } } else { st->r = dk3sto_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; dk3_delete(node_to_remove); } } #line 1675 "dk3sto.ctr" return back; } int dk3sto_add(dk3_sto_t *st, void *o) { int back = 0; dk3_sto_node_t *n = NULL; /* New node. */ #line 1686 "dk3sto.ctr" if(st && o) { if(st->app) { n = dk3_new_app(dk3_sto_node_t,1,((dk3_app_t *)(st->app))) ; } else { n = dk3_new(dk3_sto_node_t,1); } if(n) { dk3sto_node_init_for_object(n,o,st,st->c); if(st->h) { if(st->t) { st->r = dk3sto_tree_add(st->r, n, st); } else { st->r = dk3sto_list_add(st->r, n, st); } } else { st->r = dk3sto_unsorted_add(st->r, n); } back = 1; } } #line 1706 "dk3sto.ctr" return back; } dk3_sto_it_t * dk3sto_it_open(dk3_sto_t *st) { dk3_sto_it_t *back = NULL; #line 1716 "dk3sto.ctr" if(st) { if(st->app) { back = dk3_new_app(dk3_sto_it_t,1,((dk3_app_t *)(st->app))) ; } else { back = dk3_new(dk3_sto_it_t,1); } if(back) { back->s = st; back->l = NULL; back->r = (dk3_sto_it_t *)(st->i); back->c = NULL; st->i = (void *)back; } } #line 1730 "dk3sto.ctr" return back; } void dk3sto_it_close(dk3_sto_it_t *it) { dk3_sto_it_t *l = NULL; /* Left iterator. */ dk3_sto_it_t *r = NULL; /* Right iterator. */ dk3_sto_t *s = NULL; /* The storage. */ #line 1742 "dk3sto.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; dk3_delete(it) ; } #line 1759 "dk3sto.ctr" } void dk3sto_it_reset(dk3_sto_it_t *it) { #line 1767 "dk3sto.ctr" if(it) { it->c = NULL; } #line 1770 "dk3sto.ctr" } void * dk3sto_it_next(dk3_sto_it_t *it) { void *back = NULL; #line 1779 "dk3sto.ctr" if(it) { if(it->s) { if((it->s)->h) { if((it->s)->t) { it->c = dk3sto_tree_find_next_node(it->c, (it->s)->r); } else { it->c = dk3sto_list_find_next_node(it->c, (it->s)->r); } } else { it->c = dk3sto_unsorted_find_next_node(it->c, (it->s)->r); } if(it->c) { back = (it->c)->o; } } } #line 1795 "dk3sto.ctr" return back; } void * dk3sto_it_find_exact(dk3_sto_it_t *i, void const *o) { void *back = NULL; #line 1805 "dk3sto.ctr" if(i && o) { if(i->s) { if((i->s)->h) { if((i->s)->t) { i->c = dk3sto_tree_find_exact((i->s)->r, o, i->s); } else { i->c = dk3sto_list_find_exact((i->s)->r, o, i->s); } } else { i->c = dk3sto_unsorted_find_exact((i->s)->r, o); } } if(i->c) { back = (i->c)->o; } } #line 1821 "dk3sto.ctr" return back; } void * dk3sto_it_find_like(dk3_sto_it_t *i, void const *o, int cr) { void *back = NULL; dk3_sto_node_t testnode; /* Test node for comparisons. */ dk3_sto_node_t *candidate = NULL; /* Candicate node. */ #line 1833 "dk3sto.ctr" if(i && o) { if(i->s) { candidate = NULL; if((i->s)->h) { dk3sto_node_init_for_object(&testnode, (void *)o, (i->s), cr); if((i->s)->t) { i->c = dk3sto_tree_find_like((i->s)->r, &testnode, i->s, cr, &candidate); } else { i->c = dk3sto_list_find_like((i->s)->r, &testnode, i->s, cr, &candidate); } } else { i->c = dk3sto_unsorted_find_exact((i->s)->r, o); } if(i->c) { back = (i->c)->o; } else { i->c = candidate; } } } #line 1853 "dk3sto.ctr" return back; } int dk3sto_set_eval_c(dk3_sto_t *st, dk3_fct_eval_c_t *f, int cr) { int back = 0; #line 1863 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).c = f; st->c = cr; st->h = DK3STO_COMPARE_CHAR; } } #line 1871 "dk3sto.ctr" return back; } int dk3sto_set_eval_uc(dk3_sto_t *st, dk3_fct_eval_uc_t *f, int cr) { int back = 0; #line 1881 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).uc = f; st->c = cr; st->h = DK3STO_COMPARE_UCHAR; } } #line 1889 "dk3sto.ctr" return back; } int dk3sto_set_eval_s(dk3_sto_t *st, dk3_fct_eval_s_t *f, int cr) { int back = 0; #line 1899 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).s = f; st->c = cr; st->h = DK3STO_COMPARE_SHORT; } } #line 1907 "dk3sto.ctr" return back; } int dk3sto_set_eval_us(dk3_sto_t *st, dk3_fct_eval_us_t *f, int cr) { int back = 0; #line 1917 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).us = f; st->c = cr; st->h = DK3STO_COMPARE_USHORT; } } #line 1925 "dk3sto.ctr" return back; } int dk3sto_set_eval_i(dk3_sto_t *st, dk3_fct_eval_i_t *f, int cr) { int back = 0; #line 1935 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).i = f; st->c = cr; st->h = DK3STO_COMPARE_INT; } } #line 1943 "dk3sto.ctr" return back; } int dk3sto_set_eval_ui(dk3_sto_t *st, dk3_fct_eval_ui_t *f, int cr) { int back = 0; #line 1953 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).ui = f; st->c = cr; st->h = DK3STO_COMPARE_UINT; } } #line 1961 "dk3sto.ctr" return back; } int dk3sto_set_eval_l(dk3_sto_t *st, dk3_fct_eval_l_t *f, int cr) { int back = 0; #line 1971 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).l = f; st->c = cr; st->h = DK3STO_COMPARE_LONG; } } #line 1979 "dk3sto.ctr" return back; } int dk3sto_set_eval_ul(dk3_sto_t *st, dk3_fct_eval_ul_t *f, int cr) { int back = 0; #line 1989 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).ul = f; st->c = cr; st->h = DK3STO_COMPARE_ULONG; } } #line 1997 "dk3sto.ctr" return back; } int dk3sto_set_eval_f(dk3_sto_t *st, dk3_fct_eval_f_t *f, int cr) { int back = 0; #line 2007 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).f = f; st->c = cr; st->h = DK3STO_COMPARE_FLOAT; } } #line 2015 "dk3sto.ctr" return back; } int dk3sto_set_eval_d(dk3_sto_t *st, dk3_fct_eval_d_t *f, int cr) { int back = 0; #line 2025 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).d = f; st->c = cr; st->h = DK3STO_COMPARE_DOUBLE; } } #line 2033 "dk3sto.ctr" return back; } int dk3sto_set_comp(dk3_sto_t *st, dk3_fct_comp_t *f, int cr) { int back = 0; #line 2043 "dk3sto.ctr" if(st) { if(!(st->r)) { back = 1; (st->e).comp = f; st->c = cr; st->h = DK3STO_COMPARE_FCT; } } #line 2051 "dk3sto.ctr" return back; } int dk3sto_use_trees(dk3_sto_t *st,int ok) { int back = 0; if(st) { if(!(st->r)) { st->t = (ok ? 1 : 0); back = 1; } } return back; } void * dk3sto_find_root(dk3_sto_t *s) { void *back = NULL; if(s) { if(s->r) { back = (s->r)->o; } } return back; } void * dk3sto_it_find_parent(dk3_sto_it_t *i) { void *back = NULL; if(i) { if(i->c) { if((i->c)->p) { back = ((i->c)->p)->o; } } } return back; } void * dk3sto_it_find_left(dk3_sto_it_t *i) { void *back = NULL; if(i) { if(i->c) { if((i->c)->l) { back = ((i->c)->l)->o; } } } return back; } void * dk3sto_it_find_right(dk3_sto_it_t *i) { void *back = NULL; if(i) { if(i->c) { if((i->c)->r) { back = ((i->c)->r)->o; } } } return back; } void * dk3sto_it_find_root(dk3_sto_it_t *i) { void *back = NULL; if(i) { if(i->s) { back = dk3sto_find_root(i->s); } } return back; } /* vim: set ai sw=2 : */