/*
Copyright (c) 2000-2010, Dirk Krause
All rights reserved.

Redistribution and use in source and binary forms,
with or without modification, are permitted provided
that the following conditions are met:

* Redistributions of source code must retain the above
  copyright notice, this list of conditions and the
  following disclaimer.
* Redistributions in binary form must reproduce the above 
  opyright notice, this list of conditions and the following
  disclaimer in the documentation and/or other materials
  provided with the distribution.
* Neither the name of the Dirk Krause nor the names of
  contributors may be used to endorse or promote
  products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED.
IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.
*/



/**	@file	dksto.c	Storage module.
*/



#include "dk.h"
#include "dktypes.h"
#include "dkmem.h"
#include "dkstr.h"



/**	Inside the dksto module.
*/
#define DK_STO_C 1

#include "dksto.h"



#if DK_HAVE_STDLIB_H
#include <stdlib.h>
#endif




#line 66 "dksto.ctr"




/**	Allocate memory.
*/
#if DK_MEM_NOTRACK
#define STO_ALLOC(t,s)		(t *)dkmem_alloc(sizeof(t),(size_t)(s))
#else
#define STO_ALLOC(t,s)          (t *)dkmem_alloc_tracked(sizeof(t),(size_t)(s))
#endif

/**	Release memory.
*/
#define STO_FREE(p)		{ if(p) { dkmem_free((void *)(p)); } }

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

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

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

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

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

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

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

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

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

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

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

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



/**	Flag: AVL trees can be used.
*/
static int use_trees = 1;

/**	Flag: AVLTREE variable is checked.
*/
static int is_configured = 0;



/**	Check whether the use of AVL trees for sorted storages is allowed.
*/
static void configure_use_trees DK_P0()
{
  if(!is_configured) {
     char *ptr;
     ptr = getenv("AVLTREE");
     if(ptr) {
       if(dkstr_is_on(ptr)) {
	 use_trees = 1;
       } else {
	 use_trees = 0;
       }
     }
     is_configured = 1;
  }
}

/*
  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
node_init_for_object DK_P4(dk_storage_node_t *, n, void *, o, dk_storage_t *,s, int, crit)
{
  
  n->p = n->l = n->r = NULL;
  n->b = n->w = 0;
  n->o = o;
  switch(s->h) {
    case COMPARE_CHAR: (n->v).c = (*((s->e).c))(o,crit); break;
    case COMPARE_UCHAR: (n->v).uc = (*((s->e).uc))(o,crit); break;
    case COMPARE_SHORT: (n->v).s = (*((s->e).s))(o,crit); break;
    case COMPARE_USHORT: (n->v).us = (*((s->e).us))(o,crit); break;
    case COMPARE_INT: (n->v).i = (*((s->e).i))(o,crit); break;
    case COMPARE_UINT: (n->v).ui = (*((s->e).ui))(o,crit); break;
    case COMPARE_LONG: (n->v).l = (*((s->e).l))(o,crit); break;
    case COMPARE_ULONG: (n->v).ul = (*((s->e).ul))(o,crit); break;
    case COMPARE_FLOAT: (n->v).f = (*((s->e).f))(o,crit); break;
    case COMPARE_DOUBLE: (n->v).d = (*((s->e).d))(o,crit); break;
  } 
}



/**	Copy data from one storage node to another.
	@param	d	Destination node.
	@param	s	Source node.
	@param	st	Storage.
*/
static void
node_data_copy DK_P3(dk_storage_node_t *, d, dk_storage_node_t *, s, dk_storage_t *, st)
{
  
  d->o = s->o;
  switch(st->h) {
    case COMPARE_CHAR:   (d->v).c  = (s->v).c ; break;
    case COMPARE_UCHAR:  (d->v).uc = (s->v).uc ; break;
    case COMPARE_SHORT:  (d->v).s  = (s->v).s ; break;
    case COMPARE_USHORT: (d->v).us = (s->v).us ; break;
    case COMPARE_INT:    (d->v).i  = (s->v).i ; break;
    case COMPARE_UINT:   (d->v).ui = (s->v).ui ; break;
    case COMPARE_LONG:   (d->v).l  = (s->v).l ; break;
    case COMPARE_ULONG:  (d->v).ul = (s->v).ul ; break;
    case COMPARE_FLOAT:  (d->v).f  = (s->v).f ; break;
    case COMPARE_DOUBLE: (d->v).d  = (s->v).d ; break;
  }
  
}



