%%	options

copyright owner	=	Dirk Krause
copyright year	=	2011-2014
license		=	bsd



%%	header

#include "dk3conf.h"
#include "dk3types.h"

#ifdef __cplusplus
extern "C" {
#endif

/**	Create new storage.
	@param	app	Application structure for diagnostics, may be NULL.
	@return	Pointer to new storage on succcess, NULL on error.
	Use dk3sto_close() to destroy the storage when done with it.
*/
dk3_sto_t *
dk3sto_open_app(dk3_app_t *app);

/**	Destroy storage, release memory.
	@param	st	Storage to destroy.
*/
void
dk3sto_close(dk3_sto_t *st);

/**	Remove all pointers from a storage.
	@param	st	Storage.
*/
void
dk3sto_remove_all(dk3_sto_t *st);

/**	Remove one pointer from storage.
	@param	st	Storage.
	@param	o	Object pointer to remove.
	@return	1 on success, 0 on error (not found).
*/
int
dk3sto_remove(dk3_sto_t *st, void *o);

/**	Add object pointer to storage.
	@param	st	Storage.
	@param	o	Object pointer to add.
	@return	1 on success, 0 on error (not enough memory).
*/
int
dk3sto_add(dk3_sto_t *st, void *o);

/**	Create iterator for storage.
	@param	st	Storage.
	@return	Pointer to new iterator on success, NULL on error.
	Use dk3sto_it_close() to destroy the iterator when done with it.
	When closing/destroying a storage all iterators for that
	storage are destroyed automatically.
*/
dk3_sto_it_t *
dk3sto_it_open(dk3_sto_t *st);

/**	Destroy iterator.
	@param	it	Iterator to destroy.
*/
void
dk3sto_it_close(dk3_sto_it_t *it);

/**	Reset iterator (next call to dk3sto_it_next() will return the
	first object pointer.
	@param	it	Iterator.
*/
void
dk3sto_it_reset(dk3_sto_it_t *it);

/**	Return next object pointer.
	@param	it	Iterator.
	@return	Pointer to next object on success, NULL on error
	(no more pointers available).
*/
void *
dk3sto_it_next(dk3_sto_it_t *it);

/**	Find a pointer exactly.
	@param	i	Iterator.
	@param	o	Object pointer.
	@return	Object pointer on success, NULL on error (object not found).
	The next calls to dk3sto_it_next() will return pointers to objects
	after the specified object \a o.
*/
void *
dk3sto_it_find_exact(dk3_sto_it_t *i, void const *o);

/**	Find object pointer for object evaluating equally to \a o.
	@param	i	Iterator.
	@param	o	Object pointer.
	@param	cr	Comparison criteria.
	@return	Object pointer on success, NULL on error (no such object).
*/
void *
dk3sto_it_find_like(dk3_sto_it_t *i, void const *o, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to a char.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_c(dk3_sto_t *st, dk3_fct_eval_c_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to an unsigned char.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_uc(dk3_sto_t *st, dk3_fct_eval_uc_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to a short.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_s(dk3_sto_t *st, dk3_fct_eval_s_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to an unsigned short.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_us(dk3_sto_t *st, dk3_fct_eval_us_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to an int.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_i(dk3_sto_t *st, dk3_fct_eval_i_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to an unsigned int.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_ui(dk3_sto_t *st, dk3_fct_eval_ui_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to a long.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_l(dk3_sto_t *st, dk3_fct_eval_l_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to an unsigned long.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_ul(dk3_sto_t *st, dk3_fct_eval_ul_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to a float.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_f(dk3_sto_t *st, dk3_fct_eval_f_t *f, int cr);

/**	Set evaluation function.
	@param	st	Storage.
	@param	f	Function evaluating a pointer to a double.
	@param	cr	Evaluation criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_eval_d(dk3_sto_t *st, dk3_fct_eval_d_t *f, int cr);

/**	Set comparison function.
	@param	st	Storage.
	@param	f	Function comparing two object pointers.
	@param	cr	Comparison criteria.
	@return	1 on success, 0 on error.
*/
int
dk3sto_set_comp(dk3_sto_t *st, dk3_fct_comp_t *f, int cr);

/**	Allow use of tree structures.
	This function must be called before adding any data.
	@param	st	Storage.
	@param	ok	Flag: Trees may be used.
	@return	1 on success, 0 on error.
*/
int
dk3sto_use_trees(dk3_sto_t *st,int ok);

/**	Find object pointer at the trees root.
	@param	s	Storage.
*/
void *
dk3sto_find_root(dk3_sto_t *s);

/**	Find object pointer for the parent node
	of the last found object.
	@param	i	Iterator.
	@return	Object pointer on success, NULL on error.
*/
void *
dk3sto_it_find_parent(dk3_sto_it_t *i);

/**	Find object pointer for node on left child of the last found object.
	@param	i	Iterator.
	@return	Object pointer on success, NULL on error.
*/
void *
dk3sto_it_find_left(dk3_sto_it_t *i);

/**	Find object pointer for node on right child of the last found object.
	@param	i	Iterator.
	@return	Object pointer on success, NULL on error.
*/
void *
dk3sto_it_find_right(dk3_sto_it_t *i);

/**	Find object pointer at the trees root.
	@param	i	Iterator.
*/
void *
dk3sto_it_find_root(dk3_sto_it_t *i);



#ifdef __cplusplus
}
#endif



%%	module

#include "dk3all.h"



$(trace-include)



/**	Comparison criteria: Do not compare the objects (unsorted storage).
*/
#define DK3STO_COMPARE_NONE		0

/**     Comparison criteria: Use comparison function.
*/
#define DK3STO_COMPARE_FCT		1

/**     Comparison criteria: Evaluate objects to char values.
*/
#define DK3STO_COMPARE_CHAR		2

/**     Comparison criteria: Evaluate objects to unsigned char values.
*/
#define DK3STO_COMPARE_UCHAR		3

/**     Comparison criteria: Evaluate objects to short values.
*/
#define DK3STO_COMPARE_SHORT		4

/**     Comparison criteria: Evaluate objects to unsigned short values.
*/
#define DK3STO_COMPARE_USHORT		5

/**     Comparison criteria: Evaluate objects to int values.
*/
#define DK3STO_COMPARE_INT		6

/**     Comparison criteria: Evaluate objects to unsigned int values.
*/
#define DK3STO_COMPARE_UINT		7

/**     Comparison criteria: Evaluate objects to long values.
*/
#define DK3STO_COMPARE_LONG		8

/**     Comparison criteria: Evaluate objects to unsigned long values.
*/
#define DK3STO_COMPARE_ULONG		9

/**     Comparison criteria: Evaluate objects to float values.
*/
#define DK3STO_COMPARE_FLOAT		10

/**	Comparison criteria: Evaluate objects to double values.
*/
#define DK3STO_COMPARE_DOUBLE		11



/*
  GENERAL STATIC FUNCTIONS
*/

/**	Initialize storage node for object.
	@param	n	Storage node.
	@param	o	Object.
	@param	s	Storage.
	@param	crit	Comparison/evaluation criteria used by storage.
*/
static void
dk3sto_node_init_for_object(dk3_sto_node_t *n, void *o, dk3_sto_t *s, int crit)
{
  $? "+ dk3sto_node_init_for_object %s %s %s %d", TR_PTR(n), TR_PTR(o), TR_PTR(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 %s %s", TR_PTR(d), TR_PTR(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 %s %s %s %d", TR_PTR(l), TR_PTR(r), TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(r), TR_PTR(n)
  back = n;
  n->r = r;
  if(r) {
    r->l = n;
  } $? "- dk3sto_unsorted_add %s", TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(n), TR_PTR(r)
  if(n) {
    back = n->r;
  } else {
    back = r;
  } $? "- dk3sto_unsorted_find_next_node %s", TR_PTR(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 %s", TR_PTR(n)
  if(n) back = n->l;
  $? "- dk3sto_unsorted_find_last_node %s", TR_PTR(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 %s %s", TR_PTR(r), TR_PTR(o)
  c = r;
  while(c && (!back)) {
    if((c->o) == o) {
      back = c;
    }
    c = c->r;
  } $? "- dk3sto_unsorted_find_exact %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(p), TR_PTR(h)
  switch(p->b) {
    case 0: *h = - *h;
    case 3:
	    $? ". going to increment balance field of %s", TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(p), TR_PTR(h)
  switch(p->b) {
    case 0: *h = - *h;
    case 1: dk3sto_dec_balance(p);
            break;
    case 3: {
      switch((p->l)->b) {
	case 0:
	  (p->l)->b = 1;
	  *h = - *h;
	  p = dk3sto_right_rotation(p);
	break;
	case 3:
	  (p->l)->b = 0;
	  p->b = 0;
	  p = dk3sto_right_rotation(p);
	break;
	case 1:
	  p->b =      (((((p->l)->r)->b) == 3) ? 1 : 0);
	  (p->l)->b = (((((p->l)->r)->b) == 1) ? 3 : 0);
	  p->l      = dk3sto_left_rotation(p->l);
	  if(p->l) (p->l)->p = p;
	  p         = dk3sto_right_rotation(p);
	  p->b      = 0;
      }
    } 
  }
  $? "- dk3sto_right_deleted %s", TR_PTR(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 %s %s %s", TR_PTR(root), TR_PTR(newnode), TR_PTR(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 %s", TR_PTR(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 %s %s %s %s %s", TR_PTR(root), TR_PTR(node), TR_PTR(delpath), TR_PTR(st), TR_PTR(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(p) { $? ". have current node"
      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"
      }
    } else {
      can_continue = 0; $? ". no more nodes to visit"
    }
  }
  r = p;
  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 %s", TR_PTR(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 %s %s %s %d", TR_PTR(root), TR_PTR(testnode), TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(n), TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s %s %s", TR_PTR(r), TR_PTR(o), TR_PTR(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 %s", TR_PTR(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 %s %s %s %d", TR_PTR(root), TR_PTR(testnode), TR_PTR(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 %s", TR_PTR(back)
  return back;
}



/**	Find node for an object (exact search).
	@param	r	Root node.
	@param	o	Object.
	@param	s	Storage.
	@return	Pointer to the objects node or NULL.
*/
static dk3_sto_node_t *
dk3sto_list_find_exact(dk3_sto_node_t *r, void const *o, dk3_sto_t *s)
{
  dk3_sto_node_t *back;
  $? "+ sorted_find_exact %s %s %s", TR_PTR(r), TR_PTR(o), TR_PTR(s)
  back = dk3sto_unsorted_find_exact(r,o);
  $? "- sorted_find_exact %s", TR_PTR(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 %s %s %s", TR_PTR(r), TR_PTR(n), TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(n), TR_PTR(r)
  back = dk3sto_unsorted_find_next_node(n,r);
  $? "- sorted_find_next_node %s", TR_PTR(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 %s", TR_PTR(n)
  back = dk3sto_unsorted_find_last_node(n);
  $? "- sorted_find_last_node %s", TR_PTR(back)
  return back;
}



/**	Remove storage node from list storage.
	@param	ro		Root node.
	@param	n		Node to remove.
	@param	st		Storage.
	@param	sci		???
	@param	toremove	???
*/
static dk3_sto_node_t *
dk3sto_list_remove(
  dk3_sto_node_t *ro, dk3_sto_node_t *n, dk3_sto_t *st, int *sci,
  dk3_sto_node_t **toremove
)
{
  dk3_sto_node_t *back;
  $? "+ sorted_remove %s %s %s", TR_PTR(ro), TR_PTR(n), TR_PTR(st)
  back = dk3sto_unsorted_remove(ro,n);
  $? "- sorted_remove %s", TR_PTR(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 %s %s", TR_PTR(it), TR_PTR(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 %s", TR_PTR(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 %s %s", TR_PTR(n), TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(back)
  return back;
}



void
dk3sto_close(dk3_sto_t *st)
{
  $? "+ dk3sto_close %s", TR_PTR(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 %s %s", TR_PTR(st), TR_PTR(o)
  if(st && o) {
    node_to_remove = dk3sto_traverse_iterators_for(st->i, o);
    if(!node_to_remove) {
      if(st->h) {
	if(st->t) {
	  node_to_remove = dk3sto_tree_find_exact(st->r,o,st);
	} else {
	  node_to_remove = dk3sto_list_find_exact(st->r,o,st);
	}
      } else {
	node_to_remove = dk3sto_unsorted_find_exact(st->r,o);
      }
    }
    if(node_to_remove) {
      back = 1;
      ln = dk3sto_find_last_node(node_to_remove,st);
      iterator = (dk3_sto_it_t *)(st->i);
      while(iterator) {
	if((iterator->c) == node_to_remove) {
	  iterator->c = ln;
	}
	iterator = iterator->r;
      }
      if(st->h) {
	if(st->t) {
	  st->r = dk3sto_tree_remove(st->r,node_to_remove,st,&back,&node_to_remove);
	} else {
	  st->r = dk3sto_list_remove(st->r,node_to_remove,st,&back,&node_to_remove);
	}
      } else {
	st->r = dk3sto_unsorted_remove(st->r,node_to_remove);
      }
      node_to_remove->l = node_to_remove->r = node_to_remove->p = NULL;
      node_to_remove->o = NULL;
      dk3_delete(node_to_remove);
    }
  } $? "- dk3sto_remove %d", back
  return back;
}



int
dk3sto_add(dk3_sto_t *st, void *o)
{
  int back = 0;
  dk3_sto_node_t *n = NULL;	/* New node. */
  $? "+ dk3sto_add %s %s", TR_PTR(st), TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(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 %s", TR_PTR(it)
  if(it) {
    it->c = NULL;
  } $? "- dk3sto_it_reset"
}



void *
dk3sto_it_next(dk3_sto_it_t *it)
{
  void *back = NULL;
  $? "+ dk3sto_it_next %s", TR_PTR(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 %s", TR_PTR(back)
  return back;
}



void *
dk3sto_it_find_exact(dk3_sto_it_t *i, void const *o)
{
  void *back = NULL;
  $? "+ dk3sto_it_find_exact %s %s", TR_PTR(i), TR_PTR(o)
  if(i && o) {
    if(i->s) {
      if((i->s)->h) {
	if((i->s)->t) {
	  i->c = dk3sto_tree_find_exact((i->s)->r, o, i->s);
	} else {
	  i->c = dk3sto_list_find_exact((i->s)->r, o, i->s);
	}
      } else {
	i->c = dk3sto_unsorted_find_exact((i->s)->r, o);
      }
    }
    if(i->c) {
      back = (i->c)->o;
    }
  } $? "- dk3sto_it_find_exact %s", TR_PTR(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 %s %s %d", TR_PTR(i), TR_PTR(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 %s", TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(f), cr
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).us = f;
      st->c = cr;
      st->h = 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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 %s %s %d", TR_PTR(st), TR_PTR(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 : */