PERFORCE change 134177 for review
John Birrell
jb at FreeBSD.org
Sat Jan 26 18:40:03 PST 2008
http://perforce.freebsd.org/chv.cgi?CH=134177
Change 134177 by jb at jb_freebsd1 on 2008/01/27 02:39:11
IFopensolaris
Affected files ...
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/Makefile.com#5 branch
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/common/Makefile#6 branch
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/common/nfs/tst.call.c#1 branch
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/common/nfs/tst.call.d#1 branch
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/common/offsetof/err.D_OFFSETOF_BITFIELD.bitfield.d#3 integrate
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/include/debug.h#9 integrate
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/include/string_table.h#3 integrate
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/tools/common/sgsmsg.c#7 integrate
.. //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/tools/common/string_table.c#6 integrate
.. //depot/projects/dtrace/src/sys/contrib/opensolaris/uts/common/dtrace/sdt_subr.c#2 integrate
.. //depot/projects/dtrace/src/sys/contrib/opensolaris/uts/common/sys/cpuvar.h#3 integrate
.. //depot/projects/dtrace/src/sys/contrib/opensolaris/uts/common/sys/isa_defs.h#12 integrate
Differences ...
==== //depot/projects/dtrace/src/contrib/opensolaris/cmd/dtrace/test/tst/common/offsetof/err.D_OFFSETOF_BITFIELD.bitfield.d#3 (text+ko) ====
@@ -20,7 +20,7 @@
*/
/*
- * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
@@ -38,7 +38,13 @@
*
*/
+struct foo {
+ int a:1;
+ int b:3;
+};
+
BEGIN
{
- trace(offsetof(tcp_t, tcp_hwcksum));
+ trace(offsetof(struct foo, b));
+ exit(0);
}
==== //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/include/debug.h#9 (text) ====
@@ -786,7 +786,7 @@
const char *, int);
extern void Dbg_syms_ar_title(Lm_list *, const char *, int);
extern void Dbg_syms_created(Lm_list *, const char *);
-extern void Dbg_syms_discarded(Lm_list *, Sym_desc *, Is_desc *);
+extern void Dbg_syms_discarded(Lm_list *, Sym_desc *);
extern void Dbg_syms_dlsym(Rt_map *, const char *, const char *, int);
extern void Dbg_syms_dup_sort_addr(Lm_list *, const char *, const char *,
const char *, Addr);
==== //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/include/string_table.h#3 (text) ====
@@ -2,9 +2,8 @@
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
- * Common Development and Distribution License, Version 1.0 only
- * (the "License"). You may not use this file except in compliance
- * with the License.
+ * 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.
@@ -20,7 +19,7 @@
* CDDL HEADER END
*/
/*
- * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
@@ -29,109 +28,33 @@
#pragma ident "%Z%%M% %I% %E% SMI"
-#include <stdio.h>
#include <sys/types.h>
-#include <sys/avl.h>
-#include <sgs.h>
#ifdef __cplusplus
extern "C" {
#endif
-typedef struct str_hash Str_hash;
-typedef struct str_tbl Str_tbl;
-typedef struct str_master Str_master;
-
-
/*
- * The Stringlist is the list of 'input strings'
- * associatied with the AVL nodes Stringelem.
+ * Exported, opaque string table handle.
*/
-typedef struct stringlist {
- const char *sl_string;
- struct stringlist *sl_next;
-} Stringlist;
+typedef struct str_tbl Str_tbl;
/*
- * Nodes for the initial AVL tree which contains all of
- * the input strings. The AVL tree is indexed off of
- * the length of the strings. This permits later traversal
- * of all of the strings based off of their string length.
- */
-typedef struct {
- avl_node_t se_avlnode;
- Stringlist *se_strlist;
- uint_t se_stlen;
-} Stringelem;
-
-
-/*
- * Pointer to the Master string, other strings may be suffixes
- * of this string.
+ * Exported string table functions.
*/
-struct str_master {
- const char *sm_str; /* pointer to master string */
- Str_master *sm_next; /* used for tracking master strings */
- uint_t sm_stlen; /* length of master string */
- uint_t sm_hashval; /* hashval of master string */
- uint_t sm_stoff; /* offset into destination strtab */
-};
-
-
-/*
- * Represents a individual string that was input into
- * the String hash table. The string may either be a
- * suffix of another string or a master string.
- */
-struct str_hash {
- uint_t hi_stlen; /* string length */
- uint_t hi_refcnt; /* # 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 bckt */
-};
-
-/*
- * Controlling data structure for a String Table
- */
-struct str_tbl {
- avl_tree_t *st_strtree; /* avl tree of initial strs */
- char *st_strbuf; /* string buffer */
- Str_hash **st_hashbcks; /* hash buckets */
- Str_master *st_mstrlist; /* list of all master strings */
- uint_t st_fullstringsize; /* uncompressed table size */
- uint_t st_nextoff; /* next available string */
- uint_t st_stringsize; /* compressed size */
- uint_t st_stringcnt; /* # of strings */
- uint_t st_hbckcnt; /* # of buckets in hashlist */
- uint_t st_flags;
-};
-
-#define FLG_STTAB_COOKED 0x00000001 /* offset has been assigned */
-#define FLG_STTAB_COMPRESS 0x00000002 /* build compressed str tab */
-
-/*
- * starting value for use with string hashing functions
- * inside of string_table.c
- */
-#define HASHSEED 5381
-
-/*
- * Flags for st_new
- */
-#define FLG_STNEW_COMPRESS 0x00000001 /* build compressed str tab */
-
-/*
- * exported string_table.c functions
- */
extern int st_delstring(Str_tbl *, const char *);
extern void st_destroy(Str_tbl *);
extern uint_t st_getstrtab_sz(Str_tbl *);
extern const char *st_getstrbuf(Str_tbl *);
extern int st_insert(Str_tbl *, const char *);
+extern Str_tbl *st_new(uint_t);
extern int st_setstrbuf(Str_tbl *, char *, uint_t);
extern int st_setstring(Str_tbl *, const char *, uint_t *);
-extern Str_tbl *st_new(uint_t);
+
+/*
+ * Exported flags values for st_new().
+ */
+#define FLG_STNEW_COMPRESS 0x01 /* compressed string table */
#ifdef __cplusplus
}
==== //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/tools/common/sgsmsg.c#7 (text) ====
@@ -2,9 +2,8 @@
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
- * Common Development and Distribution License, Version 1.0 only
- * (the "License"). You may not use this file except in compliance
- * with the License.
+ * 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.
@@ -20,8 +19,8 @@
* CDDL HEADER END
*/
/*
- * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
- * Use is subject to license terms.
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
*
* sgsmsg generates several message files from an input template file. Messages
* are constructed for use with gettext(3i) - the default - or catgets(3c). The
@@ -67,7 +66,6 @@
* the data array being built in msg.c. The index into this array
* becomes the `message' identifier created in the msg.h file.
*/
-
#pragma ident "%Z%%M% %I% %E% SMI"
#include <fcntl.h>
@@ -81,7 +79,7 @@
#include <sys/param.h>
#include <sgs.h>
-#include <string_table.h>
+#include <_string_table.h>
/*
* Define any error message strings.
@@ -151,14 +149,13 @@
(void) fprintf(stderr, Errmsg_nmem, strerror(errno));
exit(1);
}
- if (stp == 0) {
- /*
- * Initialize string table
- */
- if ((stp = st_new(FLG_STNEW_COMPRESS)) == 0) {
- (void) fprintf(stderr, Errmsg_stnw, strerror(errno));
- exit(1);
- }
+
+ /*
+ * Initialize the string table.
+ */
+ if ((stp == 0) && ((stp = st_new(FLG_STNEW_COMPRESS)) == NULL)) {
+ (void) fprintf(stderr, Errmsg_stnw, strerror(errno));
+ exit(1);
}
@@ -314,45 +311,51 @@
return (0);
}
-
/*
* Dump contents of String Table to standard out
*/
static void
-dump_stringtab(Str_tbl *dump_stp)
+dump_stringtab(Str_tbl *stp)
{
- uint_t i;
+ uint_t cnt;
- if ((dump_stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
- (void) printf("uncompressed strings: %d\n",
- dump_stp->st_fullstringsize);
+ if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
+ (void) printf("string table full size: %d: uncompressed\n",
+ stp->st_fullstrsize);
return;
}
+ (void) printf("string table full size: %d compressed down to: %d\n\n",
+ stp->st_fullstrsize, stp->st_strsize);
+ (void) printf("string table compression information [%d buckets]:\n",
+ stp->st_hbckcnt);
+
+ for (cnt = 0; cnt < stp->st_hbckcnt; cnt++) {
+ Str_hash *sthash = stp->st_hashbcks[cnt];
+
+ if (sthash == 0)
+ continue;
+
+ (void) printf(" bucket: [%d]\n", cnt);
+
+ while (sthash) {
+ uint_t stroff = sthash->hi_mstr->sm_strlen -
+ sthash->hi_strlen;
- for (i = 0; i < dump_stp->st_hbckcnt; i++) {
- Str_hash *sthash;
- (void) printf("Bucket: [%3d]\n", i);
- for (sthash = dump_stp->st_hashbcks[i]; sthash;
- sthash = sthash->hi_next) {
- uint_t stroff;
- stroff = sthash->hi_mstr->sm_stlen - sthash->hi_stlen;
if (stroff == 0) {
- (void) printf(" %2d %s <master>\n",
- sthash->hi_refcnt,
- sthash->hi_mstr->sm_str);
+ (void) printf(" [%d]: '%s' <master>\n",
+ sthash->hi_refcnt, sthash->hi_mstr->sm_str);
} else {
- const char *str;
- str = &sthash->hi_mstr->sm_str[stroff];
- (void) printf(" %2d %s <suffix of> -> %s\n",
- sthash->hi_refcnt,
- str, sthash->hi_mstr->sm_str);
+ (void) printf(" [%d]: '%s' <suffix of: "
+ "'%s'>\n", sthash->hi_refcnt,
+ &sthash->hi_mstr->sm_str[stroff],
+ sthash->hi_mstr->sm_str);
}
+ sthash = sthash->hi_next;
}
}
- (void) printf("fullstringsize: %d compressed: %d\n",
- dump_stp->st_fullstringsize, dump_stp->st_stringsize);
}
+
/*
* Initialize the message definition header file stream.
*/
@@ -520,7 +523,6 @@
return (0);
}
-
/*
* The entire messaging file has been scanned - and all strings have been
* inserted into the string_table. We can now walk the message queue
@@ -553,7 +555,7 @@
return (1);
}
if (fddefs && fprintf(fddefs, "#define\t%s_SIZE\t%d\n",
- msg->ms_defn, (int) strlen(msg->ms_message)) < 0) {
+ msg->ms_defn, strlen(msg->ms_message)) < 0) {
(void) fprintf(stderr, Errmsg_wrte,
fldefs, strerror(errno));
return (1);
@@ -631,7 +633,7 @@
}
static int
-file(void)
+file()
{
char buffer[LINE_MAX], * token;
uint_t bufsize;
@@ -647,9 +649,8 @@
line = 1;
while ((token = fgets(buffer, LINE_MAX, fddesc)) != NULL) {
- char defn[PATH_MAX], * _defn;
- const char *str;
- int len = 0;
+ char defn[PATH_MAX], * _defn, * str;
+ int len;
switch (*token) {
case '#':
@@ -901,6 +902,7 @@
* unless an escape character is found
* terminate the data string with a 0.
*/
+ /* BEGIN CSTYLED */
if (*token == '"') {
if (fdlint && (fprintf(fdlint,
"%c", *token) < 0)) {
@@ -926,6 +928,7 @@
_token = '\0';
} else
_token = *token;
+ /* END CSTYLED */
}
if (fdmsgs && (prtmsgs == 1) &&
@@ -942,7 +945,7 @@
return (1);
}
- if (len >= (int) bufsize) {
+ if (len >= bufsize) {
bufsize += LINE_MAX;
if ((token_buffer = realloc(
token_buffer, bufsize)) == 0) {
@@ -1188,7 +1191,6 @@
if (vflag)
dump_stringtab(stp);
-
/*
* Close up everything and go home.
*/
==== //depot/projects/dtrace/src/contrib/opensolaris/cmd/sgs/tools/common/string_table.c#6 (text) ====
@@ -20,47 +20,42 @@
*/
/*
- * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
-#include <string_table.h>
+#include <_string_table.h>
#include <strings.h>
-#include <string.h>
#include <sgs.h>
#include <stdio.h>
-
-
/*
- * This file provides the interfaces to build a Str_tbl suitable
- * for use by either the sgsmsg system or a standard ELF
- * SHT_STRTAB.
+ * This file provides the interfaces to build a Str_tbl suitable for use by
+ * either the sgsmsg message system, or a standard ELF string table (SHT_STRTAB)
+ * as created by ld(1).
*
- * There are two modes which can be used when constructing a
- * string table:
+ * There are two modes which can be used when constructing a string table:
*
* st_new(0)
* standard string table - no compression. This is the
- * traditional method and fast
+ * traditional, fast method.
*
- * st_new(FLG_STNEW_COMPRESS)
- * build a compressed string table which both
- * eliminates duplicate strings and permits
- * strings with common suffixes (atexit vs. exit) to
- * overlap in the table. This provides space
- * savings for many string tables.
+ * st_new(FLG_STTAB_COMPRESS)
+ * builds a compressed string table which both eliminates
+ * duplicate strings, and permits strings with common suffixes
+ * (atexit vs. exit) to overlap in the table. This provides space
+ * savings for many string tables. Although more work than the
+ * traditional method, the algorithms used are designed to scale
+ * and keep any overhead at a minimum.
*
- * These string tables are now built with a common interface in a
- * two-pass manner, the first pass it to find all of the strings
- * required for the string-table and to calculate the size that
- * will be required for the final string table.
+ * These string tables are built with a common interface in a two-pass manner.
+ * The first pass finds all of the strings required for the string-table and
+ * calculates the size required for the final string table.
*
- * The second pass allocates the string table and populates the
- * strings into the table and returns the offsets the strings
- * have been assigned.
+ * The second pass allocates the string table, populates the strings into the
+ * table and returns the offsets the strings have been assigned.
*
* The calling sequence to build and populate a string table is:
*
@@ -72,7 +67,6 @@
*
* st_delstring(st?); // remove string previously
* // inserted
- *
* st_insert(stN);
*
* st_getstrtab_sz(); // freezes strtab and computes
@@ -114,219 +108,234 @@
* The above method will find all suffixes of a given string given
* that the strings are inserted from shortest to longest. That is
* why this is a two phase method, we first collect all of the
- * strings and store them based off of their length in a nice AVL tree.
+ * strings and store them based off of their length in an AVL tree.
* Once all of the strings have been submitted we then start the
* hash table build by traversing the AVL tree in order and
* inserting the strings from shortest to longest as described
* above.
- *
*/
/* LINTLIBRARY */
-
static int
-strlen_compare(const void *elem1, const void *elem2)
+avl_len_compare(const void *n1, const void *n2)
{
- uint_t l1, l2;
- l1 = ((const Stringelem *)elem1)->se_stlen;
- l2 = ((const Stringelem *)elem2)->se_stlen;
+ uint_t len1, len2;
+
+ len1 = ((LenNode *)n1)->ln_strlen;
+ len2 = ((LenNode *)n2)->ln_strlen;
- if (l1 == l2)
+ if (len1 == len2)
return (0);
- if (l2 < l1)
+ if (len2 < len1)
return (1);
+ return (-1);
+}
+
+static int
+avl_str_compare(const void *n1, const void *n2)
+{
+ const char *str1, *str2;
+ int rc;
+
+ str1 = ((StrNode *)n1)->sn_str;
+ str2 = ((StrNode *)n2)->sn_str;
- return (-1);
+ rc = strcmp(str1, str2);
+ if (rc > 0)
+ return (1);
+ if (rc < 0)
+ return (-1);
+ return (0);
}
/*
- * Return a initialized Str_tbl - returns NULL on failure.
+ * Return an initialized Str_tbl - returns NULL on failure.
*
- * stflags:
- *
- * FLG_STNEW_COMPRESS - build a compressed string table
- *
+ * flags:
+ * FLG_STTAB_COMPRESS - build a compressed string table
*/
Str_tbl *
-st_new(uint_t stflags)
+st_new(uint_t flags)
{
Str_tbl *stp;
- if ((stp = calloc(sizeof (Str_tbl), 1)) == 0)
- return (0);
+ if ((stp = calloc(sizeof (Str_tbl), 1)) == NULL)
+ return (NULL);
/*
* Start with a leading '\0' - it's tradition.
*/
- stp->st_stringsize = stp->st_fullstringsize = stp->st_nextoff = 1;
+ stp->st_strsize = stp->st_fullstrsize = stp->st_nextoff = 1;
/*
- * Do we compress this string table
+ * Do we compress this string table?
*/
- if ((stflags & FLG_STNEW_COMPRESS) == 0)
+ stp->st_flags = flags;
+ if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
return (stp);
- stp->st_flags |= FLG_STTAB_COMPRESS;
- if ((stp->st_strtree = calloc(sizeof (avl_tree_t), 1)) == 0) {
- return (0);
- }
+ if ((stp->st_lentree = calloc(sizeof (avl_tree_t), 1)) == NULL)
+ return (NULL);
- avl_create(stp->st_strtree, &strlen_compare, sizeof (Stringelem),
- SGSOFFSETOF(Stringelem, se_avlnode));
+ avl_create(stp->st_lentree, &avl_len_compare, sizeof (LenNode),
+ SGSOFFSETOF(LenNode, ln_avlnode));
return (stp);
}
/*
- * Tear down a String_Table structure.
+ * Insert a new string into the Str_tbl. There are two AVL trees used.
+ *
+ * . The first LenNode AVL tree maintains a tree of nodes based on string
+ * sizes.
+ * . Each LenNode maintains a StrNode AVL tree for each string. Large
+ * applications have been known to contribute thousands of strings of
+ * the same size. Should strings need to be removed (-z ignore), then
+ * the string AVL tree makes this removal efficient and scalable.
*/
-void
-st_destroy(Str_tbl *stp)
+int
+st_insert(Str_tbl *stp, const char *str)
{
- Str_hash *sthash, *psthash;
- Str_master *mstr, *pmstr;
- uint_t i;
+ uint_t len;
+ StrNode *snp, sn = { 0 };
+ LenNode *lnp, ln = { 0 };
+ avl_index_t where;
/*
- * cleanup the master strings
+ * String table can't have been cooked
*/
- for (mstr = stp->st_mstrlist, pmstr = 0; mstr;
- mstr = mstr->sm_next) {
- if (pmstr)
- free(pmstr);
- pmstr = mstr;
- }
- if (pmstr)
- free(pmstr);
-
- if (stp->st_hashbcks) {
- for (i = 0; i < stp->st_hbckcnt; i++) {
- for (sthash = stp->st_hashbcks[i], psthash = 0;
- sthash; sthash = sthash->hi_next) {
- if (psthash)
- free(psthash);
- psthash = sthash;
- }
- if (psthash)
- free(psthash);
- }
- free(stp->st_hashbcks);
- }
- free(stp);
-}
-
-
-
+ assert((stp->st_flags & FLG_STTAB_COOKED) == 0);
-/*
- * Remove a previously inserted string from the Str_tbl
- */
-int
-st_delstring(Str_tbl *stp, const char *str)
-{
- uint_t stlen;
- Stringelem qstelem;
- Stringelem *stelem;
- Stringlist *stlist, *pstlist;
-
/*
- * String table can't have been cooked
+ * Null strings always point to the head of the string
+ * table - no reason to keep searching.
*/
- assert((stp->st_flags & FLG_STTAB_COOKED) == 0);
+ if ((len = (uint_t)strlen(str)) == 0)
+ return (0);
- stlen = (uint_t)strlen(str);
- stp->st_fullstringsize -= stlen + 1;
+ stp->st_fullstrsize += len + 1;
+ stp->st_strcnt++;
if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
return (0);
- qstelem.se_stlen = stlen;
- if ((stelem = avl_find(stp->st_strtree, &qstelem, 0)) == NULL) {
- /*
- * no strings of this length recorded, let alone
- * this specific string - someone goofed.
- */
- return (-1);
- }
+ /*
+ * From the controlling string table, determine which LenNode AVL node
+ * provides for this string length. If the node doesn't exist, insert
+ * a new node to represent this string length.
+ */
+ ln.ln_strlen = len;
+ if ((lnp = avl_find(stp->st_lentree, &ln, &where)) == NULL) {
+ if ((lnp = calloc(sizeof (LenNode), 1)) == NULL)
+ return (-1);
+ lnp->ln_strlen = len;
+ avl_insert(stp->st_lentree, lnp, where);
- pstlist = 0;
- for (stlist = stelem->se_strlist; stlist; stlist = stlist->sl_next) {
- if (strcmp(str, stlist->sl_string) == 0)
- break;
- pstlist = stlist;
- }
+ if ((lnp->ln_strtree = calloc(sizeof (avl_tree_t), 1)) == NULL)
+ return (0);
- if (stlist == 0) {
- /*
- * string was not found
- */
- return (-1);
+ avl_create(lnp->ln_strtree, &avl_str_compare, sizeof (StrNode),
+ SGSOFFSETOF(StrNode, sn_avlnode));
}
- if (pstlist == 0) {
- /*
- * String is first on list.
- */
- stelem->se_strlist = stlist->sl_next;
- } else {
- /*
- * remove string from list.
- */
- pstlist->sl_next = stlist->sl_next;
+ /*
+ * From the string length AVL node determine whether a StrNode AVL node
+ * provides this string. If the node doesn't exist, insert a new node
+ * to represent this string.
+ */
+ sn.sn_str = str;
+ if ((snp = avl_find(lnp->ln_strtree, &sn, &where)) == NULL) {
+ if ((snp = calloc(sizeof (StrNode), 1)) == NULL)
+ return (-1);
+ snp->sn_str = str;
+ avl_insert(lnp->ln_strtree, snp, where);
}
+ snp->sn_refcnt++;
- free(stlist);
return (0);
}
-
/*
- * Insert a new string into the Str_tbl
+ * Remove a previously inserted string from the Str_tbl.
*/
int
-st_insert(Str_tbl *stp, const char *str)
+st_delstring(Str_tbl *stp, const char *str)
{
- uint_t stlen;
- Stringelem qstelem;
- Stringelem *stelem;
- Stringlist *strlist;
- avl_index_t where;
+ uint_t len;
+ LenNode *lnp, ln = { 0 };
+ StrNode *snp, sn = { 0 };
/*
* String table can't have been cooked
*/
assert((stp->st_flags & FLG_STTAB_COOKED) == 0);
- stlen = (uint_t)strlen(str);
- /*
- * Null strings always point to the head of the string
- * table - no reason to keep searching.
- */
- if (stlen == 0)
- return (0);
- stp->st_fullstringsize += stlen + 1;
- stp->st_stringcnt++;
+ len = (uint_t)strlen(str);
+ stp->st_fullstrsize -= len + 1;
if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
return (0);
- qstelem.se_stlen = strlen(str);
- if ((stelem = avl_find(stp->st_strtree, &qstelem,
- &where)) == NULL) {
- if ((stelem = calloc(sizeof (Stringelem), 1)) == 0)
- return (-1);
- stelem->se_stlen = qstelem.se_stlen;
- avl_insert(stp->st_strtree, stelem, where);
+ /*
+ * Determine which LenNode AVL node provides for this string length.
+ */
+ ln.ln_strlen = len;
+ if ((lnp = avl_find(stp->st_lentree, &ln, 0)) != NULL) {
+ sn.sn_str = str;
+ if ((snp = avl_find(lnp->ln_strtree, &sn, 0)) != NULL) {
+ /*
+ * Reduce the reference count, and if zero remove the
+ * node.
+ */
+ if (--snp->sn_refcnt == 0)
+ avl_remove(lnp->ln_strtree, snp);
+ return (0);
+ }
}
- if ((strlist = malloc(sizeof (Stringlist))) == 0)
- return (-1);
+
+ /*
+ * No strings of this length, or no string itself - someone goofed.
+ */
+ return (-1);
+}
+
+/*
+ * Tear down a String_Table structure.
+ */
+void
+st_destroy(Str_tbl *stp)
+{
+ Str_hash *sthash, *psthash;
+ Str_master *mstr, *pmstr;
+ uint_t i;
- strlist->sl_string = str;
- strlist->sl_next = stelem->se_strlist;
- stelem->se_strlist = strlist;
+ /*
+ * cleanup the master strings
+ */
+ for (mstr = stp->st_mstrlist, pmstr = 0; mstr;
+ mstr = mstr->sm_next) {
+ if (pmstr)
+ free(pmstr);
+ pmstr = mstr;
+ }
+ if (pmstr)
+ free(pmstr);
- return (0);
+ if (stp->st_hashbcks) {
+ for (i = 0; i < stp->st_hbckcnt; i++) {
+ for (sthash = stp->st_hashbcks[i], psthash = 0;
+ sthash; sthash = sthash->hi_next) {
+ if (psthash)
+ free(psthash);
+ psthash = sthash;
+ }
+ if (psthash)
+ free(psthash);
+ }
+ free(stp->st_hashbcks);
+ }
+ free(stp);
}
@@ -369,7 +378,7 @@
/*
* Have we overflowed our assigned buffer?
*/
- if ((_stoff + stlen) > stp->st_fullstringsize)
+ if ((_stoff + stlen) > stp->st_fullstrsize)
return (-1);
memcpy(stp->st_strbuf + _stoff, str, stlen);
*stoff = _stoff;
@@ -378,26 +387,25 @@
}
/*
- * Calculate reverse hash for string
+ * Calculate reverse hash for string.
*/
hashval = HASHSEED;
for (i = stlen; i >= 0; i--) {
hashval = ((hashval << 5) + hashval) +
- str[i]; /* h = ((h * 33) + c) */
+ str[i]; /* h = ((h * 33) + c) */
}
for (sthash = stp->st_hashbcks[hashval % stp->st_hbckcnt]; sthash;
sthash = sthash->hi_next) {
- if (sthash->hi_hashval == hashval) {
- const char *hstr;
+ const char *hstr;
+
+ if (sthash->hi_hashval != hashval)
+ continue;
- hstr = &sthash->hi_mstr->sm_str[
- sthash->hi_mstr->sm_stlen -
- sthash->hi_stlen];
- if (strcmp(str, hstr) == 0) {
- break;
- }
- }
+ hstr = &sthash->hi_mstr->sm_str[sthash->hi_mstr->sm_strlen -
+ sthash->hi_strlen];
+ if (strcmp(str, hstr) == 0)
+ break;
}
/*
@@ -410,29 +418,33 @@
* Has this string been copied into the string table?
*/
mstr = sthash->hi_mstr;
- if (mstr->sm_stoff == 0) {
- uint_t mstlen = mstr->sm_stlen + 1;
- mstr->sm_stoff = stp->st_nextoff;
+ if (mstr->sm_stroff == 0) {
+ uint_t mstrlen = mstr->sm_strlen + 1;
+
+ mstr->sm_stroff = stp->st_nextoff;
+
/*
* Have we overflowed our assigned buffer?
*/
- if ((mstr->sm_stoff + mstlen) > stp->st_fullstringsize)
+ if ((mstr->sm_stroff + mstrlen) > stp->st_fullstrsize)
return (-1);
- memcpy(stp->st_strbuf + mstr->sm_stoff, mstr->sm_str,
- mstlen);
- stp->st_nextoff += mstlen;
+
+ (void) memcpy(stp->st_strbuf + mstr->sm_stroff,
+ mstr->sm_str, mstrlen);
+ stp->st_nextoff += mstrlen;
}
+
/*
- * Calculate offset of (sub)string
+ * Calculate offset of (sub)string.
*/
- *stoff = mstr->sm_stoff + mstr->sm_stlen - sthash->hi_stlen;
+ *stoff = mstr->sm_stroff + mstr->sm_strlen - sthash->hi_strlen;
return (0);
}
static int
-st_hash_insert(Str_tbl *stp, const char *str, uint_t stlen)
+st_hash_insert(Str_tbl *stp, const char *str, uint_t len)
{
int i;
uint_t hashval = HASHSEED;
@@ -451,51 +463,48 @@
* any suffixes already exist in the tree as we generate
* the hash.
*/
- for (i = stlen; i >= 0; i--) {
+ for (i = len; i >= 0; i--) {
+ hashval = ((hashval << 5) + hashval) +
+ str[i]; /* h = ((h * 33) + c) */
- hashval = ((hashval << 5) + hashval) +
- str[i]; /* h = ((h * 33) + c) */
for (sthash = hashbcks[hashval % bckcnt];
sthash; sthash = sthash->hi_next) {
+ const char *hstr;
+ Str_master *_mstr;
- if (sthash->hi_hashval == hashval) {
- const char *hstr;
- Str_master *_mstr;
+ if (sthash->hi_hashval != hashval)
+ continue;
+
+ _mstr = sthash->hi_mstr;
+ hstr = &_mstr->sm_str[_mstr->sm_strlen -
+ sthash->hi_strlen];
+
+ if (strcmp(&str[i], hstr))
+ continue;
- _mstr = sthash->hi_mstr;
- hstr = &_mstr->sm_str[_mstr->sm_stlen -
- sthash->hi_stlen];
- if (strcmp(&str[i], hstr) == 0) {
- if (i == 0) {
- /*
- * Entry already in table,
- * increment refcnt and get
- * out.
- */
- sthash->hi_refcnt++;
- return (0);
- } else {
- /*
- * If this 'suffix' is
- * presently a 'master' string,
- * then take over it's record.
- */
- if (sthash->hi_stlen ==
>>> TRUNCATED FOR MAIL (1000 lines) <<<
More information about the p4-projects
mailing list