/**	Compare two storage nodes.
	@param	l	Left node.
	@param	r	Right node.
	@param	s	Storage.
	@param	c	Comparison criteria.
	@return	Comparison result.
*/
static int
node_compare DK_P4(dk_storage_node_t *, l, dk_storage_node_t *, r, dk_storage_t *, s, int, c)
{
  int back = 0;
  
  switch(s->h) {
    case COMPARE_FCT: { 
      back = (*((s->e).comp))((void *)(l->o),(void *)(r->o),c);
      if(back < 0) back = -1;
      if(back > 0) back =  1;
    } break;
    case COMPARE_CHAR: { 
      if(((l->v).c) > ((r->v).c)) { back = 1; }
      else { if(((l->v).c) < ((r->v).c)) { back = -1; } }
    } break;
    case COMPARE_UCHAR: { 
      if(((l->v).uc) > ((r->v).uc)) { back = 1; }
      else { if(((l->v).uc) < ((r->v).uc)) { back = -1; } }
    } break;
    case COMPARE_SHORT: { 
      if(((l->v).s) > ((r->v).s)) { back = 1; }
      else { if(((l->v).s) < ((r->v).s)) { back = -1; } }
    } break;
    case COMPARE_USHORT: { 
      if(((l->v).us) > ((r->v).us)) { back = 1; }
      else { if(((l->v).us) < ((r->v).us)) { back = -1; } }
    } break;
    case COMPARE_INT: { 
      if(((l->v).i) > ((r->v).i)) { back = 1; }
      else { if(((l->v).i) < ((r->v).i)) { back = -1; } }
    } break;
    case COMPARE_UINT: { 
      if(((l->v).ui) > ((r->v).ui)) { back = 1; }
      else { if(((l->v).ui) < ((r->v).ui)) { back = -1; } }
    } break;
    case COMPARE_LONG: { 
      if(((l->v).l) > ((r->v).l)) { back = 1; }
      else { if(((l->v).l) < ((r->v).l)) { back = -1; } }
    } break;
    case COMPARE_ULONG: { 
      if(((l->v).ul) > ((r->v).ul)) { back = 1; }
      else { if(((l->v).ul) < ((r->v).ul)) { back = -1; } }
    } break;
    case COMPARE_FLOAT: { 
      if(((l->v).f) > ((r->v).f)) { back = 1; }
      else { if(((l->v).f) < ((r->v).f)) { back = -1; } }
    } break;
    case COMPARE_DOUBLE: { 
      if(((l->v).d) > ((r->v).d)) { back = 1; }
      else { if(((l->v).d) < ((r->v).d)) { back = -1; } }
    } break;
  } 
  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 dk_storage_node_t *
unsorted_remove DK_P2(dk_storage_node_t *, ro, dk_storage_node_t *, n)
{
  dk_storage_node_t *back;
  dk_storage_node_t *l, *r;
  
  back = ro;
  l = n->l; r = n->r;
  if(r) {
    r->l = l;
  }
  if(l) {
    l->r = r;
  } else {
    back = r;
  } 
  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 dk_storage_node_t *
unsorted_add DK_P2(dk_storage_node_t *, r, dk_storage_node_t *, n)
{
  dk_storage_node_t *back;
  
  back = n;
  n->r = r;
  if(r) {
    r->l = n;
  } 
  return back;
}



/**	Release all nodes in an unsorted storage.
	@param	r	Root node.
*/
static void
unsorted_release_all_nodes DK_P1(dk_storage_node_t *, r)
{
  dk_storage_node_t *c, *n;
  
  c = r;
  while(c) {
    n = c->r;
    c->p = c->l = c->r = NULL;
    c->o = NULL;
    c->b = c->w = 0;
    STO_FREE(c) ;
    c = n;
  }
  
}



/**	Find next node in an unsorted storage.
	@param	n	Current node.
	@param	r	Root node.
	@return	Pointer to next node or NULL.
*/
static dk_storage_node_t *
unsorted_find_next_node DK_P2(dk_storage_node_t *, n, dk_storage_node_t *, r)
{
  dk_storage_node_t *back = NULL;
  
  if(n) {
    back = n->r;
  } else {
    back = r;
  } 
  return back;
}



/**	Find last node in an unsorted storage.
	@param	n	Root node.
	@return	Last node or NULL.
*/
static dk_storage_node_t *
unsorted_find_last_node DK_P1(dk_storage_node_t *, n)
{
  dk_storage_node_t *back = NULL;
  
  if(n) back = n->l;
  
  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 dk_storage_node_t *
unsorted_find_exact DK_P2(dk_storage_node_t *, r, void *, o)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t *c;
  
  c = r;
  while(c && (!back)) {
    if((c->o) == o) {
      back = c;
    }
    c = c->r;
  } 
  return back;
}



/*
	SORTED DATA HANDLING
*/



/** Go to direction: Left.
*/
#define WALK_LEFT  1

/** Go to direction: Right.
*/
#define WALK_RIGHT 2



/*
	USE AVL-TREE
*/

/**	Perform left rotation at node.
	@param  p	Subpath to modify.
	@return New subpath root node or NULL.
*/
static dk_storage_node_t *
left_rotation DK_P1(dk_storage_node_t *, p)
{
  dk_storage_node_t *p1;
  
  p1 = p->r;
  p->r = p1->l;
  if(p->r) (p->r)->p = p;
  p1->l = p;
  if(p) p->p = p1;
  
  return p1;
}



/**	Perform right rotation at node.
	@param	p	Subpath to modify.
	@return	New subpath root node or NULL.
*/
static dk_storage_node_t *
right_rotation DK_P1(dk_storage_node_t *, p)
{
  dk_storage_node_t *p1;
  
  p1 = p->l;
  p->l = p1->r;
  if(p->l) (p->l)->p = p;
  p1->r = p;
  if(p) p->p = p1;
  
  return p1;
}



/**	Increment balance field of a storage node.
	@param	p	Node to modify.
*/
static void
inc_balance DK_P1(dk_storage_node_t *, p)
{
  short x;
  
  x = p->b; 
  x++;
  if(x > 3) x = 0;
  p->b = x; 
}



/**	Decrement balance field of a storage node.
	@param	p	Storage node.
*/
static void
dec_balance DK_P1(dk_storage_node_t *, p)
{
  short x;
  
  x = p->b; 
  x--;
  if(x < 0) x = 3;
  p->b = x; 
}




/**	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 dk_storage_node_t *
left_deleted DK_P2(dk_storage_node_t *, p, short *, h)
{
  
  switch(p->b) {
    case 0: *h = - *h;
    case 3:
	    
	    inc_balance(p);
	    
	    break;
    case 1: {
      switch((p->r)->b) {
	case 0:
	  (p->r)->b = 3;
	  *h = - *h;
	  p = left_rotation(p);
	break;
	case 1:
	  (p->r)->b = 0;
	  p->b = 0;
	  p = 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      = right_rotation(p->r);
	  if(p->r) (p->r)->p = p;
	  p         = left_rotation(p);
	  p->b      = 0;
      }
    }
  }
  
  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 dk_storage_node_t *
right_deleted DK_P2(dk_storage_node_t *, p, short *, h)
{
  
  switch(p->b) {
    case 0: *h = - *h;
    case 1: dec_balance(p);
            break;
    case 3: {
      switch((p->l)->b) {
	case 0:
	  (p->l)->b = 1;
	  *h = - *h;
	  p = right_rotation(p);
	break;
	case 3:
	  (p->l)->b = 0;
	  p->b = 0;
	  p = 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      = left_rotation(p->l);
	  if(p->l) (p->l)->p = p;
	  p         = right_rotation(p);
	  p->b      = 0;
      }
    } 
  }
  
  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 dk_storage_node_t *
avlt_add DK_P3(dk_storage_node_t *, root, dk_storage_node_t *, newnode, dk_storage_t *, st)
{
  /*
    p ... the current node
    q ... father of p
    r ... critical node
    s ... father of r
  */
  dk_storage_node_t *back, *p, *q, *r, *s;
  
  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(node_compare(p,newnode,st,st->c) > 0) {
      p->w = WALK_LEFT;
      p = p->l;
    } else {
      p->w = 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(node_compare(q,newnode,st,st->c) > 0) {
      q->l = p;
      q->w = WALK_LEFT;
    } else {
      q->r = p;
      q->w = 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 == WALK_LEFT) {
	  dec_balance(p);
	  p = p->l;
	} else {
	  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 == WALK_LEFT) {
	  if((p->l)->b == 3) {
	    p->b = 0;
	    p = 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 = left_rotation(p->l);
	    if(p->l) (p->l)->p = p;
	    p = right_rotation(p);
	  }
	} else {
	  if((p->r)->b == 1) {
	    p->b = 0;
	    p = 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 = right_rotation(p->r);
	    if(p->r) (p->r)->p = p;
	    p = 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 == WALK_LEFT) {
	    s->l = p;
	  } else {
	    s->r = p;
	  }
	  if(p) p->p = s;
	} else {
	  back = p;
	}
      }
    }
  }
  if(back) {
    back->p = NULL;
  }
  
  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 dk_storage_node_t *
