summaryrefslogtreecommitdiff
path: root/support/dktools/dk3sto.ctr
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/dktools/dk3sto.ctr
Initial commit
Diffstat (limited to 'support/dktools/dk3sto.ctr')
-rw-r--r--support/dktools/dk3sto.ctr2147
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 : */
+