Date: Sun, 27 Jan 2008 02:40:02 GMT From: John Birrell <jb@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 134177 for review Message-ID: <200801270240.m0R2e2It001660@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=134177 Change 134177 by jb@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) <<<
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200801270240.m0R2e2It001660>