avlt_delete DK_P6(dk_storage_node_t *, root, dk_storage_node_t *, node, dk_storage_node_t **, delpath, dk_storage_t *, st, int *, success_indicator, dk_storage_node_t **, toremove)
{
  dk_storage_node_t *back, *p, *q, *r, *todel;
  short      x1 = 0;
  short delroot = 0;
  int can_continue;
  back = root;
  todel = node;
  
  /*
    Make sure the node to delete has max.
    1 subtree.
  */
  if((todel->l) && (todel->r)) {
    
    todel = todel->l;
    while(todel->r) todel = todel->r;
    node_data_copy(node,todel,st);
  }
  if(!(todel->p)) { 
    delroot = 1;
  }
  /*
    Mark the way in the "w" fields.
  */
  *toremove = todel;
  todel->w = 0;
  while(todel->p) {
    if((todel->p)->l == todel) {
      
      (todel->p)->w = WALK_LEFT;
    } else {
      
      (todel->p)->w = WALK_RIGHT;
    }
    todel = todel->p;
  }
  p = back;
  q = r = NULL;
  x1 = 0;
  can_continue = 1;
  while(can_continue) {
    
    if(p) { 
      if(p->w) { 
	if(p->b == 0) {
	  x1 = 0; 
	}
	delpath[x1++] = p; 
	if(x1 >= st->l) {	
	  /* x1 too large */
	  *success_indicator = 0;
	  goto error_mark;
	}
	if(p->w == WALK_LEFT) { 
	  p = p->l;
	} else { 
	  p = p->r;
	}
      } else {
	can_continue = 0; 
      }
    } else {
      can_continue = 0; 
    }
  }
  r = p;
  if(p->l) q = p->l;
  else     q = p->r;
  if(x1 == 0) {
    if(delroot) { 
      back = q;
    }
  }
  while(x1 > 0) { 
    x1--;
    p = delpath[x1];
    if(p->w == WALK_LEFT) {
      
      p->l = q; if(q) q->p = p;
      q = left_deleted(p, &x1);
      
    } else {
      
      p->r = q; if(q) q->p = p;
      q = right_deleted(p, &x1);
      
    }
    if(x1 == 0) {
      
      if(delpath[x1] == back) {
	
	back = q;
      }
    }
    if(x1 < 0) { 
      p = delpath[0 - x1 - 1];
      if(p->w == WALK_LEFT) {
	p->l = q;
      } else {
	p->r = q;
      }
      if(q) q->p = p;
    }
  }
error_mark:
  if(back) {
    back->p = NULL;
  }
  
  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 dk_storage_node_t *
tree_find_like DK_P5(dk_storage_node_t *, root, dk_storage_node_t *, testnode, dk_storage_t *, st, int, crit, dk_storage_node_t **, cand)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t *c;
  int testval;
  
  c = root;
  while(c) {
    testval = 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;
    }
  } 
  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 dk_storage_node_t *
