Shinya Kitaoka 810553
#pragma once
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*----------------------------------------------------------------------------*
Toshihiro Shimizu 890ddd
 |                                                                            |
Toshihiro Shimizu 890ddd
 |                                   avl.h                                    |
Toshihiro Shimizu 890ddd
 |                                                                            |
Toshihiro Shimizu 890ddd
 |                by W.T.  11-MAR-91, last revision 22-MAR-92                 |
Toshihiro Shimizu 890ddd
 |                                                                            |
Toshihiro Shimizu 890ddd
 *----------------------------------------------------------------------------*/
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef AVL_H
Toshihiro Shimizu 890ddd
#define AVL_H
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef __cplusplus
Toshihiro Shimizu 890ddd
extern "C" {
Toshihiro Shimizu 890ddd
#define AVL_PROTOTYPES
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef __STDC__
Toshihiro Shimizu 890ddd
#define AVL_PROTOTYPES
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#ifdef VAX
Toshihiro Shimizu 890ddd
#define AVL_PROTOTYPES
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define AVL_MAX_SAFE_OFFSET 1024
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef WIN32
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#undef TNZAPI
Toshihiro Shimizu 890ddd
#ifdef TNZ_IS_COMMONLIB
Toshihiro Shimizu 890ddd
#define TNZAPI __declspec(dllexport)
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#define TNZAPI __declspec(dllimport)
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI double Avl_Dummy[(AVL_MAX_SAFE_OFFSET / sizeof(double)) + 1];
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef AVL_C
Toshihiro Shimizu 890ddd
double Avl_Dummy[(AVL_MAX_SAFE_OFFSET / sizeof(double)) + 1];
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
extern double Avl_Dummy[];
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#define avl_offset(structure, member)                                          \
Shinya Kitaoka 120a6e
  ((unsigned)((char *)&((structure *)Avl_Dummy)->member - (char *)Avl_Dummy))
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define AVL_NODUP_MBR (0 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_PTR (1 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_STR (2 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_LNG (3 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_INT (4 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_SHT (5 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_ULN (6 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_UIN (7 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_USH (8 << 1)
Toshihiro Shimizu 890ddd
#define AVL_NODUP_CHR (9 << 1)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define AVL_DUP_MBR (AVL_NODUP_MBR | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_PTR (AVL_NODUP_PTR | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_STR (AVL_NODUP_STR | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_LNG (AVL_NODUP_LNG | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_INT (AVL_NODUP_INT | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_SHT (AVL_NODUP_SHT | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_ULN (AVL_NODUP_ULN | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_UIN (AVL_NODUP_UIN | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_USH (AVL_NODUP_USH | 1)
Toshihiro Shimizu 890ddd
#define AVL_DUP_CHR (AVL_NODUP_CHR | 1)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define AVL_AVLCMP (int (*)())0
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#define avl_tree_nodup(usrcmp) avl__tree(AVL_NODUP_MBR, (unsigned)0, (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_nodup_mbr(structure, member, usrcmp)                          \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_MBR, avl_offset(structure, member), (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_nodup_ptr(structure, member, usrcmp)                          \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_PTR, avl_offset(structure, member), (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_nodup_str(structure, member)                                  \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_STR, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_long(structure, member)                                 \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_LNG, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_int(structure, member)                                  \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_INT, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_short(structure, member)                                \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_SHT, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_ulong(structure, member)                                \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_ULN, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_uint(structure, member)                                 \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_UIN, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_ushort(structure, member)                               \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_USH, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_nodup_char(structure, member)                                 \
Shinya Kitaoka 120a6e
  avl__tree(AVL_NODUP_CHR, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
#define avl_tree_dup(usrcmp) avl__tree(AVL_DUP_MBR, (unsigned)0, (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_dup_mbr(structure, member, usrcmp)                            \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_MBR, avl_offset(structure, member), (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_dup_ptr(structure, member, usrcmp)                            \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_PTR, avl_offset(structure, member), (usrcmp))
Shinya Kitaoka 120a6e
#define avl_tree_dup_str(structure, member)                                    \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_STR, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_long(structure, member)                                   \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_LNG, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_int(structure, member)                                    \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_INT, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_short(structure, member)                                  \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_SHT, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_ulong(structure, member)                                  \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_ULN, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_uint(structure, member)                                   \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_UIN, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_ushort(structure, member)                                 \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_USH, avl_offset(structure, member), AVL_AVLCMP)
Shinya Kitaoka 120a6e
#define avl_tree_dup_char(structure, member)                                   \
Shinya Kitaoka 120a6e
  avl__tree(AVL_DUP_CHR, avl_offset(structure, member), AVL_AVLCMP)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define avl_nodes(tree) ((tree)->nodes)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define avl_locate(tree, key) avl__locate((tree), (long)(key))
Toshihiro Shimizu 890ddd
#define avl_locate_ge(tree, key) avl__locate_ge((tree), (long)(key))
Toshihiro Shimizu 890ddd
#define avl_locate_gt(tree, key) avl__locate_gt((tree), (long)(key))
Toshihiro Shimizu 890ddd
#define avl_locate_le(tree, key) avl__locate_le((tree), (long)(key))
Toshihiro Shimizu 890ddd
#define avl_locate_lt(tree, key) avl__locate_lt((tree), (long)(key))
Toshihiro Shimizu 890ddd
#define avl_remove(tree, key) avl__remove((tree), (long)(key))
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define avl_scan(tree, usrfun) avl__scan((tree), (usrfun), 0)
Toshihiro Shimizu 890ddd
#define avl_backscan(tree, usrfun) avl__scan((tree), (usrfun), 1)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define avl_start(tree, key) avl__start((tree), (long)(key), 0)
Toshihiro Shimizu 890ddd
#define avl_backstart(tree, key) avl__start((tree), (long)(key), 1)
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#define avl_link(tree, structure, member)                                      \
Shinya Kitaoka 120a6e
  avl__link((tree), avl_offset(structure, member), 0)
Shinya Kitaoka 120a6e
#define avl_backlink(tree, structure, member)                                  \
Shinya Kitaoka 120a6e
  avl__link((tree), avl_offset(structure, member), 1)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define AVL_MAX_PATHDEPTH ((int)sizeof(long) * 8 * 3 / 2 - 2)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
union avl_key {
Shinya Kitaoka 120a6e
  void *ptr;
Shinya Kitaoka 120a6e
  long val;
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
struct avl_node {
Shinya Kitaoka 120a6e
  union avl_key key;
Shinya Kitaoka 120a6e
  void *data;
Shinya Kitaoka 120a6e
  struct avl_node *left;
Shinya Kitaoka 120a6e
  struct avl_node *right;
Shinya Kitaoka 120a6e
  int bal;
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
struct avl_path {
Shinya Kitaoka 120a6e
  struct avl_node **pathnode;
Shinya Kitaoka 120a6e
  char *pathright;
Shinya Kitaoka 120a6e
  struct avl_node *node[AVL_MAX_PATHDEPTH + 2];
Shinya Kitaoka 120a6e
  char right[AVL_MAX_PATHDEPTH + 2];
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef struct avl_tree {
Shinya Kitaoka 120a6e
  unsigned short keyinfo;
Shinya Kitaoka 120a6e
  unsigned short keyoffs;
Shinya Kitaoka 120a6e
  int (*usrcmp)();
Shinya Kitaoka 120a6e
  long nodes;
Shinya Kitaoka 120a6e
  struct avl_node *root;
Shinya Kitaoka 120a6e
  struct avl_path *path;
Toshihiro Shimizu 890ddd
} TREE;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef WIN32
Toshihiro Shimizu 890ddd
#define TNZ_EXPORT_API __declspec(dllexport)
Toshihiro Shimizu 890ddd
#define TNZ_IMPORT_API __declspec(dllimport)
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#define TNZ_EXPORT_API
Toshihiro Shimizu 890ddd
#define TNZ_IMPORT_API
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#undef TNZAPI
Toshihiro Shimizu 890ddd
#ifdef TNZ_IS_COMMONLIB
Toshihiro Shimizu 890ddd
#define TNZAPI TNZ_EXPORT_API
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#define TNZAPI TNZ_IMPORT_API
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef AVL_PROTOTYPES
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI TREE *avl__tree();
Toshihiro Shimizu 890ddd
TNZAPI TREE *avl_copy();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_insert();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_ge();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_gt();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_le();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_lt();
Toshihiro Shimizu 890ddd
TNZAPI void *avl_locate_first();
Toshihiro Shimizu 890ddd
TNZAPI void *avl_locate_last();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__remove();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void avl__scan();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void *avl_first();
Toshihiro Shimizu 890ddd
TNZAPI void *avl_last();
Toshihiro Shimizu 890ddd
TNZAPI void *avl__start();
Toshihiro Shimizu 890ddd
TNZAPI void *avl_next();
Toshihiro Shimizu 890ddd
TNZAPI void *avl_prev();
Toshihiro Shimizu 890ddd
TNZAPI void avl_stop();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void *avl__link();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void avl_release();
Toshihiro Shimizu 890ddd
TNZAPI void avl_reset();
Toshihiro Shimizu 890ddd
TNZAPI void avl_close();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_dump();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_porting_problems();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI TREE *avl__tree(int treetype, unsigned keyoffs, int (*usrcmp)());
Toshihiro Shimizu 890ddd
TNZAPI TREE *avl_copy(TREE *tree);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_insert(TREE *tree, void *data);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_ge(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_gt(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_le(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__locate_lt(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
TNZAPI void *avl_locate_first(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void *avl_locate_last(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__remove(TREE *tree, long keyval);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void avl__scan(TREE *tree, void (*usrfun)(), int back);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void *avl_first(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void *avl_last(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void *avl__start(TREE *tree, long keyval, int back);
Toshihiro Shimizu 890ddd
TNZAPI void *avl_next(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void *avl_prev(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void avl_stop(TREE *tree);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void *avl__link(TREE *tree, unsigned ptroffs, int back);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI void avl_release(TREE *tree, void (*usrfun)());
Toshihiro Shimizu 890ddd
TNZAPI void avl_reset(TREE *tree);
Toshihiro Shimizu 890ddd
TNZAPI void avl_close(TREE *tree);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_dump(TREE *tree, void **dat_vect, int *lev_vect, int *pos_vect);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
TNZAPI int avl_porting_problems(void);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef __cplusplus
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif