cde/programs/dtksh/ksh93/src/lib/libodelta/suftree.h

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: suftree.h /main/3 1995/11/01 19:11:36 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 #ifndef _SUFTREE_H
  50 #if !defined(__PROTO__)
  51 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  52 #if defined(__cplusplus)
  53 #define __MANGLE__      "C"
  54 #else
  55 #define __MANGLE__
  56 #endif
  57 #define __STDARG__
  58 #define __PROTO__(x)    x
  59 #define __OTORP__(x)
  60 #define __PARAM__(n,o)  n
  61 #if !defined(__STDC__) && !defined(__cplusplus)
  62 #if !defined(c_plusplus)
  63 #define const
  64 #endif
  65 #define signed
  66 #define void            int
  67 #define volatile
  68 #define __V_            char
  69 #else
  70 #define __V_            void
  71 #endif
  72 #else
  73 #define __PROTO__(x)    ()
  74 #define __OTORP__(x)    x
  75 #define __PARAM__(n,o)  o
  76 #define __MANGLE__
  77 #define __V_            char
  78 #define const
  79 #define signed
  80 #define void            int
  81 #define volatile
  82 #endif
  83 #if defined(__cplusplus) || defined(c_plusplus)
  84 #define __VARARG__      ...
  85 #else
  86 #define __VARARG__
  87 #endif
  88 #if defined(__STDARG__)
  89 #define __VA_START__(p,a)       va_start(p,a)
  90 #else
  91 #define __VA_START__(p,a)       va_start(p)
  92 #endif
  93 #endif
  94
  95 #define _SUFTREE_H
  96
  97 #include <ast.h>
  98
  99 /* the type of list elements we play with */
 100 typedef char    Element;
 101
 102 /* for suffix trees, a tree node looks like this */
 103 typedef struct _ts_
 104 {
 105         Element         *_label;        /* substring labeling the edge */
 106         long int        _length;        /* the length of the string */
 107         struct _ts_     *_child;        /* list of children */
 108         struct _ts_     *_sibling;      /* link for the child list */
 109         union
 110         {       /* these two fields are mutual exclusive */
 111                 struct _ts_     *_link;         /* sub-link */
 112                 Element         *_suffix;       /* suffix */
 113         }       _uls_;
 114 }       Suftree;
 115
 116 /* short hand for various fields in a tree node */
 117 #define LABEL(n)        ((n)->_label)
 118 #define LENGTH(n)       ((n)->_length)
 119 #define CHILD(n)        ((n)->_child)
 120 #define SIBLING(n)      ((n)->_sibling)
 121 #define LINK(n)         ((n)->_uls_._link)
 122 #define SUFFIX(n)       ((n)->_uls_._suffix)
 123
 124 /* the following definitions are not to be seen by users */
 125 #ifdef _IN_SUF_TREE
 126 #ifdef DEBUG
 127 #define ASSERT(p)       if(!(p)) abort();
 128 #else
 129 #define ASSERT(p)
 130 #endif /*DEBUG*/
 131
 132 #ifndef NULL
 133 #define NULL    (0L)
 134 #endif /*NULL*/
 135
 136 #define ALLOCSIZE       256     /* amount of nodes to allocate each time */
 137 #define NEXT(n)         ((n)->_sibling)
 138
 139 #endif /*_IN_SUF_TREE*/
 140
 141 extern __MANGLE__ Suftree*              bldsuftree __PROTO__((Element*, long));
 142 extern __MANGLE__ void          delsuftree __PROTO__((Suftree*));
 143 extern __MANGLE__ long          mtchsuftree __PROTO__((Suftree*, Element*, long, Element**));
 144
 145 #endif