tree_add DK_P3(dk_storage_node_t *, r, dk_storage_node_t *, n, dk_storage_t *, s)
{
  dk_storage_node_t *back;
  back = avlt_add(r,n,s);
  return back;
}



/**	Release all nodes in a tree storage.
	@param	r	Root node.
*/
static void
tree_release_all_nodes DK_P1(dk_storage_node_t *, r)
{
  
  if(r) {
    tree_release_all_nodes(r->l);
    tree_release_all_nodes(r->r);
    r->l = r->r = r->p = NULL;
    r->o = NULL;
    r->b = 0; r->w = 0;
    STO_FREE(r) ;
  } 
}



/**	Find next node in a tree storage.
	@param	n	Current node.
	@param	r	Root node.
	@return	Pointer to next node or NULL.
*/
static dk_storage_node_t *
tree_find_next_node DK_P2(dk_storage_node_t *, n, dk_storage_node_t *, r)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t *c, *p;
  
  /*
  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;
    }
  }
  
  return back;
}



/**	Find last node in a tree storage.
	@param	n	Node to start search from.
	@return	Last node or NULL.
*/
static dk_storage_node_t *
tree_find_last_node DK_P1(dk_storage_node_t *, n)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t *c, *p;
  
  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;
      }
    }
  } 
  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 dk_storage_node_t *
