usr/src/cmd/sgs/include/_string_table.h

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #ifndef __STRING_TABLE_DOT_H
  27 #define __STRING_TABLE_DOT_H
  28
  29 #pragma ident   "%Z%%M% %I%     %E% SMI"
  30
  31 #include <sys/types.h>
  32 #include <sys/avl.h>
  33 #include <string_table.h>
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 /*
  40  * A string is represented in a string table using two values: length, and
  41  * value.  Grouping all the strings of a given length together allows for
  42  * efficient matching of tail strings, as each input string value is hashed.
  43  * Each string table uses a 2-level AVL tree of AVL trees to represent this
  44  * organization.
  45  *
  46  * The outer (main) AVL tree contains LenNode structures.  The search key for
  47  * nodes on this main tree is the string length.  Each such node represents
  48  * all strings of a given length, and all strings of that length are found
  49  * within.
  50  *
  51  * The strings within each LenNode are maintained using a secondary AVL tree
  52  * of StrNode structures.  The search key for this inner tree is the string
  53  * itself.  The strings are maintained in lexical order.
  54  */
  55 typedef struct {
  56         avl_node_t      sn_avlnode;     /* AVL book-keeping */
  57         const char      *sn_str;        /* string */
  58         size_t          sn_refcnt;      /* reference count */
  59 } StrNode;
  60
  61 typedef struct {
  62         avl_node_t      ln_avlnode;     /* AVL book-keeping */
  63         avl_tree_t      *ln_strtree;    /* AVL tree of associated strings */
  64         size_t          ln_strlen;      /* length of associated strings */
  65 } LenNode;
  66
  67 /*
  68  * Define a master string data item.  Other strings may be suffixes of this
  69  * string.  The final string table will consist of the master string values,
  70  * laid end to end, with the other strings referencing their tails.
  71  */
  72 typedef struct str_master       Str_master;
  73
  74 struct str_master {
  75         const char      *sm_str;        /* pointer to master string */
  76         Str_master      *sm_next;       /* used for tracking master strings */
  77         size_t          sm_strlen;      /* length of master string */
  78         uint_t          sm_hashval;     /* hashval of master string */
  79         size_t          sm_stroff;      /* offset into destination strtab */
  80 };
  81
  82 /*
  83  * Define a hash data item.  This item represents an individual string that has
  84  * been input into the String hash table.  The string may either be a suffix of
  85  * another string, or a master string.
  86  */
  87 typedef struct str_hash Str_hash;
  88
  89 struct str_hash {
  90         size_t          hi_strlen;      /* string length */
  91         size_t          hi_refcnt;      /* number of references to str */
  92         uint_t          hi_hashval;     /* hash for string */
  93         Str_master      *hi_mstr;       /* pointer to master string */
  94         Str_hash        *hi_next;       /* next entry in hash bucket */
  95 };
  96
  97 /*
  98  * Controlling data structure for a String Table.
  99  */
 100 struct str_tbl {
 101         avl_tree_t      *st_lentree;            /* AVL tree of string lengths */
 102         char            *st_strbuf;             /* string buffer */
 103         Str_hash        **st_hashbcks;          /* hash buckets */
 104         Str_master      *st_mstrlist;           /* list of all master strings */
 105         size_t          st_fullstrsize;         /* uncompressed table size */
 106         size_t          st_nextoff;             /* next available string */
 107         size_t          st_strsize;             /* compressed size */
 108         size_t          st_strcnt;              /* number of strings */
 109         uint_t          st_hbckcnt;             /* number of buckets in */
 110                                                 /*    hashlist */
 111         uint_t          st_flags;
 112 };
 113
 114 #define FLG_STTAB_COMPRESS      0x01            /* compressed string table */
 115 #define FLG_STTAB_COOKED        0x02            /* offset has been assigned */
 116
 117 /*
 118  * Starting value for use with string hashing functions inside of string_table.c
 119  */
 120 #define HASHSEED                5381
 121
 122 #ifdef __cplusplus
 123 }
 124 #endif
 125
 126 #endif /* __STRING_TABLE_DOT_H */