/*----------------------------------------------------------------------------*

 |                                                                            |

 |                                   avl.c                                    |

 |                                                                            |

 |                by W.T.  11-MAR-91, last revision 11-OCT-96                 |

 |                                                                            |

 *----------------------------------------------------------------------------*/

#ifdef _MSC_VER

#pragma warning(push)

#pragma warning(disable : 4113)

#pragma warning(disable : 4996)

#endif

#include <stdio.h></stdio.h>

#include <stdlib.h></stdlib.h>

#include <string.h></string.h>

#define AVL_C

#include "avl.h"

#include "tcm.h"

#ifndef TRUE

#define TRUE 1

#define FALSE 0

#endif

//#define NIL ((void *)0)

typedef unsigned long ulong;

#ifndef MACOSX

typedef unsigned int uint;

typedef unsigned short ushort;

#endif

typedef struct avl_node NODE;

typedef struct avl_path PATH;

#define MBR_KEY (AVL_NODUP_MBR >> 1)

#define PTR_KEY (AVL_NODUP_PTR >> 1)

#define STR_KEY (AVL_NODUP_STR >> 1)

#define LNG_KEY (AVL_NODUP_LNG >> 1)

#define INT_KEY (AVL_NODUP_INT >> 1)

#define SHT_KEY (AVL_NODUP_SHT >> 1)

#define ULN_KEY (AVL_NODUP_ULN >> 1)

#define UIN_KEY (AVL_NODUP_UIN >> 1)

#define USH_KEY (AVL_NODUP_USH >> 1)

#define CHR_KEY (AVL_NODUP_CHR >> 1)

#define USR_CMP 0

#define STR_CMP 1

#define VAL_CMP 2

#define COR_CMP 3

#define NODUP 0

#define DUP 1

#define USR_NODUP (USR_CMP | NODUP << 2)

#define STR_NODUP (STR_CMP | NODUP << 2)

#define VAL_NODUP (VAL_CMP | NODUP << 2)

#define COR_NODUP (COR_CMP | NODUP << 2)

#define USR_DUP (USR_CMP | DUP << 2)

#define STR_DUP (STR_CMP | DUP << 2)

#define VAL_DUP (VAL_CMP | DUP << 2)

#define COR_DUP (COR_CMP | DUP << 2)

/* keyinfo: bits 6-3: KEYTYPE, bit 2: DUP, bits 1-0: CMPTYPE */

/*                bits 6-2: TREETYPE, bits 2-0: LOCTYPE      */

#define KEYTYPE(keyinfo) ((keyinfo) >> 3)

#define TREETYPE(keyinfo) ((keyinfo) >> 2)

#define CMPTYPE(keyinfo) ((keyinfo)&0x3)

#define LOCTYPE(keyinfo) ((keyinfo)&0x7)

#define MAXUSHORT (((unsigned short)(~0)) >> 1)

#define MINLONG ((long)~(((unsigned long)(~0L)) >> 1))

#define CORRECT(u) ((long)(u) + MINLONG)

#ifdef VAX

#define SET_STRCMP(cmp, str1, str2)                                            \

  {                                                                            \

    char *p1, *p2;                                                             \

    for (p1 = (str1), p2 = (str2); *p1 && *p1 == *p2; p1++, p2++)              \

      ;                                                                        \

    (cmp) = *(unsigned char *)p1 - *(unsigned char *)p2;                       \

  }

#else

#define SET_STRCMP(cmp, str1, str2)                                            \

  { (cmp) = strcmp((str1), (str2)); }

#endif

#define SET_PTRCMP(cmp, usrcmp, ptr1, ptr2)                                    \

  {                                                                            \

    if (usrcmp)                                                                \

      (cmp) = (*(usrcmp))((ptr1), (ptr2));                                     \

    else                                                                       \

      SET_STRCMP((cmp), (char *)(ptr1), (char *)(ptr2))                        \

  }

#define ERROR (-1)

#define BAL 0

#define LEFT 1

#define RIGHT 2

#define LEFTUNBAL 3

#define RIGHTUNBAL 4

#define LESS 3