tree_find_exact DK_P3(dk_storage_node_t *, r, void *, o, dk_storage_t *, s)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t testnode, *c, *candidate;
  int testval;
  
  node_init_for_object(&testnode, o, s, s->c);
  c = tree_find_like(r, &testnode, s, s->c, &candidate);
  while(c && (!back)) {
    testval = node_compare(c, &testnode, s, s->c);
    if(testval == 0) {
      if((c->o) == o) {
	back = c;
      } else {
        c = tree_find_next_node(c, r);
      }
    } else {
      c = NULL;
    }
  } 
  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 dk_storage_node_t *
tree_remove DK_P5(dk_storage_node_t *, ro, dk_storage_node_t *, n, dk_storage_t *, st, int *, sci, dk_storage_node_t **, toremove)
{
  dk_storage_node_t *back;
  back = 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 dk_storage_node_t *
list_find_like DK_P5(dk_storage_node_t *, root, dk_storage_node_t *, testnode, dk_storage_t *, st, int, crit, dk_storage_node_t **, cand)
{
  dk_storage_node_t *back = NULL;
  dk_storage_node_t *c;
  int testval;
  
  c = root;
  while(c && (!back)) {
    testval = 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;
    }
  } 
  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 dk_storage_node_t *
list_find_exact DK_P3(dk_storage_node_t *, r, void *, o, dk_storage_t *, s)
{
  dk_storage_node_t *back;
  
  back = unsorted_find_exact(r,o);
  
  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 dk_storage_node_t *
list_add DK_P3(dk_storage_node_t *, r, dk_storage_node_t *, n, dk_storage_t *, s)
{
  dk_storage_node_t *back;
  dk_storage_node_t *larger, *current, *smaller;
  int ende;
  
  back = r;
  if(r) {
    larger = smaller = NULL;
    current = r;
    ende = 0;
    while(!ende) {
      if(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;
  } 
  return back;
}



/**	Release all nodes of a list storage.
	@param	r	Root node.
*/
static void
list_release_all_nodes DK_P1(dk_storage_node_t *, r)
{
  
  unsorted_release_all_nodes(r);
  
}



/**	Find next node.
	@param	n	Current node.
	@param	r	Root node.
	@return	Pointer to next node or NULL.
*/
static dk_storage_node_t *
list_find_next_node DK_P2(dk_storage_node_t *, n, dk_storage_node_t *, r)
{
  dk_storage_node_t *back;
  
  back = unsorted_find_next_node(n,r);
  
  return back;
}



/**	Find last (previous) node.
	@param	n	Current node.
	@return	Pointer to previous node or NULL.
*/
static dk_storage_node_t *
list_find_last_node DK_P1(dk_storage_node_t *, n)
{
  dk_storage_node_t *back;
  
  back = unsorted_find_last_node(n);
  
  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 dk_storage_node_t *
list_remove DK_P5(dk_storage_node_t *, ro, dk_storage_node_t *, n, dk_storage_t *, st, int *, sci, dk_storage_node_t **, toremove)
{
  dk_storage_node_t *back;
  
  back = unsorted_remove(ro,n);
  
  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 dk_storage_node_t *
traverse_iterators_for DK_P2(void *, it, void *, o)
{
  dk_storage_node_t *back = NULL;
  dk_storage_iterator_t *c;
  
  if(it) {
    c = (dk_storage_iterator_t *)it;
    while(c && (!back)) {
      if(c->c) {
	if(((c->c)->o) == o) {
	  back = c->c;
	}
      }
      if(!back) c = c->r;
    }
  } 
  return back;
}



/**	Find last storage node.
	@param	n	Current storage node.
	@param	st	Storage.
	@return	Pointer to last node or NULL.
*/
static dk_storage_node_t *
find_last_node DK_P2(dk_storage_node_t *, n, dk_storage_t *, st)
{
  dk_storage_node_t *back = NULL;
  
  if(st->h) {
    if(st->t) {
      back = tree_find_last_node(n);
    } else {
      back = list_find_last_node(n);
    }
  } else {
    back = unsorted_find_last_node(n);
  }
  
  return back;
}



/**	Initialize storage.
	@param	st	Storage to initialize.
	@param	sz	Indicator for return path buffer length.
	@return	1 on success, 0 on error.
*/
static int
storage_init DK_P2(dk_storage_t *, st, int, sz)
{
  int back = 0;
  short l;
  
  /* 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;
  switch(sz) {
    case DK_STO_SIZE_LARGE : {
      st->l = l = 1024;
    } break;
    case DK_STO_SIZE_MEDIUM : {
      st->l = l = 512;
    } break;
    case DK_STO_SIZE_SMALL : {
      st->l = l = 128;
    } break;
    case DK_STO_SIZE_TINY : {
      st->l = l = 64;
    } break;
  }
  st->d = STO_ALLOC(dk_storage_node_p,l);
  st->t = use_trees;
  if(st->d) {
    back = 1;
  } 
  return back;
}



/**	Close the storage, release memory.
	@param	st	Storage to close.
*/
static void
storage_end DK_P1(dk_storage_t *, st)
{
  
  /* release iterators */
  {
    dk_storage_iterator_t *c, *n;
    c = (dk_storage_iterator_t *)(st->i);
    st->i = NULL;
    while(c) {
      
      n = c->r;
      c->r = NULL;
      c->l = NULL;
      c->c = NULL;
      c->s = NULL;
      STO_FREE(c) ;
      c = n;
    }
    st->i = NULL;
  }
  
  /* release nodes */
  {
    if(st->h) {
      if(st->t) {
	tree_release_all_nodes(st->r);
      } else {
	list_release_all_nodes(st->r);
      }
    } else {
      unsorted_release_all_nodes(st->r);
    }
    st->r = NULL;
  }
  
  /* release delpath */
  {
    dk_storage_node_p *p;
    p = st->d;
    if(p) {
      STO_FREE(p);
    }
    st->d = NULL; st->l = 0;
  }
  
  /* set pointers to NULL */
  {
    st->h = 0;
    st->c = 0;
  }
  
  
}



/*
	PUBLIC INTERFACES
*/


dk_storage_t *dksto_open DK_P1(int, sz)
{
  dk_storage_t *back = NULL;
  
  configure_use_trees();
  back = STO_ALLOC(dk_storage_t,1) ;
  if(back) {
    if(!storage_init(back,sz)) {
      STO_FREE(back) ;
      back = NULL;
    }
  } 
  return back;
}



void dksto_close DK_P1(dk_storage_t *, st)
{
  
  if(st) {
    storage_end(st);
    STO_FREE(st) ;
  } 
}



void
dksto_remove_all DK_P1(dk_storage_t *,st)
{
  if(st) {
    /* reset all iterators */
    dk_storage_iterator_t	*c, *n;
    c = (dk_storage_iterator_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) {
          tree_release_all_nodes(st->r);
        } else {
          list_release_all_nodes(st->r);
        }
      } else {
        unsorted_release_all_nodes(st->r);
      }
    }
    st->r = NULL;
  }
}



int dksto_remove DK_P2(dk_storage_t *, st, void *, o)
{
  int back = 0;
  dk_storage_node_t *node_to_remove, *ln;
  dk_storage_iterator_t *iterator;
  
  if(st && o) {
    node_to_remove = traverse_iterators_for(st->i, o);
    if(!node_to_remove) {
      if(st->h) {
	if(st->t) {
	  node_to_remove = tree_find_exact(st->r,o,st);
	} else {
	  node_to_remove = list_find_exact(st->r,o,st);
	}
      } else {
	node_to_remove = unsorted_find_exact(st->r,o);
      }
    }
    if(node_to_remove) {
      back = 1;
      ln = find_last_node(node_to_remove,st);
      iterator = (dk_storage_iterator_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 = tree_remove(st->r,node_to_remove,st,&back,&node_to_remove);
	} else {
	  st->r = list_remove(st->r,node_to_remove,st,&back,&node_to_remove);
	}
      } else {
	st->r = 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;
      STO_FREE(node_to_remove);
    }
  } 
  return back;
}



int dksto_add DK_P2(dk_storage_t *, st, void *, o)
{
  int back = 0;
  dk_storage_node_t *n;
  
  if(st && o) {
    n = STO_ALLOC(dk_storage_node_t,1) ;
    if(n) {
      node_init_for_object(n,o,st,st->c);
      if(st->h) {
	if(st->t) {
	  st->r = tree_add(st->r, n, st);
	} else {
	  st->r = list_add(st->r, n, st);
	}
      } else {
	st->r = unsorted_add(st->r, n);
      }
      back = 1;
    }
  } 
  return back;
}



dk_storage_iterator_t *
dksto_it_open DK_P1(dk_storage_t *, st)
{
  dk_storage_iterator_t *back = NULL;
  
  if(st) {
    back = STO_ALLOC(dk_storage_iterator_t,1) ;
    if(back) {
      back->s = st;
      back->l = NULL;
      back->r = (dk_storage_iterator_t *)(st->i);
      back->c = NULL;
      st->i = (void *)back;
    }
  } 
  return back;
}



void
dksto_it_close DK_P1(dk_storage_iterator_t *, it)
{
  dk_storage_iterator_t *l, *r;
  dk_storage_t *s;
  
  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;
    STO_FREE(it) ;
  } 
}



void
dksto_it_reset DK_P1(dk_storage_iterator_t *, it)
{
  
  if(it) {
    it->c = NULL;
  } 
}



void *
dksto_it_next DK_P1(dk_storage_iterator_t *, it)
{
  void *back = NULL;
  
  if(it) {
    if(it->s) {
      if((it->s)->h) {
	if((it->s)->t) {
	  it->c = tree_find_next_node(it->c, (it->s)->r);
	} else {
	  it->c = list_find_next_node(it->c, (it->s)->r);
	}
      } else {
	it->c = unsorted_find_next_node(it->c, (it->s)->r);
      }
      if(it->c) {
	back = (it->c)->o;
      }
    }
  } 
  return back;
}



void *
dksto_it_find_exact DK_P2(dk_storage_iterator_t *, i, void *, o)
{
  void *back = NULL;
  
  if(i && o) {
    if(i->s) {
      if((i->s)->h) {
	if((i->s)->t) {
	  i->c = tree_find_exact((i->s)->r, o, i->s);
	} else {
	  i->c = list_find_exact((i->s)->r, o, i->s);
	}
      } else {
	i->c = unsorted_find_exact((i->s)->r, o);
      }
    }
    if(i->c) {
      back = (i->c)->o;
    }
  } 
  return back;
}



void *
dksto_it_find_like DK_P3(dk_storage_iterator_t *, i, void *, o, int, cr)
{
  void *back = NULL;
  dk_storage_node_t testnode, *candidate;
  
  if(i && o) {
    if(i->s) {
      candidate = NULL;
      if((i->s)->h) {
	node_init_for_object(&testnode, o, (i->s), cr);
	if((i->s)->t) {
	  i->c = tree_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
	} else {
	  i->c = list_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
	}
      } else {
	i->c = unsorted_find_exact((i->s)->r, o);
      }
      if(i->c) {
	back = (i->c)->o;
      } else {
	i->c = candidate;
      }
    }
  } 
  return back;
}



int
dksto_set_eval_c DK_P3(dk_storage_t *, st, dk_fct_eval_c_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).c = f;
      st->c = cr;
      st->h = COMPARE_CHAR;
    }
  } 
  return back;
}



int
dksto_set_eval_uc DK_P3(dk_storage_t *, st, dk_fct_eval_uc_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).uc = f;
      st->c = cr;
      st->h = COMPARE_UCHAR;
    }
  } 
  return back;
}



