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