src/libafscp/afscp_roken.c

   1 /*
   2  * Copyright (c) 1995 - 1999 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /* this file can go away when roken appears in this branch */
  35 #include <afsconfig.h>
  36 #include "afscp.h"
  37 #include "afscp_internal.h"
  38
  39 #ifdef ROKEN_LIB_FUNCTION
  40 #error this file can go away when roken appears in this branch
  41 #endif
  42
  43 #ifdef _WIN32
  44 #define ROKEN_LIB_FUNCTION
  45 #define ROKEN_LIB_CALL     __cdecl
  46 #else
  47 #define ROKEN_LIB_FUNCTION
  48 #define ROKEN_LIB_CALL
  49 #endif
  50
  51 #ifndef HAVE_STRNLEN
  52 ROKEN_LIB_FUNCTION size_t ROKEN_LIB_CALL
  53 strnlen(const char *s, size_t len)
  54 {
  55     size_t i;
  56
  57     for(i = 0; i < len && s[i]; i++)
  58         ;
  59     return i;
  60 }
  61 #endif
  62
  63 #ifndef HAVE_TSEARCH
  64 /*
  65  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  66  * the AT&T man page says.
  67  *
  68  * The node_t structure is for internal use only, lint doesn't grok it.
  69  *
  70  * Written by reading the System V Interface Definition, not the code.
  71  *
  72  * Totally public domain.
  73  *
  74  * $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $
  75  * $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $
  76  * $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
  77  * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
  78  */
  79
  80 #include <stdlib.h>
  81 #include <sys/types.h>
  82 #include "afscp_search.h"
  83
  84 typedef struct node {
  85   char         *key;
  86   struct node  *llink, *rlink;
  87 } node_t;
  88
  89 #ifndef __DECONST
  90 #define __DECONST(type, var)    ((type)(uintptr_t)(const void *)(var))
  91 #endif
  92
  93 /*
  94  * find or insert datum into search tree
  95  *
  96  * Parameters:
  97  *      vkey:   key to be located
  98  *      vrootp: address of tree root
  99  */
 100
 101 ROKEN_LIB_FUNCTION void *
 102 rk_tsearch(const void *vkey, void **vrootp,
 103         int (*compar)(const void *, const void *))
 104 {
 105         node_t *q;
 106         node_t **rootp = (node_t **)vrootp;
 107
 108         if (rootp == NULL)
 109                 return NULL;
 110
 111         while (*rootp != NULL) {        /* Knuth's T1: */
 112                 int r;
 113
 114                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
 115                         return *rootp;          /* we found it! */
 116
 117                 rootp = (r < 0) ?
 118                     &(*rootp)->llink :          /* T3: follow left branch */
 119                     &(*rootp)->rlink;           /* T4: follow right branch */
 120         }
 121
 122         q = malloc(sizeof(node_t));             /* T5: key not found */
 123         if (q != 0) {                           /* make new node */
 124                 *rootp = q;                     /* link new node to old */
 125                 /* LINTED const castaway ok */
 126                 q->key = __DECONST(void *, vkey); /* initialize new node */
 127                 q->llink = q->rlink = NULL;
 128         }
 129         return q;
 130 }
 131
 132 /*
 133  * Walk the nodes of a tree
 134  *
 135  * Parameters:
 136  *      root:   Root of the tree to be walked
 137  */
 138 static void
 139 trecurse(const node_t *root, void (*action)(const void *, VISIT, int),
 140          int level)
 141 {
 142
 143         if (root->llink == NULL && root->rlink == NULL)
 144                 (*action)(root, leaf, level);
 145         else {
 146                 (*action)(root, preorder, level);
 147                 if (root->llink != NULL)
 148                         trecurse(root->llink, action, level + 1);
 149                 (*action)(root, postorder, level);
 150                 if (root->rlink != NULL)
 151                         trecurse(root->rlink, action, level + 1);
 152                 (*action)(root, endorder, level);
 153         }
 154 }
 155
 156 /*
 157  * Walk the nodes of a tree
 158  *
 159  * Parameters:
 160  *      vroot:  Root of the tree to be walked
 161  */
 162 ROKEN_LIB_FUNCTION void
 163 rk_twalk(const void *vroot,
 164       void (*action)(const void *, VISIT, int))
 165 {
 166         if (vroot != NULL && action != NULL)
 167                 trecurse(vroot, action, 0);
 168 }
 169
 170 /*
 171  * delete node with given key
 172  *
 173  * vkey:   key to be deleted
 174  * vrootp: address of the root of the tree
 175  * compar: function to carry out node comparisons
 176  */
 177 ROKEN_LIB_FUNCTION void *
 178 rk_tdelete(const void * __restrict vkey, void ** __restrict vrootp,
 179         int (*compar)(const void *, const void *))
 180 {
 181         node_t **rootp = (node_t **)vrootp;
 182         node_t *p, *q, *r;
 183         int cmp;
 184
 185         if (rootp == NULL || (p = *rootp) == NULL)
 186                 return NULL;
 187
 188         while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
 189                 p = *rootp;
 190                 rootp = (cmp < 0) ?
 191                     &(*rootp)->llink :          /* follow llink branch */
 192                     &(*rootp)->rlink;           /* follow rlink branch */
 193                 if (*rootp == NULL)
 194                         return NULL;            /* key not found */
 195         }
 196         r = (*rootp)->rlink;                    /* D1: */
 197         if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
 198                 q = r;
 199         else if (r != NULL) {                   /* Right link is NULL? */
 200                 if (r->llink == NULL) {         /* D2: Find successor */
 201                         r->llink = q;
 202                         q = r;
 203                 } else {                        /* D3: Find NULL link */
 204                         for (q = r->llink; q->llink != NULL; q = r->llink)
 205                                 r = q;
 206                         r->llink = q->rlink;
 207                         q->llink = (*rootp)->llink;
 208                         q->rlink = (*rootp)->rlink;
 209                 }
 210         }
 211         free(*rootp);                           /* D4: Free node */
 212         *rootp = q;                             /* link parent to new node */
 213         return p;
 214 }
 215
 216 /*
 217  * find a node, or return 0
 218  *
 219  * Parameters:
 220  *      vkey:   key to be found
 221  *      vrootp: address of the tree root
 222  */
 223 ROKEN_LIB_FUNCTION void *
 224 rk_tfind(const void *vkey, void * const *vrootp,
 225       int (*compar)(const void *, const void *))
 226 {
 227         node_t **rootp = (node_t **)vrootp;
 228
 229         if (rootp == NULL)
 230                 return NULL;
 231
 232         while (*rootp != NULL) {                /* T1: */
 233                 int r;
 234
 235                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
 236                         return *rootp;          /* key found */
 237                 rootp = (r < 0) ?
 238                     &(*rootp)->llink :          /* T3: follow left branch */
 239                     &(*rootp)->rlink;           /* T4: follow right branch */
 240         }
 241         return NULL;
 242 }
 243 #endif