diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/dktools/dk3sto.ctr |
Initial commit
Diffstat (limited to 'support/dktools/dk3sto.ctr')
-rw-r--r-- | support/dktools/dk3sto.ctr | 2147 |
1 files changed, 2147 insertions, 0 deletions
diff --git a/support/dktools/dk3sto.ctr b/support/dktools/dk3sto.ctr new file mode 100644 index 0000000000..5c160687d3 --- /dev/null +++ b/support/dktools/dk3sto.ctr @@ -0,0 +1,2147 @@ +%% options + +copyright owner = Dirk Krause +copyright year = 2011-xxxx +license = bsd + + + +%% header + +#include "dk3conf.h" +#include "dk3types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** Create new storage. + @param app Application structure for diagnostics, may be NULL. + @return Pointer to new storage on succcess, NULL on error. + Use dk3sto_close() to destroy the storage when done with it. +*/ +dk3_sto_t * +dk3sto_open_app(dk3_app_t *app); + +/** Destroy storage, release memory. + @param st Storage to destroy. +*/ +void +dk3sto_close(dk3_sto_t *st); + +/** Remove all pointers from a storage. + @param st Storage. +*/ +void +dk3sto_remove_all(dk3_sto_t *st); + +/** Remove one pointer from storage. + @param st Storage. + @param o Object pointer to remove. + @return 1 on success, 0 on error (not found). +*/ +int +dk3sto_remove(dk3_sto_t *st, void *o); + +/** Add object pointer to storage. + @param st Storage. + @param o Object pointer to add. + @return 1 on success, 0 on error (not enough memory). +*/ +int +dk3sto_add(dk3_sto_t *st, void *o); + +/** Create iterator for storage. + @param st Storage. + @return Pointer to new iterator on success, NULL on error. + Use dk3sto_it_close() to destroy the iterator when done with it. + When closing/destroying a storage all iterators for that + storage are destroyed automatically. +*/ +dk3_sto_it_t * +dk3sto_it_open(dk3_sto_t *st); + +/** Destroy iterator. + @param it Iterator to destroy. +*/ +void +dk3sto_it_close(dk3_sto_it_t *it); + +/** Reset iterator (next call to dk3sto_it_next() will return the + first object pointer. + @param it Iterator. +*/ +void +dk3sto_it_reset(dk3_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 * +dk3sto_it_next(dk3_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 dk3sto_it_next() will return pointers to objects + after the specified object \a o. +*/ +void * +dk3sto_it_find_exact(dk3_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 * +dk3sto_it_find_like(dk3_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 +dk3sto_set_eval_c(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_uc(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_s(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_us(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_i(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_ui(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_l(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_ul(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_f(dk3_sto_t *st, dk3_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 +dk3sto_set_eval_d(dk3_sto_t *st, dk3_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 +dk3sto_set_comp(dk3_sto_t *st, dk3_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 +dk3sto_use_trees(dk3_sto_t *st,int ok); + +/** Find object pointer at the trees root. + @param s Storage. +*/ +void * +dk3sto_find_root(dk3_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 * +dk3sto_it_find_parent(dk3_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 * +dk3sto_it_find_left(dk3_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 * +dk3sto_it_find_right(dk3_sto_it_t *i); + +/** Find object pointer at the trees root. + @param i Iterator. +*/ +void * +dk3sto_it_find_root(dk3_sto_it_t *i); + + + +#ifdef __cplusplus +} +#endif + + + +%% module + +#include "dk3all.h" + + + +$(trace-include) + + + +/** 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) +{ + $? "+ dk3sto_node_init_for_object %!8s %!8s %!8s %d", TR_8PTR(n), TR_8PTR(o), TR_8PTR(s), crit + 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; + } $? "- dk3sto_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 +dk3sto_node_data_copy(dk3_sto_node_t *d, dk3_sto_node_t *s, dk3_sto_t *st) +{ + $? "+ dk3sto_node_data_copy %!8s %!8s", TR_8PTR(d), TR_8PTR(s) + 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; + } + $? "- dk3sto_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 +dk3sto_node_compare(dk3_sto_node_t *l, dk3_sto_node_t *r, dk3_sto_t *s, int c) +{ + int back = 0; + $? "+ dk3sto_node_compare %!8s %!8s %!8s %d", TR_8PTR(l), TR_8PTR(r), TR_8PTR(s), c + switch(s->h) { + case DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_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 DK3STO_COMPARE_DOUBLE: { $? ". compare double" + if(((l->v).d) > ((r->v).d)) { back = 1; } + else { if(((l->v).d) < ((r->v).d)) { back = -1; } } + } break; + } $? "- dk3sto_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 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. */ + $? "+ dk3sto_unsorted_remove %s %s", TR_PTR(ro), TR_PTR(n) + back = ro; + l = n->l; r = n->r; + if(r) { + r->l = l; + } + if(l) { + l->r = r; + } else { + back = r; + } $? "- dk3sto_unsorted_remove %!8s", TR_8PTR(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 dk3_sto_node_t * +dk3sto_unsorted_add(dk3_sto_node_t *r, dk3_sto_node_t *n) +{ + dk3_sto_node_t *back; + $? "+ dk3sto_unsorted_add %!8s %!8s", TR_8PTR(r), TR_8PTR(n) + back = n; + n->r = r; + if(r) { + r->l = n; + } $? "- dk3sto_unsorted_add %!8s", TR_8PTR(back) + 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. */ + $? "+ dk3sto_unsorted_release_all_nodes %!8s", TR_8PTR(r) + 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; + } + $? "- dk3sto_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 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; + $? "+ dk3sto_unsorted_find_next_node %!8s %!8s", TR_8PTR(n), TR_8PTR(r) + if(n) { + back = n->r; + } else { + back = r; + } $? "- dk3sto_unsorted_find_next_node %!8s", TR_8PTR(back) + 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; + $? "+ dk3sto_unsorted_find_last_node %!8s", TR_8PTR(n) + if(n) back = n->l; + $? "- dk3sto_unsorted_find_last_node %!8s", TR_8PTR(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 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. */ + $? "+ dk3sto_unsorted_find_exact %!8s %!8s", TR_8PTR(r), TR_8PTR(o) + c = r; + while(c && (!back)) { + if((c->o) == o) { + back = c; + } + c = c->r; + } $? "- dk3sto_unsorted_find_exact %!8s", TR_8PTR(back) + 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; + $? "+ dk3sto_left_rotation %!8s", TR_8PTR(p) + p1 = p->r; + p->r = p1->l; + if(p->r) (p->r)->p = p; + p1->l = p; + if(p) p->p = p1; + $? "- dk3sto_left_rotation %!8s", TR_8PTR(p1) + 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; + $? "+ dk3sto_right_rotation %!8s", TR_8PTR(p) + p1 = p->l; + p->l = p1->r; + if(p->l) (p->l)->p = p; + p1->r = p; + if(p) p->p = p1; + $? "- dk3sto_right_rotation %!8s", TR_8PTR(p1) + 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. */ + $? "+ dk3sto_inc_balance %!8s", TR_8PTR(p) + x = p->b; $? ". old balance %d", x + x++; + if(x > 3) x = 0; + p->b = x; $? "- dk3sto_inc_balance %d", p->b +} + + + +/** 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. */ + $? "+ dk3sto_dec_balance %!8s", TR_8PTR(p) + x = p->b; $? ". old balance %d", x + x--; + if(x < 0) x = 3; + p->b = x; $? "- dk3sto_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 dk3_sto_node_t * +dk3sto_left_deleted(dk3_sto_node_t *p, short *h) +{ + $? "+ dk3sto_left_deleted %!8s %!8s", TR_8PTR(p), TR_8PTR(h) + switch(p->b) { + case 0: *h = - *h; + case 3: + $? ". going to increment balance field of %!8s", TR_8PTR(p) + dk3sto_inc_balance(p); + $? ". balance field incremented" + 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; + } + } + } + $? "- dk3sto_left_deleted %!8s", TR_8PTR(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 dk3_sto_node_t * +dk3sto_right_deleted(dk3_sto_node_t *p, short *h) +{ + $? "+ dk3sto_right_deleted %!8s %!8s", TR_8PTR(p), TR_8PTR(h) + 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; + } + } + } + $? "- dk3sto_right_deleted %!8s", TR_8PTR(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 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. */ + $? "+ dk3sto_avlt_add %!8s %!8s %!8s", TR_8PTR(root), TR_8PTR(newnode), TR_8PTR(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(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; + } + $? "- dk3sto_avlt_add %!8s", TR_8PTR(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 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; + $? "+ dk3sto_avlt_delete %!8s %!8s %!8s %!8s %!8s", TR_8PTR(root), TR_8PTR(node), TR_8PTR(delpath), TR_8PTR(st), TR_8PTR(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; + dk3sto_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 = DK3STO_WALK_LEFT; + } else { + $? ". walk right" + (todel->p)->w = DK3STO_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_20151002 + 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 == DK3STO_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_20151002 + } else { + can_continue = 0; $? ". no more nodes to visit" + } +#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) { $? ". setting new root node" + back = q; + } + } + while(x1 > 0) { $? ". begin of while loop 2 %d", (x1 - 1) + x1--; + p = delpath[x1]; + if(p->w == DK3STO_WALK_LEFT) { + $? ". going to left" + p->l = q; if(q) q->p = p; + q = dk3sto_left_deleted(p, &x1); + $? ". after dk3sto_left_deleted" + } else { + $? ". going to right" + p->r = q; if(q) q->p = p; + q = dk3sto_right_deleted(p, &x1); + $? ". after dk3sto_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 == DK3STO_WALK_LEFT) { + p->l = q; + } else { + p->r = q; + } + if(q) q->p = p; + } + } +error_mark: + if(back) { + back->p = NULL; + } + $? "- dk3sto_avlt_delete %!8s", TR_8PTR(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 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. */ + $? "+ sorted_find_like %!8s %!8s %!8s %d", TR_8PTR(root), TR_8PTR(testnode), TR_8PTR(st), crit + 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; + } + } $? "- sorted_find_like %!8s", TR_8PTR(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 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) +{ + $? "+ sorted_release_all_nodes %!8s", TR_8PTR(r) + 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) ; + } $? "- 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 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. */ + $? "+ sorted_find_next_node %!8s %!8s", TR_8PTR(n), TR_8PTR(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 %!8s", TR_8PTR(back) + 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. */ + $? "+ sorted_find_last_node %!8s", TR_8PTR(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 %!8s", TR_8PTR(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 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. */ + $? "+ sorted_find_exact %!8s %!8s %!8s", TR_8PTR(r), TR_8PTR(o), TR_8PTR(s) + 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; + } + } $? "- sorted_find_exact %!8s", TR_8PTR(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 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. */ + $? "+ sorted_find_like %!8s %!8s %!8s %d", TR_8PTR(root), TR_8PTR(testnode), TR_8PTR(st), crit + 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; + } + } $? "- sorted_find_like %!8s", TR_8PTR(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 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; + $? "+ sorted_find_exact %!8s %!8s %!8s", TR_8PTR(r), TR_8PTR(o), TR_8PTR(s) + back = dk3sto_unsorted_find_exact(r,o); + $? "- sorted_find_exact %!8s", TR_8PTR(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 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; + $? "+ sorted_add %!8s %!8s %!8s", TR_8PTR(r), TR_8PTR(n), TR_8PTR(s) + 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; + } $? "- sorted_add %!8s", TR_8PTR(back) + 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) +{ + $? "+ sorted_release_all_nodes" + dk3sto_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 dk3_sto_node_t * +dk3sto_list_find_next_node(dk3_sto_node_t *n, dk3_sto_node_t *r) +{ + dk3_sto_node_t *back; + $? "+ sorted_find_next_node %!8s %!8s", TR_8PTR(n), TR_8PTR(r) + back = dk3sto_unsorted_find_next_node(n,r); + $? "- sorted_find_next_node %!8s", TR_8PTR(back) + 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; + $? "+ sorted_find_last_node %!8s", TR_8PTR(n) + back = dk3sto_unsorted_find_last_node(n); + $? "- sorted_find_last_node %!8s", TR_8PTR(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 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; + $? "+ sorted_remove %!8s %!8s %!8s", TR_8PTR(ro), TR_8PTR(n), TR_8PTR(st) + back = dk3sto_unsorted_remove(ro,n); + $? "- sorted_remove %!8s", TR_8PTR(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 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. */ + $? "+ dk3sto_traverse_iterators_for %!8s %!8s", TR_8PTR(it), TR_8PTR(o) + 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; + } + } $? "- dk3sto_traverse_iterators_for %!8s", TR_8PTR(back) + 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; + $? "+ dk3sto_find_last_node %!8s %!8s", TR_8PTR(n), TR_8PTR(st) + 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); + } + $? "- dk3sto_find_last_node %!8s", TR_8PTR(back) + 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. */ + $? "+ dk3sto_storage_init %!8s", TR_8PTR(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->app = app; + st->d = dk3_new_app(dk3_sto_node_p,l,app); + st->t = 1; + if(st->d) { + back = 1; + } $? "- dk3sto_storage_init %d", back + return back; +} + + + +/** Close the storage, release memory. + @param st Storage to close. +*/ +static void +dk3sto_storage_end(dk3_sto_t *st) +{ + $? "+ dk3sto_storage_end %!8s", TR_8PTR(st) + /* 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) { + $? ". going to release iterator %!8s", TR_8PTR(c) + n = c->r; + c->r = NULL; + c->l = NULL; + c->c = NULL; + c->s = NULL; + dk3_delete(c) ; + c = n; + } + st->i = NULL; + } + $? ". iterators released" + /* 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; + } + $? ". nodes released" + /* release delpath */ + { + dk3_sto_node_p *p; + p = st->d; + dk3_delete(p); + st->d = NULL; st->l = 0; + } + $? ". delpath released" + /* set pointers to NULL */ + { + st->h = 0; + st->c = 0; + } + $? ". function pointers resetted" + $? "- dk3sto_storage_end" +} + + + +/* + PUBLIC INTERFACES +*/ + + +dk3_sto_t * +dk3sto_open_app(dk3_app_t *app) +{ + dk3_sto_t *back = NULL; + $? "+ dk3sto_open" + back = dk3_new_app(dk3_sto_t,1,app) ; + if(back) { + if(!dk3sto_storage_init(back,app)) { + dk3_delete(back); + back = NULL; + } + } $? "- dk3sto_open %!8s", TR_8PTR(back) + return back; +} + + + +void +dk3sto_close(dk3_sto_t *st) +{ + $? "+ dk3sto_close %!8s", TR_8PTR(st) + if(st) { + dk3sto_storage_end(st); + dk3_delete(st) ; + } $? "- dk3sto_close" +} + + + +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. */ + $? "+ dk3sto_remove %!8s %!8s", TR_8PTR(st), TR_8PTR(o) + 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); + } + } $? "- dk3sto_remove %d", back + return back; +} + + + +int +dk3sto_add(dk3_sto_t *st, void *o) +{ + int back = 0; + dk3_sto_node_t *n = NULL; /* New node. */ + $? "+ dk3sto_add %!8s %!8s", TR_8PTR(st), TR_8PTR(o) + 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; + } + } $? "- dk3sto_add %d", back + return back; +} + + + +dk3_sto_it_t * +dk3sto_it_open(dk3_sto_t *st) +{ + dk3_sto_it_t *back = NULL; + $? "+ dk3sto_it_open %!8s", TR_8PTR(st) + 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; + } + } $? "- dk3sto_it_open %!8s", TR_8PTR(back) + 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. */ + $? "+ dk3sto_it_close %!8s", TR_8PTR(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; + dk3_delete(it) ; + } $? "- dk3sto_it_close" +} + + + +void +dk3sto_it_reset(dk3_sto_it_t *it) +{ + $? "+ dk3sto_it_reset %!8s", TR_8PTR(it) + if(it) { + it->c = NULL; + } $? "- dk3sto_it_reset" +} + + + +void * +dk3sto_it_next(dk3_sto_it_t *it) +{ + void *back = NULL; + $? "+ dk3sto_it_next %!8s", TR_8PTR(it) + 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; + } + } + } $? "- dk3sto_it_next %!8s", TR_8PTR(back) + return back; +} + + + +void * +dk3sto_it_find_exact(dk3_sto_it_t *i, void const *o) +{ + void *back = NULL; + $? "+ dk3sto_it_find_exact %!8s %!8s", TR_8PTR(i), TR_8PTR(o) + 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; + } + } $? "- dk3sto_it_find_exact %!8s", TR_8PTR(back) + 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. */ + $? "+ dk3sto_it_find_like %!8s %!8s %d", TR_8PTR(i), TR_8PTR(o), cr + 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; + } + } + } $? "- dk3sto_it_find_like %!8s", TR_8PTR(back) + return back; +} + + + +int +dk3sto_set_eval_c(dk3_sto_t *st, dk3_fct_eval_c_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_c %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).c = f; + st->c = cr; + st->h = DK3STO_COMPARE_CHAR; + } + } $? "- dk3sto_set_eval_c %d", back + return back; +} + + + +int +dk3sto_set_eval_uc(dk3_sto_t *st, dk3_fct_eval_uc_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_uc %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).uc = f; + st->c = cr; + st->h = DK3STO_COMPARE_UCHAR; + } + } $? "- dk3sto_set_eval_uc %d", back + return back; +} + + + +int +dk3sto_set_eval_s(dk3_sto_t *st, dk3_fct_eval_s_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_s %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).s = f; + st->c = cr; + st->h = DK3STO_COMPARE_SHORT; + } + } $? "- dk3sto_set_eval_s %d", back + return back; +} + + + +int +dk3sto_set_eval_us(dk3_sto_t *st, dk3_fct_eval_us_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_us %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).us = f; + st->c = cr; + st->h = DK3STO_COMPARE_USHORT; + } + } $? "- dk3sto_set_eval_us %d", back + return back; +} + + + +int +dk3sto_set_eval_i(dk3_sto_t *st, dk3_fct_eval_i_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_i %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).i = f; + st->c = cr; + st->h = DK3STO_COMPARE_INT; + } + } $? "- dk3sto_set_eval_i %d", back + return back; +} + + + +int +dk3sto_set_eval_ui(dk3_sto_t *st, dk3_fct_eval_ui_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_ui %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).ui = f; + st->c = cr; + st->h = DK3STO_COMPARE_UINT; + } + } $? "- dk3sto_set_eval_ui %d", back + return back; +} + + + +int +dk3sto_set_eval_l(dk3_sto_t *st, dk3_fct_eval_l_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_l %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).l = f; + st->c = cr; + st->h = DK3STO_COMPARE_LONG; + } + } $? "- dk3sto_set_eval_l %d", back + return back; +} + + + +int +dk3sto_set_eval_ul(dk3_sto_t *st, dk3_fct_eval_ul_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_ul %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).ul = f; + st->c = cr; + st->h = DK3STO_COMPARE_ULONG; + } + } $? "- dk3sto_set_eval_ul %d", back + return back; +} + + + +int +dk3sto_set_eval_f(dk3_sto_t *st, dk3_fct_eval_f_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_f %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).f = f; + st->c = cr; + st->h = DK3STO_COMPARE_FLOAT; + } + } $? "- dk3sto_set_eval_f %d", back + return back; +} + + + +int +dk3sto_set_eval_d(dk3_sto_t *st, dk3_fct_eval_d_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_d %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).d = f; + st->c = cr; + st->h = DK3STO_COMPARE_DOUBLE; + } + } $? "- dk3sto_set_eval_d %d", back + return back; +} + + + +int +dk3sto_set_comp(dk3_sto_t *st, dk3_fct_comp_t *f, int cr) +{ + int back = 0; + $? "+ dk3sto_set_eval_d %!8s %!8s %d", TR_8PTR(st), TR_8PTR(f), cr + if(st) { + if(!(st->r)) { + back = 1; + (st->e).comp = f; + st->c = cr; + st->h = DK3STO_COMPARE_FCT; + } + } $? "- dk3sto_set_eval_d %d", back + 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 : */ + |