int
dksto_set_eval_s DK_P3(dk_storage_t *, st, dk_fct_eval_s_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).s = f;
      st->c = cr;
      st->h = COMPARE_SHORT;
    }
  } 
  return back;
}



int
dksto_set_eval_us DK_P3(dk_storage_t *, st, dk_fct_eval_us_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).us = f;
      st->c = cr;
      st->h = COMPARE_USHORT;
    }
  } 
  return back;
}



int
dksto_set_eval_i DK_P3(dk_storage_t *, st, dk_fct_eval_i_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).i = f;
      st->c = cr;
      st->h = COMPARE_INT;
    }
  } 
  return back;
}



int
dksto_set_eval_ui DK_P3(dk_storage_t *, st, dk_fct_eval_ui_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).ui = f;
      st->c = cr;
      st->h = COMPARE_UINT;
    }
  } 
  return back;
}



int
dksto_set_eval_l DK_P3(dk_storage_t *, st, dk_fct_eval_l_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).l = f;
      st->c = cr;
      st->h = COMPARE_LONG;
    }
  } 
  return back;
}



int
dksto_set_eval_ul DK_P3(dk_storage_t *, st, dk_fct_eval_ul_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).ul = f;
      st->c = cr;
      st->h = COMPARE_ULONG;
    }
  } 
  return back;
}



