diff options
author | Norbert Preining <norbert@preining.info> | 2020-10-12 03:04:00 +0000 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2020-10-12 03:04:00 +0000 |
commit | 0ce40abb18ec02ec6fd6bcc5f21612c88daa7578 (patch) | |
tree | 416289fe1448873fd8ca33051f50ad85bffa8aaa /support/dktools/dk3sto.ctr | |
parent | fdb18507cd80dc17f5a5256153d34668b4f4e61c (diff) |
CTAN sync 202010120303
Diffstat (limited to 'support/dktools/dk3sto.ctr')
-rw-r--r-- | support/dktools/dk3sto.ctr | 2144 |
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 : */ - |