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