#define SAME 4

#define NOTINS 0

#define INS 1

#define DEEPER 2

#define NODE_LIST 0

#define TREE_LIST (NODE_LIST + (sizeof(NODE) != sizeof(TREE)))

#define PATH_LIST (TREE_LIST + 1)

#define FREE_LISTS (PATH_LIST + 1)

#define LONG_ALIGNED_SIZE(obj)                                                 \

  ((sizeof(obj) + sizeof(long) - 1) & ~(sizeof(long) - 1))

#define SIZEOF_NODE LONG_ALIGNED_SIZE(NODE)

#define SIZEOF_TREE LONG_ALIGNED_SIZE(TREE)

#define SIZEOF_PATH LONG_ALIGNED_SIZE(PATH)

#define SIZEOF_LONG sizeof(long)

#define PREALLOC_LONGS (0x7FF0 / SIZEOF_LONG)

#define PREALLOC_SIZE (PREALLOC_LONGS * SIZEOF_LONG)

#define MALLOC_LONGS (0x7FE0 / SIZEOF_LONG)

#define MALLOC_SIZE (MALLOC_LONGS * SIZEOF_LONG)

static long Prealloc[PREALLOC_LONGS];

static void *Free_List[FREE_LISTS]; /* init to 0 by C */

static char *Avail_Base = (char *)Prealloc;

static uint Avail_Size  = PREALLOC_SIZE;

/*===========================================================================*/

static void *new_memory(uint size) {

  char *base;

  while (Avail_Size >= SIZEOF_NODE) {

    base                 = Avail_Base + (Avail_Size -= SIZEOF_NODE);

    *(void **)base       = Free_List[NODE_LIST];

    Free_List[NODE_LIST] = (void *)base;

  }

  if ((Avail_Base = (char *)malloc(MALLOC_SIZE))) {

    Avail_Size = MALLOC_SIZE - size;

    return (void *)(Avail_Base + Avail_Size);

  } else {

    Avail_Size = 0;

    return NIL;

  }

}

/*---------------------------------------------------------------------------*/

#define ALLOC_OBJ(ptr, ptr_type, size, list)                                   \

  {                                                                            \

    if (Free_List[list]) {                                                     \

      (ptr)           = (ptr_type)Free_List[list];                             \

      Free_List[list] = *(void **)(ptr);                                       \

    } else if (Avail_Size >= size)                                             \

      (ptr) = (ptr_type)(Avail_Base + (Avail_Size -= size));                   \

    else                                                                       \

      (ptr) = (ptr_type)new_memory(size);                                      \

  }

#define FREE_OBJ(ptr, list)                                                    \

  {                                                                            \

    *(void **)(ptr) = Free_List[list];                                         \

    Free_List[list] = (void *)(ptr);                                           \

  }

#define ALLOC_NODE(node) ALLOC_OBJ(node, NODE *, SIZEOF_NODE, NODE_LIST)

#define ALLOC_TREE(tree) ALLOC_OBJ(tree, TREE *, SIZEOF_TREE, TREE_LIST)

#define ALLOC_PATH(path) ALLOC_OBJ(path, PATH *, SIZEOF_PATH, PATH_LIST)

#define FREE_NODE(node) FREE_OBJ(node, NODE_LIST)

#define FREE_TREE(tree) FREE_OBJ(tree, TREE_LIST)

#define FREE_PATH(path) FREE_OBJ(path, PATH_LIST)

/*===========================================================================*/

