Blame src/microhttpd/tsearch.c

Packit 875988
/*
Packit 875988
 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
Packit 875988
 * the AT&T man page says.
Packit 875988
 *
Packit 875988
 * The node_t structure is for internal use only, lint doesn't grok it.
Packit 875988
 *
Packit 875988
 * Written by reading the System V Interface Definition, not the code.
Packit 875988
 *
Packit 875988
 * Totally public domain.
Packit 875988
 */
Packit 875988
Packit 875988
#include "tsearch.h"
Packit 875988
#include <stdlib.h>
Packit 875988
Packit 875988
Packit 875988
typedef	struct node
Packit 875988
{
Packit 875988
  const void   *key;
Packit 875988
  struct node  *llink;
Packit 875988
  struct node  *rlink;
Packit 875988
} node_t;
Packit 875988
Packit 875988
Packit 875988
/*	$NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $	*/
Packit 875988
/* find or insert datum into search tree */
Packit 875988
void *
Packit 875988
tsearch (const void *vkey,		/* key to be located */
Packit 875988
         void **vrootp,			/* address of tree root */
Packit 875988
         int (*compar)(const void *, const void *))
Packit 875988
{
Packit 875988
  node_t *q;
Packit 875988
  node_t **rootp = (node_t **)vrootp;
Packit 875988
Packit 875988
  if (NULL == rootp)
Packit 875988
    return NULL;
Packit 875988
Packit 875988
  while (*rootp != NULL)
Packit 875988
    {	/* Knuth's T1: */
Packit 875988
      int r;
Packit 875988
Packit 875988
      if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
Packit 875988
        return *rootp;		/* we found it! */
Packit 875988
Packit 875988
      rootp = (r < 0) ?
Packit 875988
        &(*rootp)->llink :		/* T3: follow left branch */
Packit 875988
        &(*rootp)->rlink;		/* T4: follow right branch */
Packit 875988
    }
Packit 875988
Packit 875988
  q = malloc (sizeof(node_t));		/* T5: key not found */
Packit 875988
  if (q)
Packit 875988
    {				/* make new node */
Packit 875988
      *rootp = q;			/* link new node to old */
Packit 875988
      q->key = vkey;		/* initialize new node */
Packit 875988
      q->llink = q->rlink = NULL;
Packit 875988
    }
Packit 875988
  return q;
Packit 875988
}
Packit 875988
Packit 875988
Packit 875988
/*	$NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $	*/
Packit 875988
/* find a node, or return NULL */
Packit 875988
void *
Packit 875988
tfind (const void *vkey,         /* key to be found */
Packit 875988
       void * const *vrootp,     /* address of the tree root */
Packit 875988
       int (*compar)(const void *, const void *))
Packit 875988
{
Packit 875988
  node_t * const *rootp = (node_t * const*)vrootp;
Packit 875988
Packit 875988
  if (NULL == rootp)
Packit 875988
    return NULL;
Packit 875988
Packit 875988
  while (*rootp != NULL)
Packit 875988
    {		/* T1: */
Packit 875988
      int r;
Packit 875988
Packit 875988
      if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
Packit 875988
        return *rootp;		/* key found */
Packit 875988
      rootp = (r < 0) ?
Packit 875988
        &(*rootp)->llink :		/* T3: follow left branch */
Packit 875988
        &(*rootp)->rlink;		/* T4: follow right branch */
Packit 875988
    }
Packit 875988
  return NULL;
Packit 875988
}
Packit 875988
Packit 875988
Packit 875988
/*	$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $	*/
Packit 875988
/*
Packit 875988
 * delete node with given key
Packit 875988
 *
Packit 875988
 * vkey:   key to be deleted
Packit 875988
 * vrootp: address of the root of the tree
Packit 875988
 * compar: function to carry out node comparisons
Packit 875988
 */
Packit 875988
void *
Packit 875988
tdelete (const void * __restrict vkey,
Packit 875988
         void ** __restrict vrootp,
Packit 875988
         int (*compar)(const void *, const void *))
Packit 875988
{
Packit 875988
  node_t **rootp = (node_t **)vrootp;
Packit 875988
  node_t *p;
Packit 875988
  node_t *q;
Packit 875988
  node_t *r;
Packit 875988
  int cmp;
Packit 875988
Packit 875988
  if (rootp == NULL || (p = *rootp) == NULL)
Packit 875988
    return NULL;
Packit 875988
Packit 875988
  while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
Packit 875988
    {
Packit 875988
      p = *rootp;
Packit 875988
      rootp = (cmp < 0) ?
Packit 875988
        &(*rootp)->llink :		/* follow llink branch */
Packit 875988
        &(*rootp)->rlink;		/* follow rlink branch */
Packit 875988
      if (*rootp == NULL)
Packit 875988
        return NULL;		/* key not found */
Packit 875988
    }
Packit 875988
  r = (*rootp)->rlink;			/* D1: */
Packit 875988
  if ((q = (*rootp)->llink) == NULL)	/* Left NULL? */
Packit 875988
    {
Packit 875988
      q = r;
Packit 875988
    }
Packit 875988
  else if (r != NULL)
Packit 875988
    {			/* Right link is NULL? */
Packit 875988
      if (r->llink == NULL)
Packit 875988
        {		/* D2: Find successor */
Packit 875988
          r->llink = q;
Packit 875988
          q = r;
Packit 875988
        }
Packit 875988
      else
Packit 875988
        {			/* D3: Find NULL link */
Packit 875988
          for (q = r->llink; q->llink != NULL; q = r->llink)
Packit 875988
            r = q;
Packit 875988
          r->llink = q->rlink;
Packit 875988
          q->llink = (*rootp)->llink;
Packit 875988
          q->rlink = (*rootp)->rlink;
Packit 875988
        }
Packit 875988
    }
Packit 875988
  free(*rootp);				/* D4: Free node */
Packit 875988
  *rootp = q;				/* link parent to new node */
Packit 875988
  return p;
Packit 875988
}
Packit 875988
Packit 875988
/* end of tsearch.c */