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 #include <sys/types.h> 30 #include <sys/avl.h> 31 #include <string_table.h> 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 /* 38 * A string is represented in a string table using two values: length, and 39 * value. Grouping all the strings of a given length together allows for 40 * efficient matching of tail strings, as each input string value is hashed. 41 * Each string table uses a 2-level AVL tree of AVL trees to represent this 42 * organization. 43 * 44 * The outer (main) AVL tree contains LenNode structures. The search key for 45 * nodes on this main tree is the string length. Each such node represents 46 * all strings of a given length, and all strings of that length are found 47 * within. 48 * 49 * The strings within each LenNode are maintained using a secondary AVL tree 50 * of StrNode structures. The search key for this inner tree is the string 51 * itself. The strings are maintained in lexical order. 52 */ 53 typedef struct { 54 avl_node_t sn_avlnode; /* AVL book-keeping */ 55 const char *sn_str; /* string */ 56 size_t sn_refcnt; /* reference count */ 57 } StrNode; 58 59 typedef struct { 60 avl_node_t ln_avlnode; /* AVL book-keeping */ 61 avl_tree_t *ln_strtree; /* AVL tree of associated strings */ 62 size_t ln_strlen; /* length of associated strings */ 63 } LenNode; 64 65 /* 66 * Define a master string data item. Other strings may be suffixes of this 67 * string. The final string table will consist of the master string values, 68 * laid end to end, with the other strings referencing their tails. 69 */ 70 typedef struct str_master Str_master; 71 72 struct str_master { 73 const char *sm_str; /* pointer to master string */ 74 Str_master *sm_next; /* used for tracking master strings */ 75 size_t sm_strlen; /* length of master string */ 76 uint_t sm_hashval; /* hashval of master string */ 77 size_t sm_stroff; /* offset into destination strtab */ 78 }; 79 80 /* 81 * Define a hash data item. This item represents an individual string that has 82 * been input into the String hash table. The string may either be a suffix of 83 * another string, or a master string. 84 */ 85 typedef struct str_hash Str_hash; 86 87 struct str_hash { 88 size_t hi_strlen; /* string length */ 89 size_t hi_refcnt; /* number of references to str */ 90 uint_t hi_hashval; /* hash for string */ 91 Str_master *hi_mstr; /* pointer to master string */ 92 Str_hash *hi_next; /* next entry in hash bucket */ 93 }; 94 95 /* 96 * Controlling data structure for a String Table. 97 */ 98 struct str_tbl { 99 avl_tree_t *st_lentree; /* AVL tree of string lengths */ 100 char *st_strbuf; /* string buffer */ 101 Str_hash **st_hashbcks; /* hash buckets */ 102 Str_master *st_mstrlist; /* list of all master strings */ 103 size_t st_fullstrsize; /* uncompressed table size */ 104 size_t st_nextoff; /* next available string */ 105 size_t st_strsize; /* compressed size */ 106 size_t st_strcnt; /* number of strings */ 107 uint_t st_hbckcnt; /* number of buckets in */ 108 /* hashlist */ 109 uint_t st_flags; 110 }; 111 112 #define FLG_STTAB_COMPRESS 0x01 /* compressed string table */ 113 #define FLG_STTAB_COOKED 0x02 /* offset has been assigned */ 114 115 /* 116 * Starting value for use with string hashing functions inside of string_table.c 117 */ 118 #define HASHSEED 5381 119 120 #ifdef __cplusplus 121 } 122 #endif 123 124 #endif /* __STRING_TABLE_DOT_H */ 125