TREE *avl__tree(int treetype, uint keyoffs, int (*usrcmp)(void *, void *)) {

  TREE *tree;

  int keyinfo;

  keyinfo = treetype << 2;

  switch (treetype) {

  case AVL_NODUP_MBR:

  case AVL_DUP_MBR:

    keyinfo |= USR_CMP;

    break;

  case AVL_NODUP_PTR:

  case AVL_DUP_PTR:

    keyinfo |= USR_CMP;

    break;

  case AVL_NODUP_STR:

  case AVL_DUP_STR:

    keyinfo |= STR_CMP;

    break;

  case AVL_NODUP_LNG:

  case AVL_DUP_LNG:

    keyinfo |= VAL_CMP;

    break;

  case AVL_NODUP_INT:

  case AVL_DUP_INT:

    keyinfo |= VAL_CMP;

    break;

  case AVL_NODUP_SHT:

  case AVL_DUP_SHT:

    keyinfo |= VAL_CMP;

    break;

  case AVL_NODUP_ULN:

  case AVL_DUP_ULN:

    keyinfo |= COR_CMP;

    break;

  case AVL_NODUP_UIN:

  case AVL_DUP_UIN:

    keyinfo |= COR_CMP;

    break;

  case AVL_NODUP_USH:

  case AVL_DUP_USH:

    keyinfo |= VAL_CMP;

    break;

  case AVL_NODUP_CHR:

  case AVL_DUP_CHR:

    keyinfo |= VAL_CMP;

    break;

  default:

    return NIL;

  }

  ALLOC_TREE(tree)

  if (!tree) return NIL;

  tree->root    = NIL;

  tree->keyinfo = (ushort)keyinfo;

  tree->keyoffs = (ushort)keyoffs;

  tree->usrcmp  = usrcmp;

  tree->nodes   = 0L;

  tree->path    = NIL;

  return tree;

}

/*===========================================================================*/

static int rebalance(NODE **rootaddr) {

  NODE *root = *rootaddr;

  NODE *newroot;

  NODE *half;

  switch (root->bal) {

  case LEFTUNBAL:

    switch (root->left->bal) {

    case LEFT: /* simple rotation, tree depth decreased */

      newroot        = root->left;

      root->left     = newroot->right;

      root->bal      = BAL;

      newroot->right = root;

      newroot->bal   = BAL;

      *rootaddr      = newroot;

      return LESS;

    case BAL: /* simple rotation, tree depth unchanged */

      newroot        = root->left;

      root->left     = newroot->right;

      root->bal      = LEFT;

      newroot->right = root;

      newroot->bal   = RIGHT;

      *rootaddr      = newroot;

      return SAME;

    case RIGHT: /* double rotation */

      half        = root->left;

      newroot     = half->right;

      root->left  = newroot->right;

      half->right = newroot->left;

      switch (newroot->bal) {

      case BAL:

        root->bal = BAL;

        half->bal = BAL;

        break;

      case LEFT:

        root->bal = RIGHT;

        half->bal = BAL;

        break;

      case RIGHT:

        root->bal = BAL;

        half->bal = LEFT;

        break;

      }

      newroot->left  = half;

      newroot->right = root;

      newroot->bal   = BAL;

      *rootaddr      = newroot;

      return LESS;

    }

    break;

  case RIGHTUNBAL:

    switch (root->right->bal) {

    case RIGHT: /* simple rotation, tree depth decreased */

      newroot       = root->right;

      root->right   = newroot->left;

      root->bal     = BAL;

      newroot->left = root;

      newroot->bal  = BAL;

      *rootaddr     = newroot;

      return LESS;

    case BAL: /* simple rotation, tree depth unchanged */

      newroot       = root->right;

      root->right   = newroot->left;

      root->bal     = RIGHT;

      newroot->left = root;

      newroot->bal  = LEFT;

      *rootaddr     = newroot;

      return SAME;

    case LEFT: /* double rotation */

      half        = root->right;

      newroot     = half->left;

      root->right = newroot->left;

      half->left  = newroot->right;

      switch (newroot->bal) {

      case BAL:

        root->bal = BAL;

        half->bal = BAL;

        break;

      case RIGHT:

        root->bal = LEFT;

        half->bal = BAL;

        break;

      case LEFT:

        root->bal = BAL;

        half->bal = RIGHT;

        break;

      }

      newroot->right = half;

      newroot->left  = root;

      newroot->bal   = BAL;

      *rootaddr      = newroot;

      return LESS;

    }

    break;

  default:

    return SAME;

  }

  return ERROR;

}

/*===========================================================================*/

