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
36extern "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 */
55typedef 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
61typedef 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 */
72typedef	struct str_master	Str_master;
73
74struct 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 */
87typedef	struct str_hash	Str_hash;
88
89struct 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 */
100struct 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