aboutsummaryrefslogtreecommitdiff
path: root/cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h
diff options
context:
space:
mode:
Diffstat (limited to 'cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h')
-rw-r--r--cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h126
1 files changed, 126 insertions, 0 deletions
diff --git a/cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h b/cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h
new file mode 100644
index 000000000000..2d2963f9dab7
--- /dev/null
+++ b/cddl/contrib/opensolaris/cmd/sgs/include/_string_table.h
@@ -0,0 +1,126 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#ifndef __STRING_TABLE_DOT_H
+#define __STRING_TABLE_DOT_H
+
+#pragma ident "%Z%%M% %I% %E% SMI"
+
+#include <sys/types.h>
+#include <sys/avl.h>
+#include <string_table.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/*
+ * A string is represented in a string table using two values: length, and
+ * value. Grouping all the strings of a given length together allows for
+ * efficient matching of tail strings, as each input string value is hashed.
+ * Each string table uses a 2-level AVL tree of AVL trees to represent this
+ * organization.
+ *
+ * The outer (main) AVL tree contains LenNode structures. The search key for
+ * nodes on this main tree is the string length. Each such node represents
+ * all strings of a given length, and all strings of that length are found
+ * within.
+ *
+ * The strings within each LenNode are maintained using a secondary AVL tree
+ * of StrNode structures. The search key for this inner tree is the string
+ * itself. The strings are maintained in lexical order.
+ */
+typedef struct {
+ avl_node_t sn_avlnode; /* AVL book-keeping */
+ const char *sn_str; /* string */
+ size_t sn_refcnt; /* reference count */
+} StrNode;
+
+typedef struct {
+ avl_node_t ln_avlnode; /* AVL book-keeping */
+ avl_tree_t *ln_strtree; /* AVL tree of associated strings */
+ size_t ln_strlen; /* length of associated strings */
+} LenNode;
+
+/*
+ * Define a master string data item. Other strings may be suffixes of this
+ * string. The final string table will consist of the master string values,
+ * laid end to end, with the other strings referencing their tails.
+ */
+typedef struct str_master Str_master;
+
+struct str_master {
+ const char *sm_str; /* pointer to master string */
+ Str_master *sm_next; /* used for tracking master strings */
+ size_t sm_strlen; /* length of master string */
+ uint_t sm_hashval; /* hashval of master string */
+ size_t sm_stroff; /* offset into destination strtab */
+};
+
+/*
+ * Define a hash data item. This item represents an individual string that has
+ * been input into the String hash table. The string may either be a suffix of
+ * another string, or a master string.
+ */
+typedef struct str_hash Str_hash;
+
+struct str_hash {
+ size_t hi_strlen; /* string length */
+ size_t hi_refcnt; /* number of references to str */
+ uint_t hi_hashval; /* hash for string */
+ Str_master *hi_mstr; /* pointer to master string */
+ Str_hash *hi_next; /* next entry in hash bucket */
+};
+
+/*
+ * Controlling data structure for a String Table.
+ */
+struct str_tbl {
+ avl_tree_t *st_lentree; /* AVL tree of string lengths */
+ char *st_strbuf; /* string buffer */
+ Str_hash **st_hashbcks; /* hash buckets */
+ Str_master *st_mstrlist; /* list of all master strings */
+ size_t st_fullstrsize; /* uncompressed table size */
+ size_t st_nextoff; /* next available string */
+ size_t st_strsize; /* compressed size */
+ size_t st_strcnt; /* number of strings */
+ uint_t st_hbckcnt; /* number of buckets in */
+ /* hashlist */
+ uint_t st_flags;
+};
+
+#define FLG_STTAB_COMPRESS 0x01 /* compressed string table */
+#define FLG_STTAB_COOKED 0x02 /* offset has been assigned */
+
+/*
+ * Starting value for use with string hashing functions inside of string_table.c
+ */
+#define HASHSEED 5381
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __STRING_TABLE_DOT_H */