static int insert_ptr(NODE **rootaddr, NODE *node,

                      int (*usrcmp)(void *, void *), int dup) {

  NODE *root = *rootaddr;

  int cmp;

  int ins;

  SET_PTRCMP(cmp, usrcmp, node->key.ptr, root->key.ptr)

  if (cmp < 0) {

    if (root->left)

      ins = insert_ptr(&root->left, node, usrcmp, dup);

    else {

      root->left = node;

      ins        = DEEPER;

    }

    switch (ins) {

    case DEEPER:

      switch (root->bal) {

      case RIGHT:

        root->bal = BAL;

        return INS;

      case BAL:

        root->bal = LEFT;

        return DEEPER;

      case LEFT:

        root->bal = LEFTUNBAL;

        return rebalance(rootaddr) == LESS ? INS : DEEPER;

      }

      break;

    case INS:

      return INS;

    case NOTINS:

      return NOTINS;

    }

  } else if (cmp > 0 || dup) {

    if (root->right)

      ins = insert_ptr(&root->right, node, usrcmp, dup);

    else {

      root->right = node;

      ins         = DEEPER;

    }

    switch (ins) {

    case DEEPER:

      switch (root->bal) {

      case LEFT:

        root->bal = BAL;

        return INS;

      case BAL:

        root->bal = RIGHT;

        return DEEPER;

      case RIGHT:

        root->bal = RIGHTUNBAL;

        return rebalance(rootaddr) == LESS ? INS : DEEPER;

      }

      break;

    case INS:

      return INS;

    case NOTINS:

      return NOTINS;

    }

  }

  return NOTINS;

}

/*---------------------------------------------------------------------------*/

static int insert_val(NODE **rootaddr, NODE *node, int dup) {

  NODE *root = *rootaddr;

  int ins;

  if (node->key.val < root->key.val) {

    if (root->left)

      ins = insert_val(&root->left, node, dup);

    else {

      root->left = node;

      ins        = DEEPER;

    }

    switch (ins) {

    case DEEPER:

      switch (root->bal) {

      case RIGHT:

        root->bal = BAL;

        return INS;

      case BAL:

        root->bal = LEFT;

        return DEEPER;

      case LEFT:

        root->bal = LEFTUNBAL;

        return rebalance(rootaddr) == LESS ? INS : DEEPER;

      }

      break;

    case INS:

      return INS;

    case NOTINS:

      return NOTINS;

    }

  } else if (node->key.val > root->key.val || dup) {

    if (root->right) {

      ins = insert_val(&root->right, node, dup);

    } else {

      root->right = node;

      ins         = DEEPER;

    }

    switch (ins) {

    case DEEPER:

      switch (root->bal) {

      case LEFT:

        root->bal = BAL;

        return INS;

      case BAL:

        root->bal = RIGHT;

        return DEEPER;

      case RIGHT:

        root->bal = RIGHTUNBAL;

        return rebalance(rootaddr) == LESS ? INS : DEEPER;

      }

    case INS:

      return INS;

    case NOTINS:

      return NOTINS;

    }

  }

  return NOTINS;

}

/*---------------------------------------------------------------------------*/

