%% options
copyright owner = Dirk Krause
copyright year = 2011-xxxx
license = bsd
%% header
/** @file
Sorted and unsorted data storage in
AVL trees or double linked lists.
CRT on Windows: Optional.
*/
#ifndef DK4CONF_H_INCLUDED
#include "dk4conf.h"
#endif
#ifndef DK4TYPES_H_INCLUDED
#include "dk4types.h"
#endif
#ifndef DK4ERROR_H_INCLUDED
#include "dk4error.h"
#endif
/** Evaluation result for an object.
*/
typedef union {
double d; /**< Evaluation to double. */
float f; /**< Evaluation to float. */
long l; /**< Evaluation to long. */
unsigned long ul; /**< Evaluation to unsigned long. */
int i; /**< Evaluation to int. */
unsigned int ui; /**< Evaluation to unsigned int. */
short s; /**< Evaluation to short. */
unsigned short us; /**< Evaluation to unsigned short. */
char c; /**< Evaluation to char. */
unsigned char uc; /**< Evaluation to unsigned char. */
} dk4_object_eval_res_t;
/** Internal node for dk4_sto_t.
This structure is used internally by the dksto module.
*/
struct dk4__sto__node {
dk4_object_eval_res_t v; /**< Object evaluation of @a o. */
struct dk4__sto__node *p; /**< Parent node in tree. */
struct dk4__sto__node *l; /**< Left child (tree) or neighbour (list). */
struct dk4__sto__node *r; /**< Right child (tree) or neighbour (list). */
void *o; /**< Object to store. */
short b; /**< Balance flag (used in tree only). */
short w; /**< Direction to walk. */
};
/** Internal node for dk4_sto_t.
*/
typedef struct dk4__sto__node dk4_sto_node_t;
/** Pointer to internal node for dk4_sto_t.
*/
typedef dk4_sto_node_t *dk4_sto_node_p;
/** Evaluation functions.
These function type are used to evaluate and compare objects
stored in a sorted dk4_sto_t.
*/
/** Object evaluation function for sorted storage.
*/
typedef char dk4_fct_eval_c_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef unsigned char dk4_fct_eval_uc_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef short dk4_fct_eval_s_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef unsigned short dk4_fct_eval_us_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef int dk4_fct_eval_i_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef unsigned int dk4_fct_eval_ui_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef long dk4_fct_eval_l_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef unsigned long dk4_fct_eval_ul_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef float dk4_fct_eval_f_t(void const *obj, int crit);
/** Object evaluation function for sorted storage.
*/
typedef double dk4_fct_eval_d_t(void const *obj, int crit);
/** Object comparison function for sorted storage.
When comparing to objects while inserting a new object into
a storage both @a o1 and @a o2 are object pointers.
When this function is called from dk4sto_it_find_like() the
@a o1 argument is an object pointer from the storage,
@a o2 is the pointer passed to dk4sto_it_find_like().
*/
typedef int dk4_fct_comp_t(void const *o1, void const *o2, int crit);
/** Choice for object evaluation function.
*/
typedef union {
dk4_fct_eval_c_t *c; /**< Evaluate to char. */
dk4_fct_eval_uc_t *uc; /**< Evaluate to unsigned char. */
dk4_fct_eval_s_t *s; /**< Evaluate to short. */
dk4_fct_eval_us_t *us; /**< Evaluate to unsigned short. */
dk4_fct_eval_i_t *i; /**< Evaluate to int. */
dk4_fct_eval_ui_t *ui; /**< Evaluate to unsigned int. */
dk4_fct_eval_l_t *l; /**< Evaluate to long. */
dk4_fct_eval_ul_t*ul; /**< Evaluate to unsigned long. */
dk4_fct_eval_f_t *f; /**< Evaluate to float. */
dk4_fct_eval_d_t *d; /**< Evaluate to double. */
dk4_fct_comp_t *comp; /**< Compare two objects. */
} dk4_object_eval_fct_t;
/** Object storage.
A storage can be used to store pointers to objects.
*/
typedef struct dk4__sto__t {
dk4_object_eval_fct_t e; /**< Comparison or evaluation function. */
dk4_sto_node_p *d; /**< Critical path for delete operations. */
dk4_sto_node_t *r; /**< Tree root or start of list. */
void *i; /**< Double-linked list of iterators. */
int h; /**< Selection for comparison or evaluation. */
int c; /**< Comparison or evaluation criteria. */
int t; /**< Flag: Use tree, 1=tree, 0=list. */
short l; /**< Path length of critical path. */
} dk4_sto_t;
/** Storage iterator.
This structure can be used to iterate through a dk4_sto_t.
*/
struct dk4__sto__iterator {
struct dk4__sto__iterator *l; /**< Left neighbour (preceeding iterator). */
struct dk4__sto__iterator *r; /**< Right neighbour (following iterator). */
dk4_sto_t *s; /**< Owner storage. */
dk4_sto_node_t *c; /**< Current node, current position. */
};
/** Storage iterator. Can be used to iterate through a dk4_sto_t.
*/
typedef struct dk4__sto__iterator dk4_sto_it_t;
#ifdef __cplusplus
extern "C" {
#endif
/** Create new storage.
@param erp Error report, may be NULL.
@return Pointer to new storage on succcess, NULL on error.
Use dk4sto_close() to destroy the storage when done with it.
Error codes:
- DK4_E_INVALID_ARGUMENTS
if elsize or nelem is 0,
- DK4_E_MATH_OVERFLOW
on numeric overflow when calculating the
product of elsize and nelem,
- DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem
set if there is not enough memory available.
*/
dk4_sto_t *
dk4sto_open(dk4_er_t *erp);
/** Destroy storage, release memory.
@param st Storage to destroy.
*/
void
dk4sto_close(dk4_sto_t *st);
/** Remove all pointers from a storage.
@param st Storage.
*/
void
dk4sto_remove_all(dk4_sto_t *st);
/** Remove one pointer from storage.
@param st Storage.
@param o Object pointer to remove.
@param erp Error report, may be NULL.
@return 1 on success, 0 on error (not found).
Error codes:
- DK4_E_INVALID_ARGUMENTS
if st or o is NULL,
- DK4_E_NOT_FOUND
if o was not found in st.
*/
int
dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp);
/** Add object pointer to storage.
@param st Storage.
@param o Object pointer to add.
@param erp Error report, may be NULL.
@return 1 on success, 0 on error (not enough memory).
Error codes:
- DK4_E_INVALID_ARGUMENTS
if st or os is NULL,
- DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem
set if there is not enough memory available.
*/
int
dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp);
/** Create iterator for storage.
@param st Storage.
@param erp Error report, may be NULL.
@return Pointer to new iterator on success, NULL on error.
Use dk4sto_it_close() to destroy the iterator when done with it.
When closing/destroying a storage all iterators for that
storage are destroyed automatically.
Error codes:
- DK4_E_INVALID_ARGUMENTS
if st is NULL,
- DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem
set if there is not enough memory available.
*/
dk4_sto_it_t *
dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp);
/** Destroy iterator.
@param it Iterator to destroy.
*/
void
dk4sto_it_close(dk4_sto_it_t *it);
/** Reset iterator (next call to dk4sto_it_next() will return the
first object pointer.
@param it Iterator.
*/
void
dk4sto_it_reset(dk4_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 *
dk4sto_it_next(dk4_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 dk4sto_it_next() will return pointers to objects
after the specified object \a o.
*/
void *
dk4sto_it_find_exact(dk4_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 *
dk4sto_it_find_like(dk4_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
dk4sto_set_eval_c(dk4_sto_t *st, dk4_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
dk4sto_set_eval_uc(dk4_sto_t *st, dk4_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
dk4sto_set_eval_s(dk4_sto_t *st, dk4_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
dk4sto_set_eval_us(dk4_sto_t *st, dk4_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
dk4sto_set_eval_i(dk4_sto_t *st, dk4_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
dk4sto_set_eval_ui(dk4_sto_t *st, dk4_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
dk4sto_set_eval_l(dk4_sto_t *st, dk4_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
dk4sto_set_eval_ul(dk4_sto_t *st, dk4_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
dk4sto_set_eval_f(dk4_sto_t *st, dk4_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
dk4sto_set_eval_d(dk4_sto_t *st, dk4_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
dk4sto_set_comp(dk4_sto_t *st, dk4_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
dk4sto_use_trees(dk4_sto_t *st,int ok);
/** Find object pointer at the trees root.
@param s Storage.
*/
void *
dk4sto_find_root(dk4_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 *
dk4sto_it_find_parent(dk4_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 *
dk4sto_it_find_left(dk4_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 *
dk4sto_it_find_right(dk4_sto_it_t *i);
/** Find object pointer at the trees root.
@param i Iterator.
*/
void *
dk4sto_it_find_root(dk4_sto_it_t *i);
#ifdef __cplusplus
}
#endif
%% module
#include "dk4sto.h"
#include "dk4mem.h"
#if 0
#ifndef STDLIB_H_INCLUDED
#include
#define STDLIB_H_INCLUDED 1
#endif
#endif
$(trace-include)
/** Comparison criteria for comparing nodes.
*/
enum {
DK4STO_COMPARE_NONE = 0, /**< Do not compare the objects (unsorted). */
DK4STO_COMPARE_FCT , /**< Use comparison function. */
DK4STO_COMPARE_CHAR , /**< Evaluate objects to char values. */
DK4STO_COMPARE_UCHAR , /**< Evaluate to unsigned char values. */
DK4STO_COMPARE_SHORT , /**< Evaluate to short values. */
DK4STO_COMPARE_USHORT , /**< Evaluate to unsigned short values. */
DK4STO_COMPARE_INT , /**< Evaluate to int values. */
DK4STO_COMPARE_UINT , /**< Evaluate to unsigned int values. */
DK4STO_COMPARE_LONG , /**< Evaluate to long values. */
DK4STO_COMPARE_ULONG , /**< Evaluate to unsigned long values. */
DK4STO_COMPARE_FLOAT , /**< Evaluate to float values. */
DK4STO_COMPARE_DOUBLE /**< Evaluate to double values. */
};
/*
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
dk4sto_node_init_for_object(
dk4_sto_node_t *n,
void *o,
dk4_sto_t *s,
int crit
)
{
$? "+ dk4sto_node_init_for_object PTR=%d PTR=%d PTR=%d %d", TR_IPTR(n), TR_IPTR(o), TR_IPTR(s), crit
n->p = n->l = n->r = NULL;
n->b = n->w = 0;
n->o = o;
switch(s->h) {
case DK4STO_COMPARE_CHAR: (n->v).c = (*((s->e).c))(o,crit); break;
case DK4STO_COMPARE_UCHAR: (n->v).uc = (*((s->e).uc))(o,crit); break;
case DK4STO_COMPARE_SHORT: (n->v).s = (*((s->e).s))(o,crit); break;
case DK4STO_COMPARE_USHORT: (n->v).us = (*((s->e).us))(o,crit); break;
case DK4STO_COMPARE_INT: (n->v).i = (*((s->e).i))(o,crit); break;
case DK4STO_COMPARE_UINT: (n->v).ui = (*((s->e).ui))(o,crit); break;
case DK4STO_COMPARE_LONG: (n->v).l = (*((s->e).l))(o,crit); break;
case DK4STO_COMPARE_ULONG: (n->v).ul = (*((s->e).ul))(o,crit); break;
case DK4STO_COMPARE_FLOAT: (n->v).f = (*((s->e).f))(o,crit); break;
case DK4STO_COMPARE_DOUBLE: (n->v).d = (*((s->e).d))(o,crit); break;
} $? "- dk4sto_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
dk4sto_node_data_copy(
dk4_sto_node_t *d,
dk4_sto_node_t const *s,
dk4_sto_t *st
)
{
$? "+ dk4sto_node_data_copy PTR=%d PTR=%d", TR_IPTR(d), TR_IPTR(s)
d->o = s->o;
switch(st->h) {
case DK4STO_COMPARE_CHAR: (d->v).c = (s->v).c ; break;
case DK4STO_COMPARE_UCHAR: (d->v).uc = (s->v).uc ; break;
case DK4STO_COMPARE_SHORT: (d->v).s = (s->v).s ; break;
case DK4STO_COMPARE_USHORT: (d->v).us = (s->v).us ; break;
case DK4STO_COMPARE_INT: (d->v).i = (s->v).i ; break;
case DK4STO_COMPARE_UINT: (d->v).ui = (s->v).ui ; break;
case DK4STO_COMPARE_LONG: (d->v).l = (s->v).l ; break;
case DK4STO_COMPARE_ULONG: (d->v).ul = (s->v).ul ; break;
case DK4STO_COMPARE_FLOAT: (d->v).f = (s->v).f ; break;
case DK4STO_COMPARE_DOUBLE: (d->v).d = (s->v).d ; break;
}
$? "- dk4sto_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
dk4sto_node_compare(
dk4_sto_node_t const *l,
dk4_sto_node_t const *r,
dk4_sto_t const *s,
int c
)
{
int back = 0;
$? "+ dk4sto_node_compare PTR=%d PTR=%d PTR=%d %d", TR_IPTR(l), TR_IPTR(r), TR_IPTR(s), c
switch(s->h) {
case DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_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 DK4STO_COMPARE_DOUBLE: { $? ". compare double"
if(((l->v).d) > ((r->v).d)) { back = 1; }
else { if(((l->v).d) < ((r->v).d)) { back = -1; } }
} break;
} $? "- dk4sto_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 dk4_sto_node_t *
dk4sto_unsorted_remove(dk4_sto_node_t *ro, dk4_sto_node_t *n)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *l = NULL; /* Left element. */
dk4_sto_node_t *r = NULL; /* Right element. */
$? "+ dk4sto_unsorted_remove PTR=%d PTR=%d", TR_IPTR(ro), TR_IPTR(n)
back = ro;
l = n->l; r = n->r;
if(r) {
r->l = l;
}
if(l) {
l->r = r;
} else {
back = r;
} $? "- dk4sto_unsorted_remove PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_unsorted_add(dk4_sto_node_t *r, dk4_sto_node_t *n)
{
dk4_sto_node_t *back;
$? "+ dk4sto_unsorted_add PTR=%d PTR=%d", TR_IPTR(r), TR_IPTR(n)
back = n;
n->r = r;
if(r) {
r->l = n;
} $? "- dk4sto_unsorted_add PTR=%d", TR_IPTR(back)
return back;
}
/** Release all nodes in an unsorted storage.
@param r Root node.
*/
static void
dk4sto_unsorted_release_all_nodes(dk4_sto_node_t *r)
{
dk4_sto_node_t *c; /* Current element. */
dk4_sto_node_t *n; /* Next element. */
$? "+ dk4sto_unsorted_release_all_nodes PTR=%d", TR_IPTR(r)
c = r;
while(c) {
n = c->r;
c->p = c->l = c->r = NULL;
c->o = NULL;
c->b = c->w = 0;
dk4mem_free(c) ;
c = n;
}
$? "- dk4sto_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
dk4_sto_node_t *
dk4sto_unsorted_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
{
dk4_sto_node_t *back = NULL;
$? "+ dk4sto_unsorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(r)
if(n) {
back = n->r;
} else {
back = r;
} $? "- dk4sto_unsorted_find_next_node PTR=%d", TR_IPTR(back)
return back;
}
/** Find last node in an unsorted storage.
@param n Root node.
@return Last node or NULL.
*/
static dk4_sto_node_t *
dk4sto_unsorted_find_last_node(dk4_sto_node_t *n)
{
dk4_sto_node_t *back = NULL;
$? "+ dk4sto_unsorted_find_last_node PTR=%d", TR_IPTR(n)
if(n) back = n->l;
$? "- dk4sto_unsorted_find_last_node PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_unsorted_find_exact(dk4_sto_node_t *r, void const *o)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *c; /* Current node. */
$? "+ dk4sto_unsorted_find_exact PTR=%d PTR=%d", TR_IPTR(r), TR_IPTR(o)
c = r;
while(c && (!back)) {
if((c->o) == o) {
back = c;
}
c = c->r;
} $? "- dk4sto_unsorted_find_exact PTR=%d", TR_IPTR(back)
return back;
}
/*
SORTED DATA HANDLING
*/
/** Direction to walk to.
*/
enum {
DK4STO_WALK_LEFT = 1, /**< Go to left. */
DK4STO_WALK_RIGHT = 2 /**< Go to right. */
};
/** Perform left rotation at node.
@param p Subpath to modify.
@return New subpath root node or NULL.
*/
static dk4_sto_node_t *
dk4sto_left_rotation(dk4_sto_node_t *p)
{
dk4_sto_node_t *p1;
$? "+ dk4sto_left_rotation PTR=%d", TR_IPTR(p)
p1 = p->r;
p->r = p1->l;
if(p->r) (p->r)->p = p;
p1->l = p;
if(p) p->p = p1;
$? "- dk4sto_left_rotation PTR=%d", TR_IPTR(p1)
return p1;
}
/** Perform right rotation at node.
@param p Subpath to modify.
@return New subpath root node or NULL.
*/
static dk4_sto_node_t *
dk4sto_right_rotation(dk4_sto_node_t *p)
{
dk4_sto_node_t *p1;
$? "+ dk4sto_right_rotation PTR=%d", TR_IPTR(p)
p1 = p->l;
p->l = p1->r;
if(p->l) (p->l)->p = p;
p1->r = p;
if(p) p->p = p1;
$? "- dk4sto_right_rotation PTR=%d", TR_IPTR(p1)
return p1;
}
/** Increment balance field of a storage node.
@param p Node to modify.
*/
static void
dk4sto_inc_balance(dk4_sto_node_t *p)
{
short x; /* New balance value. */
$? "+ dk4sto_inc_balance PTR=%d", TR_IPTR(p)
x = p->b; $? ". old balance %d", x
x++;
if(x > 3) x = 0;
p->b = x; $? "- dk4sto_inc_balance %d", p->b
}
/** Decrement balance field of a storage node.
@param p Storage node.
*/
static void
dk4sto_dec_balance(dk4_sto_node_t *p)
{
short x; /* New balance value. */
$? "+ dk4sto_dec_balance PTR=%d", TR_IPTR(p)
x = p->b; $? ". old balance %d", x
x--;
if(x < 0) x = 3;
p->b = x; $? "- dk4sto_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 dk4_sto_node_t *
dk4sto_left_deleted(dk4_sto_node_t *p, short *h)
{
$? "+ dk4sto_left_deleted PTR=%d PTR=%d", TR_IPTR(p), TR_IPTR(h)
switch(p->b) {
case 0: *h = - *h;
case 3:
$? ". going to increment balance field of PTR=%d", TR_IPTR(p)
dk4sto_inc_balance(p);
$? ". balance field incremented"
break;
case 1: {
switch((p->r)->b) {
case 0:
(p->r)->b = 3;
*h = - *h;
p = dk4sto_left_rotation(p);
break;
case 1:
(p->r)->b = 0;
p->b = 0;
p = dk4sto_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 = dk4sto_right_rotation(p->r);
if(p->r) (p->r)->p = p;
p = dk4sto_left_rotation(p);
p->b = 0;
}
}
}
$? "- dk4sto_left_deleted PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_right_deleted(dk4_sto_node_t *p, short *h)
{
$? "+ dk4sto_right_deleted PTR=%d PTR=%d", TR_IPTR(p), TR_IPTR(h)
switch(p->b) {
case 0: *h = - *h;
case 1: dk4sto_dec_balance(p);
break;
case 3: {
switch((p->l)->b) {
case 0:
(p->l)->b = 1;
*h = - *h;
p = dk4sto_right_rotation(p);
break;
case 3:
(p->l)->b = 0;
p->b = 0;
p = dk4sto_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 = dk4sto_left_rotation(p->l);
if(p->l) (p->l)->p = p;
p = dk4sto_right_rotation(p);
p->b = 0;
}
}
}
$? "- dk4sto_right_deleted PTR=%d", TR_IPTR(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
dk4_sto_node_t *
dk4sto_avlt_add(dk4_sto_node_t *root, dk4_sto_node_t *newnode, dk4_sto_t *st)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *p = NULL; /* Current node. */
dk4_sto_node_t *q = NULL; /* Father of p. */
dk4_sto_node_t *r = NULL; /* Critical node. */
dk4_sto_node_t *s = NULL; /* Father of r. */
$? "+ dk4sto_avlt_add PTR=%d PTR=%d PTR=%d", TR_IPTR(root), TR_IPTR(newnode), TR_IPTR(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(dk4sto_node_compare(p,newnode,st,st->c) > 0) {
p->w = DK4STO_WALK_LEFT;
p = p->l;
} else {
p->w = DK4STO_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(dk4sto_node_compare(q,newnode,st,st->c) > 0) {
q->l = p;
q->w = DK4STO_WALK_LEFT;
} else {
q->r = p;
q->w = DK4STO_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 == DK4STO_WALK_LEFT) {
dk4sto_dec_balance(p);
p = p->l;
} else {
dk4sto_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 == DK4STO_WALK_LEFT) {
if((p->l)->b == 3) {
p->b = 0;
p = dk4sto_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 = dk4sto_left_rotation(p->l);
if(p->l) (p->l)->p = p;
p = dk4sto_right_rotation(p);
}
} else {
if((p->r)->b == 1) {
p->b = 0;
p = dk4sto_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 = dk4sto_right_rotation(p->r);
if(p->r) (p->r)->p = p;
p = dk4sto_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 == DK4STO_WALK_LEFT) {
s->l = p;
} else {
s->r = p;
}
if(p) p->p = s;
} else {
back = p;
}
}
}
}
if(back) {
back->p = NULL;
}
$? "- dk4sto_avlt_add PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_avlt_delete(
dk4_sto_node_t *root, dk4_sto_node_t *node, dk4_sto_node_t **delpath,
dk4_sto_t *st, int *success_indicator, dk4_sto_node_t **toremove
)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *p = NULL; /* Current node. */
dk4_sto_node_t *q = NULL; /* Father of p. */
dk4_sto_node_t *r = NULL; /* Critical node. */
dk4_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;
$? "+ dk4sto_avlt_delete PTRS=%d %d %d %d %d", TR_IPTR(root), TR_IPTR(node), TR_IPTR(delpath), TR_IPTR(st), TR_IPTR(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;
dk4sto_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 = DK4STO_WALK_LEFT;
} else {
$? ". walk right"
(todel->p)->w = DK4STO_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_20150821
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 == DK4STO_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_20150821
} else {
can_continue = 0; $? ". no more nodes to visit"
}
#endif
}
#if VERSION_BEFORE_20150821
r = p;
#endif
/* 2015-08-21 Static code analysis complains p could be NULL.
I think it can not.
*/
if(NULL != 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 == DK4STO_WALK_LEFT) {
$? ". going to left"
p->l = q; if(q) q->p = p;
q = dk4sto_left_deleted(p, &x1);
$? ". after dk4sto_left_deleted"
} else {
$? ". going to right"
p->r = q; if(q) q->p = p;
q = dk4sto_right_deleted(p, &x1);
$? ". after dk4sto_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 == DK4STO_WALK_LEFT) {
p->l = q;
} else {
p->r = q;
}
if(q) q->p = p;
}
}
error_mark:
if(back) {
back->p = NULL;
}
$? "- dk4sto_avlt_delete PTR=%d", TR_IPTR(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
dk4_sto_node_t *
dk4sto_tree_find_like(
dk4_sto_node_t *root, dk4_sto_node_t *testnode, dk4_sto_t *st, int crit,
dk4_sto_node_t **cand
)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *c = NULL; /* Current node. */
int testval = 0; /* Comparison result. */
$? "+ sorted_find_like PTR=%d PTR=%d PTR=%d %d", TR_IPTR(root), TR_IPTR(testnode), TR_IPTR(st), crit
c = root;
while(c) {
testval = dk4sto_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 PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_tree_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s)
{
dk4_sto_node_t *back;
back = dk4sto_avlt_add(r,n,s);
return back;
}
/** Release all nodes in a tree storage.
@param r Root node.
*/
static void
dk4sto_tree_release_all_nodes(dk4_sto_node_t *r)
{
$? "+ sorted_release_all_nodes PTR=%d", TR_IPTR(r)
if(r) {
dk4sto_tree_release_all_nodes(r->l);
dk4sto_tree_release_all_nodes(r->r);
r->l = r->r = r->p = NULL;
r->o = NULL;
r->b = 0; r->w = 0;
dk4mem_free(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 dk4_sto_node_t *
dk4sto_tree_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *c = NULL; /* Current node. */
dk4_sto_node_t *p = NULL; /* Parent of c. */
$? "+ sorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(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 PTR=%d", TR_IPTR(back)
return back;
}
/** Find last node in a tree storage.
@param n Node to start search from.
@return Last node or NULL.
*/
static dk4_sto_node_t *
dk4sto_tree_find_last_node(dk4_sto_node_t *n)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *c; /* Current node. */
dk4_sto_node_t *p; /* Father of c. */
$? "+ sorted_find_last_node PTR=%d", TR_IPTR(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 PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_tree_find_exact(dk4_sto_node_t *r, void const *o, dk4_sto_t *s)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t testnode; /* Test node for comparisons. */
dk4_sto_node_t *c; /* Current node to test. */
dk4_sto_node_t *candidate; /* Candidate for found node. */
int testval = 0; /* Comparison result. */
$? "+ sorted_find_exact PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(o), TR_IPTR(s)
dk4sto_node_init_for_object(&testnode, (void *)o, s, s->c);
c = dk4sto_tree_find_like(r, &testnode, s, s->c, &candidate);
while(c && (!back)) {
testval = dk4sto_node_compare(c, &testnode, s, s->c);
if(testval == 0) {
if((c->o) == o) {
back = c;
} else {
c = dk4sto_tree_find_next_node(c, r);
}
} else {
c = NULL;
}
} $? "- sorted_find_exact PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_tree_remove(
dk4_sto_node_t *ro, dk4_sto_node_t *n, dk4_sto_t *st, int *sci,
dk4_sto_node_t **toremove
)
{
dk4_sto_node_t *back;
back = dk4sto_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 dk4_sto_node_t *
dk4sto_list_find_like(
dk4_sto_node_t *root, dk4_sto_node_t *testnode, dk4_sto_t *st, int crit,
dk4_sto_node_t **cand
)
{
dk4_sto_node_t *back = NULL;
dk4_sto_node_t *c = NULL; /* Current node. */
int testval = 0; /* Comparison result. */
$? "+ sorted_find_like PTR=%d PTR=%d PTR=%d %d", TR_IPTR(root), TR_IPTR(testnode), TR_IPTR(st), crit
c = root;
while(c && (!back)) {
testval = dk4sto_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 PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_list_find_exact(dk4_sto_node_t *r, void const *o, dk4_sto_t *s)
{
dk4_sto_node_t *back;
$? "+ sorted_find_exact PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(o), TR_IPTR(s)
back = dk4sto_unsorted_find_exact(r,o);
$? "- sorted_find_exact PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_list_add(dk4_sto_node_t *r, dk4_sto_node_t *n, dk4_sto_t *s)
{
dk4_sto_node_t *back;
dk4_sto_node_t *larger = NULL; /* Last found larger entry. */
dk4_sto_node_t *current = NULL; /* Current node. */
dk4_sto_node_t *smaller = NULL; /* Last found smaller entry. */
int ende;
$? "+ sorted_add PTRS= %d %d %d", TR_IPTR(r), TR_IPTR(n), TR_IPTR(s)
back = r;
if(r) {
larger = smaller = NULL;
current = r;
ende = 0;
while(!ende) {
if(dk4sto_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 PTR=%d", TR_IPTR(back)
return back;
}
/** Release all nodes of a list storage.
@param r Root node.
*/
static void
dk4sto_list_release_all_nodes(dk4_sto_node_t *r)
{
$? "+ sorted_release_all_nodes"
dk4sto_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 dk4_sto_node_t *
dk4sto_list_find_next_node(dk4_sto_node_t *n, dk4_sto_node_t *r)
{
dk4_sto_node_t *back;
$? "+ sorted_find_next_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(r)
back = dk4sto_unsorted_find_next_node(n,r);
$? "- sorted_find_next_node PTR=%d", TR_IPTR(back)
return back;
}
/** Find last (previous) node.
@param n Current node.
@return Pointer to previous node or NULL.
*/
static dk4_sto_node_t *
dk4sto_list_find_last_node(dk4_sto_node_t *n)
{
dk4_sto_node_t *back;
$? "+ sorted_find_last_node PTR=%d", TR_IPTR(n)
back = dk4sto_unsorted_find_last_node(n);
$? "- sorted_find_last_node PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_list_remove(
dk4_sto_node_t *ro, dk4_sto_node_t *n, dk4_sto_t *st, int *sci,
dk4_sto_node_t **toremove
)
{
dk4_sto_node_t *back;
$? "+ sorted_remove PTRS= %d %d %d", TR_IPTR(ro), TR_IPTR(n), TR_IPTR(st)
back = dk4sto_unsorted_remove(ro,n);
$? "- sorted_remove PTR=%d", TR_IPTR(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 dk4_sto_node_t *
dk4sto_traverse_iterators_for(void *it, void *o)
{
dk4_sto_node_t *back = NULL;
dk4_sto_it_t *c = NULL; /* Current node. */
$? "+ dk4sto_traverse_iterators_for PTR=%d PTR=%d", TR_IPTR(it), TR_IPTR(o)
if(it) {
c = (dk4_sto_it_t *)it;
while(c && (!back)) {
if(c->c) {
if(((c->c)->o) == o) {
back = c->c;
}
}
if(!back) c = c->r;
}
} $? "- dk4sto_traverse_iterators_for PTR=%d", TR_IPTR(back)
return back;
}
/** Find last storage node.
@param n Current storage node.
@param st Storage.
@return Pointer to last node or NULL.
*/
static dk4_sto_node_t *
dk4sto_find_last_node(dk4_sto_node_t *n, dk4_sto_t *st)
{
dk4_sto_node_t *back = NULL;
$? "+ dk4sto_find_last_node PTR=%d PTR=%d", TR_IPTR(n), TR_IPTR(st)
if(st->h) {
if(st->t) {
back = dk4sto_tree_find_last_node(n);
} else {
back = dk4sto_list_find_last_node(n);
}
} else {
back = dk4sto_unsorted_find_last_node(n);
}
$? "- dk4sto_find_last_node PTR=%d", TR_IPTR(back)
return back;
}
/** Initialize storage.
@param st Storage to initialize.
@param erp Error report, may be NULL.
@return 1 on success, 0 on error.
*/
static int
dk4sto_storage_init(dk4_sto_t *st, dk4_er_t *erp)
{
int back = 0;
short l = 0; /* Critical path length. */
$? "+ dk4sto_storage_init PTR=%d", TR_IPTR(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->d = dk4mem_new(dk4_sto_node_p,l,erp);
st->t = 1;
if(st->d) {
back = 1;
} $? "- dk4sto_storage_init %d", back
return back;
}
/** Close the storage, release memory.
@param st Storage to close.
*/
static void
dk4sto_storage_end(dk4_sto_t *st)
{
$? "+ dk4sto_storage_end PTR=%d", TR_IPTR(st)
/* release iterators */
{
dk4_sto_it_t *c = NULL; /* Current iterator. */
dk4_sto_it_t *n = NULL; /* Next iterator. */
c = (dk4_sto_it_t *)(st->i);
st->i = NULL;
while(c) {
$? ". going to release iterator PTR=%d", TR_IPTR(c)
n = c->r;
c->r = NULL;
c->l = NULL;
c->c = NULL;
c->s = NULL;
dk4mem_free(c) ;
c = n;
}
st->i = NULL;
}
$? ". iterators released"
/* release nodes */
{
if(st->h) {
if(st->t) {
dk4sto_tree_release_all_nodes(st->r);
} else {
dk4sto_list_release_all_nodes(st->r);
}
} else {
dk4sto_unsorted_release_all_nodes(st->r);
}
st->r = NULL;
}
$? ". nodes released"
/* release delpath */
{
dk4_sto_node_p *p;
p = st->d;
dk4mem_free(p);
st->d = NULL; st->l = 0;
}
$? ". delpath released"
/* set pointers to NULL */
{
st->h = 0;
st->c = 0;
}
$? ". function pointers resetted"
$? "- dk4sto_storage_end"
}
/*
PUBLIC INTERFACES
*/
dk4_sto_t *
dk4sto_open(dk4_er_t *erp)
{
dk4_sto_t *back = NULL;
$? "+ dk4sto_open"
back = dk4mem_new(dk4_sto_t,1,erp) ;
if(back) {
if(!dk4sto_storage_init(back,erp)) {
dk4mem_free(back);
back = NULL;
}
} $? "- dk4sto_open PTR=%d", TR_IPTR(back)
return back;
}
void
dk4sto_close(dk4_sto_t *st)
{
$? "+ dk4sto_close PTR=%d", TR_IPTR(st)
if(st) {
dk4sto_storage_end(st);
dk4mem_free(st) ;
} $? "- dk4sto_close"
}
void
dk4sto_remove_all(dk4_sto_t *st)
{
if(st) {
/* reset all iterators */
dk4_sto_it_t *c = NULL; /* Curent iterator. */
dk4_sto_it_t *n = NULL; /* Next iterator. */
c = (dk4_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) {
dk4sto_tree_release_all_nodes(st->r);
} else {
dk4sto_list_release_all_nodes(st->r);
}
} else {
dk4sto_unsorted_release_all_nodes(st->r);
}
}
st->r = NULL;
}
}
int
dk4sto_remove(dk4_sto_t *st, void *o, dk4_er_t *erp)
{
int back = 0;
dk4_sto_node_t *node_to_remove = NULL; /* Node to remove. */
dk4_sto_node_t *ln = NULL; /* Last node. */
dk4_sto_it_t *iterator = NULL; /* Traverse all iterators. */
$? "+ dk4sto_remove PTR=%d PTR=%d", TR_IPTR(st), TR_IPTR(o)
if(st && o) {
node_to_remove = dk4sto_traverse_iterators_for(st->i, o);
if(!node_to_remove) {
if(st->h) {
if(st->t) {
node_to_remove = dk4sto_tree_find_exact(st->r,o,st);
} else {
node_to_remove = dk4sto_list_find_exact(st->r,o,st);
}
} else {
node_to_remove = dk4sto_unsorted_find_exact(st->r,o);
}
}
if(node_to_remove) {
back = 1;
ln = dk4sto_find_last_node(node_to_remove,st);
iterator = (dk4_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 =
dk4sto_tree_remove(st->r,node_to_remove,st,&back,&node_to_remove);
} else {
st->r =
dk4sto_list_remove(st->r,node_to_remove,st,&back,&node_to_remove);
}
} else {
st->r = dk4sto_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;
dk4mem_free(node_to_remove);
} else {
dk4error_set_simple_error_code(erp, DK4_E_NOT_FOUND);
}
} else {
dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
} $? "- dk4sto_remove %d", back
return back;
}
int
dk4sto_add(dk4_sto_t *st, void *o, dk4_er_t *erp)
{
int back = 0;
dk4_sto_node_t *n = NULL; /* New node. */
$? "+ dk4sto_add st=PTR:%d o=PTR:%d", TR_IPTR(st), TR_IPTR(o)
if(st && o) {
n = dk4mem_new(dk4_sto_node_t,1,erp);
if(n) {
dk4sto_node_init_for_object(n,o,st,st->c);
if(st->h) {
if(st->t) {
st->r = dk4sto_tree_add(st->r, n, st);
} else {
st->r = dk4sto_list_add(st->r, n, st);
}
} else {
st->r = dk4sto_unsorted_add(st->r, n);
}
back = 1;
}
} else {
dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
} $? "- dk4sto_add %d", back
return back;
}
dk4_sto_it_t *
dk4sto_it_open(dk4_sto_t *st, dk4_er_t *erp)
{
dk4_sto_it_t *back = NULL;
$? "+ dk4sto_it_open PTR=%d", TR_IPTR(st)
if(st) {
back = dk4mem_new(dk4_sto_it_t,1,erp);
if(back) {
back->s = st;
back->l = NULL;
back->r = (dk4_sto_it_t *)(st->i);
back->c = NULL;
st->i = (void *)back;
}
} else {
dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
}$? "- dk4sto_it_open PTR=%d", TR_IPTR(back)
return back;
}
void
dk4sto_it_close(dk4_sto_it_t *it)
{
dk4_sto_it_t *l = NULL; /* Left iterator. */
dk4_sto_it_t *r = NULL; /* Right iterator. */
dk4_sto_t *s = NULL; /* The storage. */
$? "+ dk4sto_it_close PTR=%d", TR_IPTR(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;
dk4mem_free(it) ;
} $? "- dk4sto_it_close"
}
void
dk4sto_it_reset(dk4_sto_it_t *it)
{
$? "+ dk4sto_it_reset PTR=%d", TR_IPTR(it)
if(it) {
it->c = NULL;
} $? "- dk4sto_it_reset"
}
void *
dk4sto_it_next(dk4_sto_it_t *it)
{
void *back = NULL;
$? "+ dk4sto_it_next PTR=%d", TR_IPTR(it)
if(it) {
if(it->s) {
if((it->s)->h) {
if((it->s)->t) {
it->c = dk4sto_tree_find_next_node(it->c, (it->s)->r);
} else {
it->c = dk4sto_list_find_next_node(it->c, (it->s)->r);
}
} else {
it->c = dk4sto_unsorted_find_next_node(it->c, (it->s)->r);
}
if(it->c) {
back = (it->c)->o;
}
}
} $? "- dk4sto_it_next PTR=%d", TR_IPTR(back)
return back;
}
void *
dk4sto_it_find_exact(dk4_sto_it_t *i, void const *o)
{
void *back = NULL;
$? "+ dk4sto_it_find_exact i=PTR:%d o=PTR:%d", TR_IPTR(i), TR_IPTR(o)
if(i && o) {
if(i->s) {
if((i->s)->h) {
if((i->s)->t) {
i->c = dk4sto_tree_find_exact((i->s)->r, o, i->s);
} else {
i->c = dk4sto_list_find_exact((i->s)->r, o, i->s);
}
} else {
i->c = dk4sto_unsorted_find_exact((i->s)->r, o);
}
}
if(i->c) {
back = (i->c)->o;
}
} $? "- dk4sto_it_find_exact PTR=%d", TR_IPTR(back)
return back;
}
void *
dk4sto_it_find_like(dk4_sto_it_t *i, void const *o, int cr)
{
void *back = NULL;
dk4_sto_node_t testnode; /* Test node for comparisons. */
dk4_sto_node_t *candidate = NULL; /* Candicate node. */
$? "+ dk4sto_it_find_like i=PTR:%d o=PTR:%d %d", TR_IPTR(i), TR_IPTR(o), cr
if(i && o) {
if(i->s) {
candidate = NULL;
if((i->s)->h) {
dk4sto_node_init_for_object(&testnode, (void *)o, (i->s), cr);
if((i->s)->t) {
i->c =
dk4sto_tree_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
} else {
i->c =
dk4sto_list_find_like((i->s)->r, &testnode, i->s, cr, &candidate);
}
} else {
i->c = dk4sto_unsorted_find_exact((i->s)->r, o);
}
if(i->c) {
back = (i->c)->o;
} else {
i->c = candidate;
}
}
} $? "- dk4sto_it_find_like PTR=%d", TR_IPTR(back)
return back;
}
int
dk4sto_set_eval_c(dk4_sto_t *st, dk4_fct_eval_c_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_c st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).c = f;
st->c = cr;
st->h = DK4STO_COMPARE_CHAR;
}
} $? "- dk4sto_set_eval_c %d", back
return back;
}
int
dk4sto_set_eval_uc(dk4_sto_t *st, dk4_fct_eval_uc_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_uc st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).uc = f;
st->c = cr;
st->h = DK4STO_COMPARE_UCHAR;
}
} $? "- dk4sto_set_eval_uc %d", back
return back;
}
int
dk4sto_set_eval_s(dk4_sto_t *st, dk4_fct_eval_s_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_s st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).s = f;
st->c = cr;
st->h = DK4STO_COMPARE_SHORT;
}
} $? "- dk4sto_set_eval_s %d", back
return back;
}
int
dk4sto_set_eval_us(dk4_sto_t *st, dk4_fct_eval_us_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_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 = DK4STO_COMPARE_USHORT;
}
} $? "- dk4sto_set_eval_us %d", back
return back;
}
int
dk4sto_set_eval_i(dk4_sto_t *st, dk4_fct_eval_i_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_i st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).i = f;
st->c = cr;
st->h = DK4STO_COMPARE_INT;
}
} $? "- dk4sto_set_eval_i %d", back
return back;
}
int
dk4sto_set_eval_ui(dk4_sto_t *st, dk4_fct_eval_ui_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_ui st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).ui = f;
st->c = cr;
st->h = DK4STO_COMPARE_UINT;
}
} $? "- dk4sto_set_eval_ui %d", back
return back;
}
int
dk4sto_set_eval_l(dk4_sto_t *st, dk4_fct_eval_l_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_l st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).l = f;
st->c = cr;
st->h = DK4STO_COMPARE_LONG;
}
} $? "- dk4sto_set_eval_l %d", back
return back;
}
int
dk4sto_set_eval_ul(dk4_sto_t *st, dk4_fct_eval_ul_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_ul st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).ul = f;
st->c = cr;
st->h = DK4STO_COMPARE_ULONG;
}
} $? "- dk4sto_set_eval_ul %d", back
return back;
}
int
dk4sto_set_eval_f(dk4_sto_t *st, dk4_fct_eval_f_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_f st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).f = f;
st->c = cr;
st->h = DK4STO_COMPARE_FLOAT;
}
} $? "- dk4sto_set_eval_f %d", back
return back;
}
int
dk4sto_set_eval_d(dk4_sto_t *st, dk4_fct_eval_d_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_d st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).d = f;
st->c = cr;
st->h = DK4STO_COMPARE_DOUBLE;
}
} $? "- dk4sto_set_eval_d %d", back
return back;
}
int
dk4sto_set_comp(dk4_sto_t *st, dk4_fct_comp_t *f, int cr)
{
int back = 0;
$? "+ dk4sto_set_eval_d st=PTR:%d f=PTR:%d %d", TR_IPTR(st), TR_IPTR(f), cr
if(st) {
if(!(st->r)) {
back = 1;
(st->e).comp = f;
st->c = cr;
st->h = DK4STO_COMPARE_FCT;
}
} $? "- dk4sto_set_eval_d %d", back
return back;
}
int
dk4sto_use_trees(dk4_sto_t *st,int ok)
{
int back = 0;
if(st) {
if(!(st->r)) {
st->t = (ok ? 1 : 0);
back = 1;
}
}
return back;
}
void *
dk4sto_find_root(dk4_sto_t *s)
{
void *back = NULL;
if(s) {
if(s->r) {
back = (s->r)->o;
}
}
return back;
}
void *
dk4sto_it_find_parent(dk4_sto_it_t *i)
{
void *back = NULL;
if(i) {
if(i->c) {
if((i->c)->p) {
back = ((i->c)->p)->o;
}
}
}
return back;
}
void *
dk4sto_it_find_left(dk4_sto_it_t *i)
{
void *back = NULL;
if(i) {
if(i->c) {
if((i->c)->l) {
back = ((i->c)->l)->o;
}
}
}
return back;
}
void *
dk4sto_it_find_right(dk4_sto_it_t *i)
{
void *back = NULL;
if(i) {
if(i->c) {
if((i->c)->r) {
back = ((i->c)->r)->o;
}
}
}
return back;
}
void *
dk4sto_it_find_root(dk4_sto_it_t *i)
{
void *back = NULL;
if(i) {
if(i->s) {
back = dk4sto_find_root(i->s);
}
}
return back;
}
/* vim: set ai sw=2 : */