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 */ 127