xref: /illumos-gate/usr/src/cmd/sgs/include/_string_table.h (revision 2a8bcb4efb45d99ac41c94a75c396b362c414f7f)
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