/*
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 * the AT&T man page says.
 *
 * The node_t structure is for internal use only, lint doesn't grok it.
 *
 * Written by reading the System V Interface Definition, not the code.
 *
 * Totally public domain.
 */

#include "tsearch.h"
#include <stdlib.h>


typedef struct node
{
  const void   *key;
  struct node  *llink;
  struct node  *rlink;
} node_t;


/*	$NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $	*/
/* find or insert datum into search tree */
void *
tsearch (const void *vkey,  /* key to be located */
         void **vrootp,     /* address of tree root */
         int (*compar)(const void *, const void *))
{
  node_t *q;
  node_t **rootp = (node_t **) vrootp;

  if (NULL == rootp)
    return NULL;

  while (*rootp != NULL)
  {   /* Knuth's T1: */
    int r;

    if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
      return *rootp;                               /* we found it! */

    rootp = (r < 0) ?
            &(*rootp)->llink : /* T3: follow left branch */
            &(*rootp)->rlink; /* T4: follow right branch */
  }

  q = malloc (sizeof(node_t)); /* T5: key not found */
  if (q)
  {                            /* make new node */
    *rootp = q;                /* link new node to old */
    q->key = vkey;             /* initialize new node */
    q->llink = q->rlink = NULL;
  }
  return q;
}


/*	$NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $	*/
/* find a node, or return NULL */
void *
tfind (const void *vkey,         /* key to be found */
       void *const *vrootp,      /* address of the tree root */
       int (*compar)(const void *, const void *))
{
  node_t *const *rootp = (node_t *const *) vrootp;

  if (NULL == rootp)
    return NULL;

  while (*rootp != NULL)
  {     /* T1: */
    int r;

    if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
      return *rootp;                               /* key found */
    rootp = (r < 0) ?
            &(*rootp)->llink : /* T3: follow left branch */
            &(*rootp)->rlink; /* T4: follow right branch */
  }
  return NULL;
}


/*	$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $	*/
/*
 * delete node with given key
 *
 * vkey:   key to be deleted
 * vrootp: address of the root of the tree
 * compar: function to carry out node comparisons
 */
void *
tdelete (const void *__restrict vkey,
         void **__restrict vrootp,
         int (*compar)(const void *, const void *))
{
  node_t **rootp = (node_t **) vrootp;
  node_t *p;
  node_t *q;
  node_t *r;
  int cmp;

  if ((rootp == NULL) || ((p = *rootp) == NULL))
    return NULL;

  while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
  {
    p = *rootp;
    rootp = (cmp < 0) ?
            &(*rootp)->llink : /* follow llink branch */
            &(*rootp)->rlink; /* follow rlink branch */
    if (*rootp == NULL)
      return NULL;                   /* key not found */
  }
  r = (*rootp)->rlink;               /* D1: */
  if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
  {
    q = r;
  }
  else if (r != NULL)
  {       /* Right link is NULL? */
    if (r->llink == NULL)
    {     /* D2: Find successor */
      r->llink = q;
      q = r;
    }
    else
    {         /* D3: Find NULL link */
      for (q = r->llink; q->llink != NULL; q = r->llink)
        r = q;
      r->llink = q->rlink;
      q->llink = (*rootp)->llink;
      q->rlink = (*rootp)->rlink;
    }
  }
  free (*rootp);    /* D4: Free node */
  *rootp = q;       /* link parent to new node */
  return p;
}


/* end of tsearch.c */