int
dksto_set_eval_f DK_P3(dk_storage_t *, st, dk_fct_eval_f_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).f = f;
      st->c = cr;
      st->h = COMPARE_FLOAT;
    }
  } 
  return back;
}



int
dksto_set_eval_d DK_P3(dk_storage_t *, st, dk_fct_eval_d_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).d = f;
      st->c = cr;
      st->h = COMPARE_DOUBLE;
    }
  } 
  return back;
}



int
dksto_set_comp DK_P3(dk_storage_t *, st, dk_fct_comp_t *, f, int, cr)
{
  int back = 0;
  
  if(st) {
    if(!(st->r)) {
      back = 1;
      (st->e).comp = f;
      st->c = cr;
      st->h = COMPARE_FCT;
    }
  } 
  return back;
}



int dksto_use_trees DK_P2(dk_storage_t *,st,int,ok)
{
  int back = 0;
  if(st) {
    if(!(st->r)) {
      st->t = (ok ? 1 : 0);
      back = 1;
    }
  } else {
    use_trees = (ok ? 1 : 0);
    is_configured = 1;
  }
  return back;
}


void *
dksto_find_root DK_P1(dk_storage_t *,s)
{
  void *back = NULL;
  if(s) {
    if(s->r) {
      back = (s->r)->o;
    }
  }
  return back;
}



void *
dksto_it_find_parent DK_P1(dk_storage_iterator_t *,i)
{
  void *back = NULL;
  if(i) {
    if(i->c) {
      if((i->c)->p) {
        back = ((i->c)->p)->o;
      }
    }
  }
  return back;
}



void *
dksto_it_find_left DK_P1(dk_storage_iterator_t *,i)
{
  void *back = NULL;
  if(i) {
    if(i->c) {
      if((i->c)->l) {
        back = ((i->c)->l)->o;
      }
    }
  }
  return back;
}



void *
dksto_it_find_right DK_P1(dk_storage_iterator_t *,i)
{
  void *back = NULL;
  if(i) {
    if(i->c) {
      if((i->c)->r) {
        back = ((i->c)->r)->o;
      }
    }
  }
  return back;
}



void *
dksto_it_find_root DK_P1(dk_storage_iterator_t *,i)
{
  void *back = NULL;
  if(i) {
    if(i->s) {
      back = dksto_find_root(i->s);
    }
  }
  return back;
}