int avl_insert(TREE *tree, void *data) {

  NODE *node;

  int keyinfo;

  int ins;

  ALLOC_NODE(node)

  if (!node) return FALSE;

  node->data  = data;

  node->left  = NIL;

  node->right = NIL;

  node->bal   = BAL;

  keyinfo     = tree->keyinfo;

  switch (KEYTYPE(keyinfo)) {

  case MBR_KEY:

    node->key.ptr = (void *)((char *)data + tree->keyoffs);

    break;

  case PTR_KEY:

    node->key.ptr = *(void **)((char *)data + tree->keyoffs);

    break;

  case STR_KEY:

    node->key.ptr = *(void **)((char *)data + tree->keyoffs);

    break;

  case LNG_KEY:

    node->key.val = *(long *)((char *)data + tree->keyoffs);

    break;

  case INT_KEY:

    node->key.val = *(int *)((char *)data + tree->keyoffs);

    break;

  case SHT_KEY:

    node->key.val = *(short *)((char *)data + tree->keyoffs);

    break;

  case ULN_KEY:

    node->key.val = CORRECT(*(ulong *)((char *)data + tree->keyoffs));

    break;

  case UIN_KEY:

    node->key.val = CORRECT(*(uint *)((char *)data + tree->keyoffs));

    break;

  case USH_KEY:

    node->key.val = *(ushort *)((char *)data + tree->keyoffs);

    break;

  case CHR_KEY:

    node->key.val = *((char *)data + tree->keyoffs);

    break;

  default:

    FREE_NODE(node)

    return FALSE;

  }

  if (tree->root) {

    switch (LOCTYPE(keyinfo)) {

    case USR_NODUP:

      ins = insert_ptr(&tree->root, node, tree->usrcmp, NODUP);

      break;

    case STR_NODUP:

      ins = insert_ptr(&tree->root, node, AVL_AVLCMP, NODUP);

      break;

    case COR_NODUP:

    case VAL_NODUP:

      ins = insert_val(&tree->root, node, NODUP);

      break;

    case USR_DUP:

      ins = insert_ptr(&tree->root, node, tree->usrcmp, DUP);

      break;

    case STR_DUP:

      ins = insert_ptr(&tree->root, node, AVL_AVLCMP, DUP);

      break;

    case COR_DUP:

    case VAL_DUP:

      ins = insert_val(&tree->root, node, DUP);

      break;

    }

    if (ins == NOTINS) {

      FREE_NODE(node)

      return FALSE;

    }

  } else {

    tree->root = node;

  }

  tree->nodes++;

  if (tree->path) {

    FREE_PATH(tree->path)

    tree->path = NIL;

  }

  return TRUE;

}

/*===========================================================================*/

#define SELECT_EQ_NODUP(node, val, this)                                       \

  {                                                                            \

    if (this < val)                                                            \

      node = node->right;                                                      \

    else if (val < this)                                                       \

      node = node->left;                                                       \

    else                                                                       \

      return node->data;                                                       \

  }

#define SELECT_EQ_DUP(node, val, this, save)                                   \

  {                                                                            \

    if (this < val)                                                            \

      node = node->right;                                                      \

    else if (val < this)                                                       \

      node = node->left;                                                       \

    else {                                                                     \

      save = node;                                                             \

      node = node->left;                                                       \

    }                                                                          \

  }

#define SELECT_GE_NODUP(node, val, this, save)                                 \

  {                                                                            \

    if (val < this) {                                                          \

      save = node;                                                             \

      node = node->left;                                                       \

    } else if (this < val)                                                     \

      node = node->right;                                                      \

    else                                                                       \

      return node->data;                                                       \

  }

#define SELECT_GE_DUP(node, val, this, save)                                   \

  {                                                                            \

    if (this < val)                                                            \

      node = node->right;                                                      \

    else {                                                                     \

      save = node;                                                             \

      node = node->left;                                                       \

    }                                                                          \

  }

#define SELECT_GT(node, val, this, save)                                       \

  {                                                                            \

    if (val < this) {                                                          \

      save = node;                                                             \

      node = node->left;                                                       \

    } else                                                                     \

      node = node->right;                                                      \

  }

#define SELECT_LE_NODUP(node, val, this, save)                                 \

  {                                                                            \

    if (this < val) {                                                          \

      save = node;                                                             \

      node = node->right;                                                      \

    } else if (val < this)                                                     \

      node = node->left;                                                       \

    else                                                                       \

      return node->data;                                                       \

  }

#define SELECT_LE_DUP(node, val, this, save)                                   \

  {                                                                            \

    if (val < this)                                                            \

      node = node->left;                                                       \

    else {                                                                     \

      save = node;                                                             \

      node = node->right;                                                      \

    }                                                                          \

  }

#define SELECT_LT(node, val, this, save)                                       \

  {                                                                            \

    if (this < val) {                                                          \

      save = node;                                                             \

      node = node->right;                                                      \

    } else                                                                     \

      node = node->left;                                                       \

  }

/*---------------------------------------------------------------------------*/

