%% options copyright owner = Dirk Krause copyright year = 2011-xxxx license = bsd %% header /** @file Sorted and unsorted data storage in AVL trees or double linked lists. CRT on Windows: Optional. */ #ifndef DK4CONF_H_INCLUDED #include "dk4conf.h" #endif #ifndef DK4TYPES_H_INCLUDED #include "dk4types.h" #endif #ifndef DK4ERROR_H_INCLUDED #include "dk4error.h" #endif /** Evaluation result for an object. */ typedef union { double d; /**< Evaluation to double. */ float f; /**< Evaluation to float. */ long l; /**< Evaluation to long. */ unsigned long ul; /**< Evaluation to unsigned long. */ int i; /**< Evaluation to int. */ unsigned int ui; /**< Evaluation to unsigned int. */ short s; /**< Evaluation to short. */ unsigned short us; /**< Evaluation to unsigned short. */ char c; /**< Evaluation to char. */ unsigned char uc; /**< Evaluation to unsigned char. */ } dk4_object_eval_res_t; /** Internal node for dk4_sto_t. This structure is used internally by the dksto module. */ struct dk4__sto__node { dk4_object_eval_res_t v; /**< Object evaluation of @a o. */ struct dk4__sto__node *p; /**< Parent node in tree. */ struct dk4__sto__node *l; /**< Left child (tree) or neighbour (list). */ struct dk4__sto__node *r; /**< Right child (tree) or neighbour (list). */ void *o; /**< Object to store. */ short b; /**< Balance flag (used in tree only). */ short w; /**< Direction to walk. */ }; /** Internal node for dk4_sto_t. */ typedef struct dk4__sto__node dk4_sto_node_t; /** Pointer to internal node for dk4_sto_t. */ typedef dk4_sto_node_t *dk4_sto_node_p; /** Evaluation functions. These function type are used to evaluate and compare objects stored in a sorted dk4_sto_t. */ /** Object evaluation function for sorted storage. */ typedef char dk4_fct_eval_c_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef unsigned char dk4_fct_eval_uc_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef short dk4_fct_eval_s_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef unsigned short dk4_fct_eval_us_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef int dk4_fct_eval_i_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef unsigned int dk4_fct_eval_ui_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef long dk4_fct_eval_l_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef unsigned long dk4_fct_eval_ul_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef float dk4_fct_eval_f_t(void const *obj, int crit); /** Object evaluation function for sorted storage. */ typedef double dk4_fct_eval_d_t(void const *obj, int crit); /** Object comparison function for sorted storage. When comparing to objects while inserting a new object into a storage both @a o1 and @a o2 are object pointers. When this function is called from dk4sto_it_find_like() the @a o1 argument is an object pointer from the storage, @a o2 is the pointer passed to dk4sto_it_find_like(). */ typedef int dk4_fct_comp_t(void const *o1, void const *o2, int crit); /** Choice for object evaluation function. */ typedef union { dk4_fct_eval_c_t *c; /**< Evaluate to char. */ dk4_fct_eval_uc_t *uc; /**< Evaluate to unsigned char. */ dk4_fct_eval_s_t *s; /**< Evaluate to short. */ dk4_fct_eval_us_t *us; /**< Evaluate to unsigned short. */ dk4_fct_eval_i_t *i; /**< Evaluate to int. */ dk4_fct_eval_ui_t *ui; /**< Evaluate to unsigned int. */ dk4_fct_eval_l_t *l; /**< Evaluate to long. */ dk4_fct_eval_ul_t*ul; /**< Evaluate to unsigned long. */ dk4_fct_eval_f_t *f; /**< Evaluate to float. */ dk4_fct_eval_d_t *d; /**< Evaluate to double. */ dk4_fct_comp_t *comp; /**< Compare two objects. */ } dk4_object_eval_fct_t; /** Object storage. A storage can be used to store pointers to objects. */ typedef struct dk4__sto__t { dk4_object_eval_fct_t e; /**< Comparison or evaluation function. */ dk4_sto_node_p *d; /**< Critical path for delete operations. */ dk4_sto_node_t *r; /**< Tree root or start of list. */ void *i; /**< Double-linked list of iterators. */ int h; /**< Selection for comparison or evaluation. */ int c; /**< Comparison or evaluation criteria. */ int t; /**< Flag: Use tree, 1=tree, 0=list. */ short l; /**< Path length of critical path. */ } dk4_sto_t; /** Storage iterator. This structure can be used to iterate through a dk4_sto_t. */ struct dk4__sto__iterator { struct dk4__sto__iterator *l; /**< Left neighbour (preceeding iterator). */ struct dk4__sto__iterator *r; /**< Right neighbour (following iterator). */ dk4_sto_t *s; /**< Owner storage. */ dk4_sto_node_t *c; /**< Current node, current position. */ }; /** Storage iterator. Can be used to iterate through a dk4_sto_t. */ typedef struct dk4__sto__iterator dk4_sto_it_t; #ifdef __cplusplus extern "C" { #endif /** Create new storage. @param erp Error report, may be NULL. @return Pointer to new storage on succcess, NULL on error. Use dk4sto_close() to destroy the storage when done with it. Error codes: - DK4_E_INVALID_ARGUMENTS
if elsize or nelem is 0, - DK4_E_MATH_OVERFLOW
on numeric overflow when calculating the product of elsize and nelem, - DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem set if there is not enough memory available. */ dk4_sto_t * dk4sto_open(dk4_er_t *erp); /** Destroy storage, release memory. @param st Storage to destroy. */ void dk4sto_close(dk4_sto_t *st); /** Remove all pointers from a storage. @param st Storage. */ void dk4sto_remove_all(dk4_sto_t *st); /** Remove one pointer from storage. @param st Storage. @param o Object pointer to remove. @param erp Error report, may be NULL. @return 1 on success, 0 on error (not found). Error codes: - DK4_E_INVALID_ARGUMENTS
if st or o is NULL, - DK4_E_NOT_FOUND if o was not found in st. */ int dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp); /** Add object pointer to storage. @param st Storage. @param o Object pointer to add. @param erp Error report, may be NULL. @return 1 on success, 0 on error (not enough memory). Error codes: - DK4_E_INVALID_ARGUMENTS
if st or os is NULL, - DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem set if there is not enough memory available. */ int dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp); /** Create iterator for storage. @param st Storage. @param erp Error report, may be NULL. @return Pointer to new iterator on success, NULL on error. Use dk4sto_it_close() to destroy the iterator when done with it. When closing/destroying a storage all iterators for that storage are destroyed automatically. Error codes: - DK4_E_INVALID_ARGUMENTS
if st is NULL, - DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem set if there is not enough memory available. */ dk4_sto_it_t * dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp); /** Destroy iterator. @param it Iterator to destroy. */ void dk4sto_it_close(dk4_sto_it_t *it); /** Reset iterator (next call to dk4sto_it_next() will return the first object pointer. @param it Iterator. */ void dk4sto_it_reset(dk4_sto_it_t *it); /** Return next object pointer. @param it Iterator. @return Pointer to next object on success, NULL on error (no more pointers available). */ void * dk4sto_it_next(dk4_sto_it_t *it); /** Find a pointer exactly. @param i Iterator. @param o Object pointer. @return Object pointer on success, NULL on error (object not found). The next calls to dk4sto_it_next() will return pointers to objects after the specified object \a o. */ void * dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o); /** Find object pointer for object evaluating equally to \a o. @param i Iterator. @param o Object pointer. @param cr Comparison criteria. @return Object pointer on success, NULL on error (no such object). */ void * dk4sto_it_find_like(dk4_sto_it_t *i, void const *o, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to a char. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to an unsigned char. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to a short. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to an unsigned short. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to an int. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to an unsigned int. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to a long. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to an unsigned long. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to a float. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr); /** Set evaluation function. @param st Storage. @param f Function evaluating a pointer to a double. @param cr Evaluation criteria. @return 1 on success, 0 on error. */ int dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr); /** Set comparison function. @param st Storage. @param f Function comparing two object pointers. @param cr Comparison criteria. @return 1 on success, 0 on error. */ int dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr); /** Allow use of tree structures. This function must be called before adding any data. @param st Storage. @param ok Flag: Trees may be used. @return 1 on success, 0 on error. */ int dk4sto_use_trees(dk4_sto_t *st,int ok); /** Find object pointer at the trees root. @param s Storage. */ void * dk4sto_find_root(dk4_sto_t *s); /** Find object pointer for the parent node of the last found object. @param i Iterator. @return Object pointer on success, NULL on error. */ void * dk4sto_it_find_parent(dk4_sto_it_t *i); /** Find object pointer for node on left child of the last found object. @param i Iterator. @return Object pointer on success, NULL on error. */ void * dk4sto_it_find_left(dk4_sto_it_t *i); /** Find object pointer for node on right child of the last found object. @param i Iterator. @return Object pointer on success, NULL on error. */ void * dk4sto_it_find_right(dk4_sto_it_t *i); /** Find object pointer at the trees root. @param i Iterator. */ void * dk4sto_it_find_root(dk4_sto_it_t *i); #ifdef __cplusplus } #endif %% module #include "dk4sto.h" #include "dk4mem.h" #if 0 #ifndef STDLIB_H_INCLUDED #include #define STDLIB_H_INCLUDED 1 #endif #endif $(trace-include) /** 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 ) { $? "+ dk4sto_node_init_for_object PTR=%d PTR=%d PTR=%d %d", TR_IPTR(n), TR_IPTR(o), TR_IPTR(s), crit 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; } $? "- dk4sto_node_init_for_object" } /** 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 ) { $? "+ dk4sto_node_data_copy PTR=%d PTR=%d", TR_IPTR(d), TR_IPTR(s) 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; } $? "- dk4sto_node_data_copy" } /** 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; $? "+ dk4sto_node_compare PTR=%d PTR=%d PTR=%d %d", TR_IPTR(l), TR_IPTR(r), TR_IPTR(s), c switch(s->h) { case DK4STO_COMPARE_FCT: { $? ". compare by function" 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: { $? ". compare character" if(((l->v).c) > ((r->v).c)) { back = 1; } else { if(((l->v).c) < ((r->v).c)) { back = -1; } } } break; case DK4STO_COMPARE_UCHAR: { $? ". compare unsigned character" if(((l->v).uc) > ((r->v).uc)) { back = 1; } else { if(((l->v).uc) < ((r->v).uc)) { back = -1; } } } break; case DK4STO_COMPARE_SHORT: { $? ". compare short" if(((l->v).s) > ((r->v).s)) { back = 1; } else { if(((l->v).s) < ((r->v).s)) { back = -1; } } } break; case DK4STO_COMPARE_USHORT: { $? ". compare unsigned short" if(((l->v).us) > ((r->v).us)) { back = 1; } else { if(((l->v).us) < ((r->v).us)) { back = -1; } } } break; case DK4STO_COMPARE_INT: { $? ". compare int" if(((l->v).i) > ((r->v).i)) { back = 1; } else { if(((l->v).i) < ((r->v).i)) { back = -1; } } } break; case DK4STO_COMPARE_UINT: { $? ". compare unsigned int" if(((l->v).ui) > ((r->v).ui)) { back = 1; } else { if(((l->v).ui) < ((r->v).ui)) { back = -1; } } } break; case DK4STO_COMPARE_LONG: { $? ". compare long" if(((l->v).l) > ((r->v).l)) { back = 1; } else { if(((l->v).l) < ((r->v).l)) { back = -1; } } } break; case DK4STO_COMPARE_ULONG: { $? ". compare unsigned long" if(((l->v).ul) > ((r->v).ul)) { back = 1; } else { if(((l->v).ul) < ((r->v).ul)) { back = -1; } } } break; case DK4STO_COMPARE_FLOAT: { $? ". compare float" if(((l->v).f) > ((r->v).f)) { back = 1; } else { if(((l->v).f) < ((r->v).f)) { back = -1; } } } break; case DK4STO_COMPARE_DOUBLE: { $? ". compare double" if(((l->v).d) > ((r->v).d)) { back = 1; } else { if(((l->v).d) < ((r->v).d)) { back = -1; } } } break; } $? "- dk4sto_node_compare %d", back 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. */ $? "+ dk4sto_unsorted_remove PTR=%d PTR=%d", TR_IPTR(ro), TR_IPTR(n) back = ro; l = n->l; r = n->r; if(r) { r->l = l; } if(l) { l->r = r; } else { back = r; } $? "- dk4sto_unsorted_remove PTR=%d", TR_IPTR(back) 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; $? "+ dk4sto_unsorted_add PTR=%d PTR=%d", TR_IPTR(r), TR_IPTR(n) back = n; n->r = r; if(r) { r->l = n; } $? "- dk4sto_unsorted_add PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_unsorted_release_all_nodes PTR=%d", TR_IPTR(r) 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; } $? "- dk4sto_unsorted_release_all_nodes" } /** 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; $? "+ dk4sto_unsorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(r) if(n) { back = n->r; } else { back = r; } $? "- dk4sto_unsorted_find_next_node PTR=%d", TR_IPTR(back) 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; $? "+ dk4sto_unsorted_find_last_node PTR=%d", TR_IPTR(n) if(n) back = n->l; $? "- dk4sto_unsorted_find_last_node PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_unsorted_find_exact PTR=%d PTR=%d", TR_IPTR(r), TR_IPTR(o) c = r; while(c && (!back)) { if((c->o) == o) { back = c; } c = c->r; } $? "- dk4sto_unsorted_find_exact PTR=%d", TR_IPTR(back) 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; $? "+ dk4sto_left_rotation PTR=%d", TR_IPTR(p) p1 = p->r; p->r = p1->l; if(p->r) (p->r)->p = p; p1->l = p; if(p) p->p = p1; $? "- dk4sto_left_rotation PTR=%d", TR_IPTR(p1) 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; $? "+ dk4sto_right_rotation PTR=%d", TR_IPTR(p) p1 = p->l; p->l = p1->r; if(p->l) (p->l)->p = p; p1->r = p; if(p) p->p = p1; $? "- dk4sto_right_rotation PTR=%d", TR_IPTR(p1) 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. */ $? "+ dk4sto_inc_balance PTR=%d", TR_IPTR(p) x = p->b; $? ". old balance %d", x x++; if(x > 3) x = 0; p->b = x; $? "- dk4sto_inc_balance %d", p->b } /** 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. */ $? "+ dk4sto_dec_balance PTR=%d", TR_IPTR(p) x = p->b; $? ". old balance %d", x x--; if(x < 0) x = 3; p->b = x; $? "- dk4sto_dec_balance %d", p->b } /** 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) { $? "+ dk4sto_left_deleted PTR=%d PTR=%d", TR_IPTR(p), TR_IPTR(h) switch(p->b) { case 0: *h = - *h; case 3: $? ". going to increment balance field of PTR=%d", TR_IPTR(p) dk4sto_inc_balance(p); $? ". balance field incremented" 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; } } } $? "- dk4sto_left_deleted PTR=%d", TR_IPTR(p) 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) { $? "+ dk4sto_right_deleted PTR=%d PTR=%d", TR_IPTR(p), TR_IPTR(h) 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; } } } $? "- dk4sto_right_deleted PTR=%d", TR_IPTR(p) 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. */ $? "+ dk4sto_avlt_add PTR=%d PTR=%d PTR=%d", TR_IPTR(root), TR_IPTR(newnode), TR_IPTR(st) 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; } $? "- dk4sto_avlt_add PTR=%d", TR_IPTR(back) 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; $? "+ dk4sto_avlt_delete PTRS=%d %d %d %d %d", TR_IPTR(root), TR_IPTR(node), TR_IPTR(delpath), TR_IPTR(st), TR_IPTR(success_indicator) /* Make sure the node to delete has max. 1 subtree. */ if((todel->l) && (todel->r)) { $? ". finding another node to delete" todel = todel->l; while(todel->r) todel = todel->r; dk4sto_node_data_copy(node,todel,st); } if(!(todel->p)) { $? ". deleting the root node" delroot = 1; } /* Mark the way in the "w" fields. */ *toremove = todel; todel->w = 0; while(todel->p) { if((todel->p)->l == todel) { $? ". walk left" (todel->p)->w = DK4STO_WALK_LEFT; } else { $? ". walk right" (todel->p)->w = DK4STO_WALK_RIGHT; } todel = todel->p; } p = back; q = r = NULL; x1 = 0; can_continue = 1; while(can_continue) { $? ". new while loop 1 %d", x1 #if VERSION_BEFORE_20150821 if(p) { $? ". have current node" #endif if(p->w) { $? ". not final node" if(p->b == 0) { x1 = 0; $? ". current node is balanced" } delpath[x1++] = p; $? ". adding current node to delpath %d", (x1 - 1) if(x1 >= st->l) { $? ". x1 out of range" /* x1 too large */ *success_indicator = 0; goto error_mark; } if(p->w == DK4STO_WALK_LEFT) { $? ". going down left" p = p->l; } else { $? ". going down right" p = p->r; } } else { can_continue = 0; $? ". we are at the final point" } #if VERSION_BEFORE_20150821 } else { can_continue = 0; $? ". no more nodes to visit" } #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) { $? ". setting new root node" back = q; } } while(x1 > 0) { $? ". begin of while loop 2 %d", (x1 - 1) x1--; p = delpath[x1]; if(p->w == DK4STO_WALK_LEFT) { $? ". going to left" p->l = q; if(q) q->p = p; q = dk4sto_left_deleted(p, &x1); $? ". after dk4sto_left_deleted" } else { $? ". going to right" p->r = q; if(q) q->p = p; q = dk4sto_right_deleted(p, &x1); $? ". after dk4sto_right_deleted" } if(x1 == 0) { $? ". final node" if(delpath[x1] == back) { $? ". setting new root node" back = q; } } if(x1 < 0) { $? ". finished" 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; } $? "- dk4sto_avlt_delete PTR=%d", TR_IPTR(back) 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. */ $? "+ sorted_find_like PTR=%d PTR=%d PTR=%d %d", TR_IPTR(root), TR_IPTR(testnode), TR_IPTR(st), crit 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; } } $? "- sorted_find_like PTR=%d", TR_IPTR(back) 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) { $? "+ sorted_release_all_nodes PTR=%d", TR_IPTR(r) 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) ; } $? "- sorted_release_all_nodes" } /** 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. */ $? "+ sorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(r) /* 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; } } $? "- sorted_find_next_node PTR=%d", TR_IPTR(back) 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. */ $? "+ sorted_find_last_node PTR=%d", TR_IPTR(n) 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; } } } $? "- sorted_find_last_node PTR=%d", TR_IPTR(back) 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. */ $? "+ sorted_find_exact PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(o), TR_IPTR(s) 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; } } $? "- sorted_find_exact PTR=%d", TR_IPTR(back) 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. */ $? "+ sorted_find_like PTR=%d PTR=%d PTR=%d %d", TR_IPTR(root), TR_IPTR(testnode), TR_IPTR(st), crit 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; } } $? "- sorted_find_like PTR=%d", TR_IPTR(back) 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; $? "+ sorted_find_exact PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(o), TR_IPTR(s) back = dk4sto_unsorted_find_exact(r,o); $? "- sorted_find_exact PTR=%d", TR_IPTR(back) 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; $? "+ sorted_add PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(n), TR_IPTR(s) 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; } $? "- sorted_add PTR=%d", TR_IPTR(back) 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) { $? "+ sorted_release_all_nodes" dk4sto_unsorted_release_all_nodes(r); $? "- sorted_release_all_nodes" } /** 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; $? "+ sorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(r) back = dk4sto_unsorted_find_next_node(n,r); $? "- sorted_find_next_node PTR=%d", TR_IPTR(back) 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; $? "+ sorted_find_last_node PTR=%d", TR_IPTR(n) back = dk4sto_unsorted_find_last_node(n); $? "- sorted_find_last_node PTR=%d", TR_IPTR(back) 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; $? "+ sorted_remove PTRS= %d %d %d", TR_IPTR(ro), TR_IPTR(n), TR_IPTR(st) back = dk4sto_unsorted_remove(ro,n); $? "- sorted_remove PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_traverse_iterators_for PTR=%d PTR=%d", TR_IPTR(it), TR_IPTR(o) 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; } } $? "- dk4sto_traverse_iterators_for PTR=%d", TR_IPTR(back) 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; $? "+ dk4sto_find_last_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(st) 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); } $? "- dk4sto_find_last_node PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_storage_init PTR=%d", TR_IPTR(st) /* 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; } $? "- dk4sto_storage_init %d", back return back; } /** Close the storage, release memory. @param st Storage to close. */ static void dk4sto_storage_end(dk4_sto_t *st) { $? "+ dk4sto_storage_end PTR=%d", TR_IPTR(st) /* 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) { $? ". going to release iterator PTR=%d", TR_IPTR(c) n = c->r; c->r = NULL; c->l = NULL; c->c = NULL; c->s = NULL; dk4mem_free(c) ; c = n; } st->i = NULL; } $? ". iterators released" /* 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; } $? ". nodes released" /* release delpath */ { dk4_sto_node_p *p; p = st->d; dk4mem_free(p); st->d = NULL; st->l = 0; } $? ". delpath released" /* set pointers to NULL */ { st->h = 0; st->c = 0; } $? ". function pointers resetted" $? "- dk4sto_storage_end" } /* PUBLIC INTERFACES */ dk4_sto_t * dk4sto_open(dk4_er_t *erp) { dk4_sto_t *back = NULL; $? "+ dk4sto_open" back = dk4mem_new(dk4_sto_t,1,erp) ; if(back) { if(!dk4sto_storage_init(back,erp)) { dk4mem_free(back); back = NULL; } } $? "- dk4sto_open PTR=%d", TR_IPTR(back) return back; } void dk4sto_close(dk4_sto_t *st) { $? "+ dk4sto_close PTR=%d", TR_IPTR(st) if(st) { dk4sto_storage_end(st); dk4mem_free(st) ; } $? "- dk4sto_close" } 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. */ $? "+ dk4sto_remove PTR=%d PTR=%d", TR_IPTR(st), TR_IPTR(o) 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); } $? "- dk4sto_remove %d", back 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. */ $? "+ dk4sto_add st=PTR:%d o=PTR:%d", TR_IPTR(st), TR_IPTR(o) 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); } $? "- dk4sto_add %d", back return back; } dk4_sto_it_t * dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp) { dk4_sto_it_t *back = NULL; $? "+ dk4sto_it_open PTR=%d", TR_IPTR(st) 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); }$? "- dk4sto_it_open PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_it_close PTR=%d", TR_IPTR(it) 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) ; } $? "- dk4sto_it_close" } void dk4sto_it_reset(dk4_sto_it_t *it) { $? "+ dk4sto_it_reset PTR=%d", TR_IPTR(it) if(it) { it->c = NULL; } $? "- dk4sto_it_reset" } void * dk4sto_it_next(dk4_sto_it_t *it) { void *back = NULL; $? "+ dk4sto_it_next PTR=%d", TR_IPTR(it) 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; } } } $? "- dk4sto_it_next PTR=%d", TR_IPTR(back) return back; } void * dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o) { void *back = NULL; $? "+ dk4sto_it_find_exact i=PTR:%d o=PTR:%d", TR_IPTR(i), TR_IPTR(o) 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; } } $? "- dk4sto_it_find_exact PTR=%d", TR_IPTR(back) 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. */ $? "+ dk4sto_it_find_like i=PTR:%d o=PTR:%d %d", TR_IPTR(i), TR_IPTR(o), cr 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; } } } $? "- dk4sto_it_find_like PTR=%d", TR_IPTR(back) return back; } int dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_c st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).c = f; st->c = cr; st->h = DK4STO_COMPARE_CHAR; } } $? "- dk4sto_set_eval_c %d", back return back; } int dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_uc st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).uc = f; st->c = cr; st->h = DK4STO_COMPARE_UCHAR; } } $? "- dk4sto_set_eval_uc %d", back return back; } int dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_s st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).s = f; st->c = cr; st->h = DK4STO_COMPARE_SHORT; } } $? "- dk4sto_set_eval_s %d", back return back; } int dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_us %s %s %d", TR_PTR(st), TR_PTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).us = f; st->c = cr; st->h = DK4STO_COMPARE_USHORT; } } $? "- dk4sto_set_eval_us %d", back return back; } int dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_i st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).i = f; st->c = cr; st->h = DK4STO_COMPARE_INT; } } $? "- dk4sto_set_eval_i %d", back return back; } int dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_ui st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).ui = f; st->c = cr; st->h = DK4STO_COMPARE_UINT; } } $? "- dk4sto_set_eval_ui %d", back return back; } int dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_l st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).l = f; st->c = cr; st->h = DK4STO_COMPARE_LONG; } } $? "- dk4sto_set_eval_l %d", back return back; } int dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_ul st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).ul = f; st->c = cr; st->h = DK4STO_COMPARE_ULONG; } } $? "- dk4sto_set_eval_ul %d", back return back; } int dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_f st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).f = f; st->c = cr; st->h = DK4STO_COMPARE_FLOAT; } } $? "- dk4sto_set_eval_f %d", back return back; } int dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_d st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).d = f; st->c = cr; st->h = DK4STO_COMPARE_DOUBLE; } } $? "- dk4sto_set_eval_d %d", back return back; } int dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr) { int back = 0; $? "+ dk4sto_set_eval_d st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr if(st) { if(!(st->r)) { back = 1; (st->e).comp = f; st->c = cr; st->h = DK4STO_COMPARE_FCT; } } $? "- dk4sto_set_eval_d %d", back 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 : */