xref: /onnv-gate/usr/src/cmd/sgs/include/_string_table.h (revision 5549:beb29939b34a)
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