void *avl__locate(TREE *tree, long keyval) {

  NODE *node;

  NODE *save;

  int (*usrcmp)(void *, void *);

  int cmp;

  node = tree->root;

  switch (LOCTYPE(tree->keyinfo)) {

  case USR_NODUP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_EQ_NODUP(node, cmp, 0);

    }

    break;

  case STR_NODUP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_EQ_NODUP(node, cmp, 0);

    }

    break;

  case COR_NODUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_NODUP:

    while (node) {

      SELECT_EQ_NODUP(node, keyval, node->key.val);

    }

    break;

  case USR_DUP:

    save   = NIL;

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_EQ_DUP(node, cmp, 0, save);

    }

    if (save) {

      return save->data;

    }

    break;

  case STR_DUP:

    save = NIL;

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_EQ_DUP(node, cmp, 0, save);

    }

    if (save) {

      return save->data;

    }

    break;

  case COR_DUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_DUP:

    save = NIL;

    while (node) {

      SELECT_EQ_DUP(node, keyval, node->key.val, save);

    }

    if (save) {

      return save->data;

    }

    break;

  }

  return NIL;

}

/*---------------------------------------------------------------------------*/

void *avl__locate_ge(TREE *tree, long keyval) {

  NODE *node;

  NODE *save;

  int (*usrcmp)(void *, void *);

  int cmp;

  node = tree->root;

  save = NIL;

  switch (LOCTYPE(tree->keyinfo)) {

  case USR_NODUP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_GE_NODUP(node, cmp, 0, save);

    }

    break;

  case STR_NODUP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_GE_NODUP(node, cmp, 0, save);

    }

    break;

  case COR_NODUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_NODUP:

    while (node) {

      SELECT_GE_NODUP(node, keyval, node->key.val, save);

    }

    break;

  case USR_DUP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_GE_DUP(node, cmp, 0, save);

    }

    break;

  case STR_DUP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_GE_DUP(node, cmp, 0, save);

    }

    break;

  case COR_DUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_DUP:

    while (node) {

      SELECT_GE_DUP(node, keyval, node->key.val, save);

    }

    break;

  }

  return save ? save->data : NIL;

}

/*---------------------------------------------------------------------------*/

void *avl__locate_gt(TREE *tree, long keyval) {

  NODE *node;

  NODE *save;

  int (*usrcmp)(void *, void *);

  int cmp;

  node = tree->root;

  save = NIL;

  switch (CMPTYPE(tree->keyinfo)) {

  case USR_CMP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_GT(node, cmp, 0, save);

    }

    break;

  case STR_CMP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_GT(node, cmp, 0, save);

    }

    break;

  case COR_CMP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_CMP:

    while (node) {

      SELECT_GT(node, keyval, node->key.val, save);

    }

    break;

  }

  return save ? save->data : NIL;

}

/*---------------------------------------------------------------------------*/

void *avl__locate_le(TREE *tree, long keyval) {

  NODE *node;

  NODE *save;

  int (*usrcmp)(void *, void *);

  int cmp;

  node = tree->root;

  save = NIL;

  switch (LOCTYPE(tree->keyinfo)) {

  case USR_NODUP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_LE_NODUP(node, cmp, 0, save);

    }

    break;

  case STR_NODUP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_LE_NODUP(node, cmp, 0, save);

    }

    break;

  case COR_NODUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_NODUP:

    while (node) {

      SELECT_LE_NODUP(node, keyval, node->key.val, save);

    }

    break;

  case USR_DUP:

    usrcmp = tree->usrcmp;

    while (node) {

      cmp = (*usrcmp)((void *)keyval, node->key.ptr);

      SELECT_LE_DUP(node, cmp, 0, save);

    }

    break;

  case STR_DUP:

    while (node) {

      SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr);

      SELECT_LE_DUP(node, cmp, 0, save);

    }

    break;

  case COR_DUP:

    keyval = CORRECT(keyval);

  // fallthrough

  case VAL_DUP:

    while (node) {

      SELECT_LE_DUP(node, keyval, node->key.val, save);

    }

    break;

  }

  return save ? save->data : NIL;

}

/*---------------------------------------------------------------------------*/

void *avl__locate_lt(TREE *tree, long keyval) {