summaryrefslogtreecommitdiff
path: root/support/dktools/dk3sto.ctr
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2020-10-12 03:04:00 +0000
committerNorbert Preining <norbert@preining.info>2020-10-12 03:04:00 +0000
commit0ce40abb18ec02ec6fd6bcc5f21612c88daa7578 (patch)
tree416289fe1448873fd8ca33051f50ad85bffa8aaa /support/dktools/dk3sto.ctr
parentfdb18507cd80dc17f5a5256153d34668b4f4e61c (diff)
CTAN sync 202010120303
Diffstat (limited to 'support/dktools/dk3sto.ctr')
-rw-r--r--support/dktools/dk3sto.ctr2144
1 files changed, 0 insertions, 2144 deletions
diff --git a/support/dktools/dk3sto.ctr b/support/dktools/dk3sto.ctr
deleted file mode 100644
index d1d32b6078..0000000000
--- a/support/dktools/dk3sto.ctr
+++ /dev/null
@@ -1,2144 +0,0 @@
-%% options
-
-copyright owner = Dirk Krause
-copyright year = 2011-xxxx
-SPDX-License-Identifier: BSD-3-Clause
-
-
-
-%% 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;
- /* fall-through */
- 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;
- /* fall-through */
- 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.
- @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_node_t *back;
- $? "+ sorted_find_exact %!8s %!8s", TR_8PTR(r), TR_8PTR(o)
- 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.
-*/
-static
-dk3_sto_node_t *
-dk3sto_list_remove( dk3_sto_node_t *ro, dk3_sto_node_t *n)
-{
- dk3_sto_node_t *back;
- $? "+ sorted_remove %!8s %!8s", TR_8PTR(ro), TR_8PTR(n)
- 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);
- }
- } 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);
- }
- } 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);
- }
- } 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 : */
-