From 20f2f23be6cd5834997cb22ae2bbf4bec308c60c Mon Sep 17 00:00:00 2001 From: Heimdal Developers Date: Sat, 9 Apr 2011 09:46:26 -0400 Subject: [PATCH] Import of code from heimdal This commit updates the code imported from heimdal to 2a32bf67f0a7c77b6adf6e7c23ec8abe7937a9ea (switch-from-svn-to-git-2067-g2a32bf6) Upstream changes are: Derrick Brashear (1): Add tsearch and friends, and a test program New files are: roken/search.hin roken/tsearch.c Change-Id: Ie7ddb2da595797ca354e36776ce813a03b3d462c Reviewed-on: http://gerrit.openafs.org/4453 Reviewed-by: Derrick Brashear Tested-by: Derrick Brashear --- src/external/heimdal-last | 2 +- src/external/heimdal/roken/roken.h.in | 12 ++ src/external/heimdal/roken/search.hin | 42 ++++++ src/external/heimdal/roken/tsearch.c | 180 ++++++++++++++++++++++++++ 4 files changed, 235 insertions(+), 1 deletion(-) create mode 100644 src/external/heimdal/roken/search.hin create mode 100644 src/external/heimdal/roken/tsearch.c diff --git a/src/external/heimdal-last b/src/external/heimdal-last index 581f02f5f..48c5ad9ce 100644 --- a/src/external/heimdal-last +++ b/src/external/heimdal-last @@ -1 +1 @@ -a597ccdde692709ab387cde21518f09eb501c5a1 +2a32bf67f0a7c77b6adf6e7c23ec8abe7937a9ea diff --git a/src/external/heimdal/roken/roken.h.in b/src/external/heimdal/roken/roken.h.in index 6051427ab..e2da87194 100644 --- a/src/external/heimdal/roken/roken.h.in +++ b/src/external/heimdal/roken/roken.h.in @@ -1099,6 +1099,18 @@ rk_qsort(void *, size_t, size_t, int (*)(const void *, const void *)); #define rk_random() rand() #endif +#ifndef HAVE_TDELETE +#define tdelete(a,b,c) rk_tdelete(a,b,c) +#endif +#ifndef HAVE_TFIND +#define tfind(a,b,c) rk_tfind(a,b,c) +#endif +#ifndef HAVE_TSEARCH +#define tsearch(a,b,c) rk_tsearch(a,b,c) +#endif +#ifndef HAVE_TWALK +#define twalk(a,b) rk_twalk(a,b) +#endif #if defined(__linux__) && defined(SOCK_CLOEXEC) && !defined(SOCKET_WRAPPER_REPLACE) && !defined(__SOCKET_WRAPPER_H__) #undef socket diff --git a/src/external/heimdal/roken/search.hin b/src/external/heimdal/roken/search.hin new file mode 100644 index 000000000..9e45c2a9e --- /dev/null +++ b/src/external/heimdal/roken/search.hin @@ -0,0 +1,42 @@ +/*- + * Written by J.T. Conklin + * Public domain. + * + * $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ + */ + +#ifndef _rk_SEARCH_H_ +#define _rk_SEARCH_H_ 1 + +#ifndef ROKEN_LIB_FUNCTION +#ifdef _WIN32 +#define ROKEN_LIB_FUNCTION +#define ROKEN_LIB_CALL __cdecl +#else +#define ROKEN_LIB_FUNCTION +#define ROKEN_LIB_CALL +#endif +#endif + +#include +#include + +typedef enum { + preorder, + postorder, + endorder, + leaf +} VISIT; + +ROKEN_CPP_START + +ROKEN_LIB_FUNCTION void * ROKEN_LIB_CALL rk_tdelete(const void * __restrict, void ** __restrict, + int (*)(const void *, const void *)); +ROKEN_LIB_FUNCTION void * ROKEN_LIB_CALL rk_tfind(const void *, void * const *, + int (*)(const void *, const void *)); +ROKEN_LIB_FUNCTION void * ROKEN_LIB_CALL rk_tsearch(const void *, void **, int (*)(const void *, const void *)); +ROKEN_LIB_FUNCTION void ROKEN_LIB_CALL rk_twalk(const void *, void (*)(const void *, VISIT, int)); + +ROKEN_CPP_END + +#endif /* !_rk_SEARCH_H_ */ diff --git a/src/external/heimdal/roken/tsearch.c b/src/external/heimdal/roken/tsearch.c new file mode 100644 index 000000000..c51a64339 --- /dev/null +++ b/src/external/heimdal/roken/tsearch.c @@ -0,0 +1,180 @@ +/* + * 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. + * + * $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ + * $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $ + * $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ + * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ + */ + +#include +#include "roken.h" +#include "search.h" +#include + +typedef struct node { + char *key; + struct node *llink, *rlink; +} node_t; + +#ifndef __DECONST +#define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var)) +#endif + +/* + * find or insert datum into search tree + * + * Parameters: + * vkey: key to be located + * vrootp: address of tree root + */ + +ROKEN_LIB_FUNCTION void * +rk_tsearch(const void *vkey, void **vrootp, + int (*compar)(const void *, const void *)) +{ + node_t *q; + node_t **rootp = (node_t **)vrootp; + + if (rootp == NULL) + 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 != 0) { /* make new node */ + *rootp = q; /* link new node to old */ + /* LINTED const castaway ok */ + q->key = __DECONST(void *, vkey); /* initialize new node */ + q->llink = q->rlink = NULL; + } + return q; +} + +/* + * Walk the nodes of a tree + * + * Parameters: + * root: Root of the tree to be walked + */ +static void +trecurse(const node_t *root, void (*action)(const void *, VISIT, int), + int level) +{ + + if (root->llink == NULL && root->rlink == NULL) + (*action)(root, leaf, level); + else { + (*action)(root, preorder, level); + if (root->llink != NULL) + trecurse(root->llink, action, level + 1); + (*action)(root, postorder, level); + if (root->rlink != NULL) + trecurse(root->rlink, action, level + 1); + (*action)(root, endorder, level); + } +} + +/* + * Walk the nodes of a tree + * + * Parameters: + * vroot: Root of the tree to be walked + */ +ROKEN_LIB_FUNCTION void +rk_twalk(const void *vroot, + void (*action)(const void *, VISIT, int)) +{ + if (vroot != NULL && action != NULL) + trecurse(vroot, action, 0); +} + +/* + * 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 + */ +ROKEN_LIB_FUNCTION void * +rk_tdelete(const void * __restrict vkey, void ** __restrict vrootp, + int (*compar)(const void *, const void *)) +{ + node_t **rootp = (node_t **)vrootp; + node_t *p, *q, *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; +} + +/* + * find a node, or return 0 + * + * Parameters: + * vkey: key to be found + * vrootp: address of the tree root + */ +ROKEN_LIB_FUNCTION void * +rk_tfind(const void *vkey, void * const *vrootp, + int (*compar)(const void *, const void *)) +{ + node_t **rootp = (node_t **)vrootp; + + if (rootp == NULL) + 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; +} -- 2.39.5