1178525Sjb/* 2178525Sjb * CDDL HEADER START 3178525Sjb * 4178525Sjb * The contents of this file are subject to the terms of the 5178525Sjb * Common Development and Distribution License (the "License"). 6178525Sjb * You may not use this file except in compliance with the License. 7178525Sjb * 8178525Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9178525Sjb * or http://www.opensolaris.org/os/licensing. 10178525Sjb * See the License for the specific language governing permissions 11178525Sjb * and limitations under the License. 12178525Sjb * 13178525Sjb * When distributing Covered Code, include this CDDL HEADER in each 14178525Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15178525Sjb * If applicable, add the following below this CDDL HEADER, with the 16178525Sjb * fields enclosed by brackets "[]" replaced with your own identifying 17178525Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 18178525Sjb * 19178525Sjb * CDDL HEADER END 20178525Sjb */ 21178525Sjb/* 22178525Sjb * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23178525Sjb * Use is subject to license terms. 24178525Sjb */ 25178525Sjb 26178525Sjb#ifndef __STRING_TABLE_DOT_H 27178525Sjb#define __STRING_TABLE_DOT_H 28178525Sjb 29178525Sjb#pragma ident "%Z%%M% %I% %E% SMI" 30178525Sjb 31178525Sjb#include <sys/types.h> 32178525Sjb#include <sys/avl.h> 33178525Sjb#include <string_table.h> 34178525Sjb 35178525Sjb#ifdef __cplusplus 36178525Sjbextern "C" { 37178525Sjb#endif 38178525Sjb 39178525Sjb/* 40178525Sjb * A string is represented in a string table using two values: length, and 41178525Sjb * value. Grouping all the strings of a given length together allows for 42178525Sjb * efficient matching of tail strings, as each input string value is hashed. 43178525Sjb * Each string table uses a 2-level AVL tree of AVL trees to represent this 44178525Sjb * organization. 45178525Sjb * 46178525Sjb * The outer (main) AVL tree contains LenNode structures. The search key for 47178525Sjb * nodes on this main tree is the string length. Each such node represents 48178525Sjb * all strings of a given length, and all strings of that length are found 49178525Sjb * within. 50178525Sjb * 51178525Sjb * The strings within each LenNode are maintained using a secondary AVL tree 52178525Sjb * of StrNode structures. The search key for this inner tree is the string 53178525Sjb * itself. The strings are maintained in lexical order. 54178525Sjb */ 55178525Sjbtypedef struct { 56178525Sjb avl_node_t sn_avlnode; /* AVL book-keeping */ 57178525Sjb const char *sn_str; /* string */ 58178525Sjb size_t sn_refcnt; /* reference count */ 59178525Sjb} StrNode; 60178525Sjb 61178525Sjbtypedef struct { 62178525Sjb avl_node_t ln_avlnode; /* AVL book-keeping */ 63178525Sjb avl_tree_t *ln_strtree; /* AVL tree of associated strings */ 64178525Sjb size_t ln_strlen; /* length of associated strings */ 65178525Sjb} LenNode; 66178525Sjb 67178525Sjb/* 68178525Sjb * Define a master string data item. Other strings may be suffixes of this 69178525Sjb * string. The final string table will consist of the master string values, 70178525Sjb * laid end to end, with the other strings referencing their tails. 71178525Sjb */ 72178525Sjbtypedef struct str_master Str_master; 73178525Sjb 74178525Sjbstruct str_master { 75178525Sjb const char *sm_str; /* pointer to master string */ 76178525Sjb Str_master *sm_next; /* used for tracking master strings */ 77178525Sjb size_t sm_strlen; /* length of master string */ 78178525Sjb uint_t sm_hashval; /* hashval of master string */ 79178525Sjb size_t sm_stroff; /* offset into destination strtab */ 80178525Sjb}; 81178525Sjb 82178525Sjb/* 83178525Sjb * Define a hash data item. This item represents an individual string that has 84178525Sjb * been input into the String hash table. The string may either be a suffix of 85178525Sjb * another string, or a master string. 86178525Sjb */ 87178525Sjbtypedef struct str_hash Str_hash; 88178525Sjb 89178525Sjbstruct str_hash { 90178525Sjb size_t hi_strlen; /* string length */ 91178525Sjb size_t hi_refcnt; /* number of references to str */ 92178525Sjb uint_t hi_hashval; /* hash for string */ 93178525Sjb Str_master *hi_mstr; /* pointer to master string */ 94178525Sjb Str_hash *hi_next; /* next entry in hash bucket */ 95178525Sjb}; 96178525Sjb 97178525Sjb/* 98178525Sjb * Controlling data structure for a String Table. 99178525Sjb */ 100178525Sjbstruct str_tbl { 101178525Sjb avl_tree_t *st_lentree; /* AVL tree of string lengths */ 102178525Sjb char *st_strbuf; /* string buffer */ 103178525Sjb Str_hash **st_hashbcks; /* hash buckets */ 104178525Sjb Str_master *st_mstrlist; /* list of all master strings */ 105178525Sjb size_t st_fullstrsize; /* uncompressed table size */ 106178525Sjb size_t st_nextoff; /* next available string */ 107178525Sjb size_t st_strsize; /* compressed size */ 108178525Sjb size_t st_strcnt; /* number of strings */ 109178525Sjb uint_t st_hbckcnt; /* number of buckets in */ 110178525Sjb /* hashlist */ 111178525Sjb uint_t st_flags; 112178525Sjb}; 113178525Sjb 114178525Sjb#define FLG_STTAB_COMPRESS 0x01 /* compressed string table */ 115178525Sjb#define FLG_STTAB_COOKED 0x02 /* offset has been assigned */ 116178525Sjb 117178525Sjb/* 118178525Sjb * Starting value for use with string hashing functions inside of string_table.c 119178525Sjb */ 120178525Sjb#define HASHSEED 5381 121178525Sjb 122178525Sjb#ifdef __cplusplus 123178525Sjb} 124178525Sjb#endif 125178525Sjb 126178525Sjb#endif /* __STRING_TABLE_DOT_H */ 127