server/common/shstr.c

/*
 * static char *rcsid_shstr_c =
 *   "$Id: shstr.c,v 1.8 2005/12/05 23:34:03 akirschbaum Exp $";
 *
 * shstr.c
 *
 * This is a simple shared strings package with a simple interface.
 *
 *     char *find_string(const char *str)
 *     char *add_string(const char *str)
 *      char *add_refcount(char *str)
 *      void free_string(char *str)
 *      char *ss_dump_table(int what)
 *      void ss_dump_statistics()
 *
 * Author: Kjetil T. Homme, Oslo 1992.
 */

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <sys/types.h>
#include <limits.h>
#include <string.h>

#if defined (__sun__) && defined (StupidSunHeaders)
#include <sys/time.h>
#include "sunos.h"
#endif

#include "shstr.h"

#ifndef WIN32
#include <autoconf.h>
#endif
#ifdef HAVE_LIBDMALLOC
#include <dmalloc.h>
#endif

static shared_string *hash_table[TABLESIZE];

/*
 * Initialises the hash-table used by the shared string library.
 */

void
init_hash_table(void) {
    /* A static object should be zeroed out always */
#if !defined(__STDC__)
    (void) memset((void *)hash_table, 0, TABLESIZE * sizeof(shared_string *));
#endif
}

/*
 * Hashing-function used by the shared string library.
 */

static int
hashstr(const char *str) {
    unsigned long hash = 0;
    int i = 0;
    unsigned rot = 0;
    const char *p;

    GATHER(hash_stats.calls);

    for (p = str; i < MAXSTRING && *p; p++, i++) {
        hash ^= (unsigned long) *p << rot;
        rot += 2;
        if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT)
            rot = 0;
    }
    return (hash % TABLESIZE);
}

/*
 * Allocates and initialises a new shared_string structure, containing
 * the string str.
 */

static shared_string *
new_shared_string(const char *str) {
    shared_string *ss;

    /* Allocate room for a struct which can hold str. Note
     * that some bytes for the string are already allocated in the 
     * shared_string struct.
     */
    ss = (shared_string *) malloc(sizeof(shared_string) - PADDING +
                                  strlen(str) + 1);
    ss->u.previous = NULL;
    ss->next = NULL;
    ss->refcount = 1;
    strcpy(ss->string, str);

    return ss;
}

/*
 * Description:
 *      This will add 'str' to the hash table. If there's no entry for this
 *      string, a copy will be allocated, and a pointer to that is returned.
 * Return values:
 *      - pointer to string identical to str
 */

const char *
add_string(const char *str) {
    shared_string *ss;
    int ind;

    GATHER(add_stats.calls);

    /* Should really core dump here, since functions should not be calling
     * add_string with a null parameter.  But this will prevent a few
     * core dumps.
     */
    if (str==NULL) {
#ifdef MANY_CORES
        abort();
#else
        return NULL;
#endif
    }

    ind = hashstr(str);
    ss = hash_table[ind];

    /* Is there an entry for that hash?
     */
    if (ss) {
        /* Simple case first: See if the first pointer matches.
         */
        if (str != ss->string) {
            GATHER(add_stats.strcmps);
            if (strcmp(ss->string, str)) {
                /* Apparantly, a string with the same hash value has this 
                 * slot. We must see in the list if "str" has been 
                 * registered earlier.
                 */
                while (ss->next) {
                    GATHER(add_stats.search);
                    ss = ss->next;
                    if (ss->string != str) {
                        GATHER(add_stats.strcmps);
                        if (strcmp(ss->string, str)) {
                            /* This wasn't the right string...
                             */
                            continue;
                        }
                    }
                    /* We found an entry for this string. Fix the
                     * refcount and exit.
                     */
                    GATHER(add_stats.linked);
                    ++(ss->refcount);

                    return ss->string;
                }
                /* There are no occurences of this string in the hash table.
                 */
                {
                    shared_string *new_ss;

                    GATHER(add_stats.linked);
                    new_ss = new_shared_string(str);
                    ss->next = new_ss;
                    new_ss->u.previous = ss;
                    return new_ss->string;
                }
            }
            /* Fall through.
             */
        }
        GATHER(add_stats.hashed);
        ++(ss->refcount);
        return ss->string;
    } else {
        /* The string isn't registered, and the slot is empty.
         */
        GATHER(add_stats.hashed);
        hash_table[ind] = new_shared_string(str);

        /* One bit in refcount is used to keep track of the union.
         */
        hash_table[ind]->refcount |= TOPBIT;
        hash_table[ind]->u.array = &(hash_table[ind]);

        return hash_table[ind]->string;
    }
}

/*
 * Description:
 *      This will increase the refcount of the string str, which *must*
 *      have been returned from a previous add_string().
 * Return values:
 *      - str
 */

const char *
add_refcount(const char *str) {
    GATHER(add_ref_stats.calls);
    ++(SS(str)->refcount);
    /* This function should be declared 
     *    const char *add_refcount(const char *)
     * Unfortunately, that would require changing a lot of structs
     *
     *   Yup, many changes, but may have make some bugs more visible :)
     *   -- Ryo 2005-08-12
     */
    return (char*)str;
}

/*
 * Description:
 *      This will return the refcount of the string str, which *must*
 *      have been returned from a previous add_string().
 * Return values:
 *      - length
 */

int
query_refcount(const char *str) {
    return SS(str)->refcount;
}

/*
 * Description:
 *      This will see if str is in the hash table, and return the address
 *      of that string if it exists.
 * Return values:
 *      - pointer to identical string or NULL
 */

const char *
find_string(const char *str) {
    shared_string *ss;
    int ind;

    GATHER(find_stats.calls);

    ind = hashstr(str);
    ss = hash_table[ind];

    /* Is there an entry for that hash?
     */
    if (ss) {
        /* Simple case first: Is the first string the right one?
         */
        GATHER(find_stats.strcmps);
        if (!strcmp(ss->string, str)) {
            GATHER(find_stats.hashed);
            return ss->string;
        } else {
            /* Recurse through the linked list, if there's one.
             */
            while (ss->next) {
                GATHER(find_stats.search);
                GATHER(find_stats.strcmps);
                ss = ss->next;
                if (!strcmp(ss->string, str)) {
                    GATHER(find_stats.linked);
                    return ss->string;
                }
            }
            /* No match. Fall through.
             */
        }
    }
    return NULL;
}

/*
 * Description:
 *     This will reduce the refcount, and if it has reached 0, str will
 *     be freed.
 * Return values:
 *     None
 */

void
free_string(const char *str) {
    shared_string *ss;

    GATHER(free_stats.calls);

    ss = SS(str);

    if ((--ss->refcount & ~TOPBIT) == 0) {
        /* Remove this entry.
         */
        if (ss->refcount & TOPBIT) {
            /* We must put a new value into the hash_table[].
             */
            if (ss->next) {
                *(ss->u.array) = ss->next;
                ss->next->u.array = ss->u.array;
                ss->next->refcount |= TOPBIT;
            } else {
                *(ss->u.array) = NULL;
            }
            free(ss);
        } else {
            /* Relink and free this struct.
             */
            if (ss->next)
                ss->next->u.previous = ss->u.previous;
            ss->u.previous->next = ss->next;
            free(ss);
        }
    }
}

#ifdef SS_STATISTICS

extern char errmsg[];

/*
 * Description:
 *      The routines will gather statistics if SS_STATISTICS is defined.
 *      A call to this function will cause the statistics to be dumped
 *      into an external string errmsg, which must be large.
 * Return values:
 *      None
 */

void
ss_dump_statistics(void) {
    static char line[80];

    sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", 
            "", "calls", "hashed", "strcmp", "search", "linked");
    sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", 
            "add_string:", add_stats.calls, add_stats.hashed, 
            add_stats.strcmps, add_stats.search, add_stats.linked);
    strcat(errmsg, line);
    sprintf(line, "%-13s %6d\n",
            "add_refcount:", add_ref_stats.calls);
    strcat(errmsg, line);
    sprintf(line, "%-13s %6d\n",
            "free_string:", free_stats.calls);
    strcat(errmsg, line);
    sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", 
            "find_string:", find_stats.calls, find_stats.hashed, 
            find_stats.strcmps, find_stats.search, find_stats.linked);
    strcat(errmsg, line);
    sprintf(line, "%-13s %6d\n",
            "hashstr:", hash_stats.calls);
    strcat(errmsg, line);
}
#endif /* SS_STATISTICS */

/*
 * Description:
 *      If (what & SS_DUMP_TABLE) dump the contents of the hash table to
 *      stderr. If (what & SS_DUMP_TOTALS) return a string which
 *      says how many entries etc. there are in the table.
 * Return values:
 *      - a string or NULL
 */

const char *
ss_dump_table(int what) {
    static char totals[80];
    int entries = 0, refs = 0, links = 0;
    int i;

    for (i = 0; i < TABLESIZE; i++) {
        shared_string *ss;
        
        if ((ss = hash_table[i])!=NULL) {
            ++entries;
            refs += (ss->refcount & ~TOPBIT);
#if 1 /* Can't use stderr any longer, need to include global.h and
            if (what & SS_DUMP_TABLE)
       * use logfile. */
                fprintf(stderr, "%4d -- %4d refs '%s' %c\n",
                        i, (ss->refcount & ~TOPBIT), ss->string,
                        (ss->refcount & TOPBIT ? ' ' : '#'));
#endif
            while (ss->next) {
                ss = ss->next;
                ++links;
                refs += (ss->refcount & ~TOPBIT);
#if 1
                if (what & SS_DUMP_TABLE)
                    fprintf(stderr, "     -- %4d refs '%s' %c\n",
                            (ss->refcount & ~TOPBIT), ss->string,
                            (ss->refcount & TOPBIT ? '*' : ' '));
#endif
            }
        }
    }

    if (what & SS_DUMP_TOTALS) {
        sprintf(totals, "\n%d entries, %d refs, %d links.",
                entries, refs, links);
        return totals;
    }
    return NULL;
}

/* buf_overflow() - we don't want to exceed the buffer size of 
 * buf1 by adding on buf2! Returns true if overflow will occur.
 */

int 
buf_overflow (const char *buf1, const char *buf2, int bufsize)
{
    int     len1 = 0, len2 = 0;

    if (buf1)
        len1 = strlen (buf1);
    if (buf2)
        len2 = strlen (buf2);
    if ((len1 + len2) >= bufsize)
        return 1;
    return 0;
}

Revision:	1.1.1.1 (vendor branch)
Committed:	Fri Feb 3 07:11:40 2006 UTC (18 years, 3 months ago) by root
Content type:	text/plain
Branch:	UPSTREAM
CVS Tags:	UPSTREAM_2006_02_22, UPSTREAM_2006_02_03
Changes since 1.1:	+0 -0 lines
Log Message:	initial import
#	User	Rev	Content
1	root	1.1	/*
2			* static char *rcsid_shstr_c =
3			* "$Id: shstr.c,v 1.8 2005/12/05 23:34:03 akirschbaum Exp $";
4			*
5			* shstr.c
6			*
7			* This is a simple shared strings package with a simple interface.
8			*
9			* char find_string(const char str)
10			* char add_string(const char str)
11			* char add_refcount(char str)
12			* void free_string(char *str)
13			* char *ss_dump_table(int what)
14			* void ss_dump_statistics()
15			*
16			* Author: Kjetil T. Homme, Oslo 1992.
17			*/
18
19			#include <stdio.h>
20			#include <stddef.h>
21			#include <stdlib.h>
22			#include <sys/types.h>
23			#include <limits.h>
24			#include <string.h>
25
26			#if defined (__sun__) && defined (StupidSunHeaders)
27			#include <sys/time.h>
28			#include "sunos.h"
29			#endif
30
31			#include "shstr.h"
32
33			#ifndef WIN32
34			#include <autoconf.h>
35			#endif
36			#ifdef HAVE_LIBDMALLOC
37			#include <dmalloc.h>
38			#endif
39
40			static shared_string *hash_table[TABLESIZE];
41
42			/*
43			* Initialises the hash-table used by the shared string library.
44			*/
45
46			void
47			init_hash_table(void) {
48			/* A static object should be zeroed out always */
49			#if !defined(__STDC__)
50			(void) memset((void )hash_table, 0, TABLESIZE sizeof(shared_string *));
51			#endif
52			}
53
54			/*
55			* Hashing-function used by the shared string library.
56			*/
57
58			static int
59			hashstr(const char *str) {
60			unsigned long hash = 0;
61			int i = 0;
62			unsigned rot = 0;
63			const char *p;
64
65			GATHER(hash_stats.calls);
66
67			for (p = str; i < MAXSTRING && *p; p++, i++) {
68			hash ^= (unsigned long) *p << rot;
69			rot += 2;
70			if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT)
71			rot = 0;
72			}
73			return (hash % TABLESIZE);
74			}
75
76			/*
77			* Allocates and initialises a new shared_string structure, containing
78			* the string str.
79			*/
80
81			static shared_string *
82			new_shared_string(const char *str) {
83			shared_string *ss;
84
85			/* Allocate room for a struct which can hold str. Note
86			* that some bytes for the string are already allocated in the
87			* shared_string struct.
88			*/
89			ss = (shared_string *) malloc(sizeof(shared_string) - PADDING +
90			strlen(str) + 1);
91			ss->u.previous = NULL;
92			ss->next = NULL;
93			ss->refcount = 1;
94			strcpy(ss->string, str);
95
96			return ss;
97			}
98
99			/*
100			* Description:
101			* This will add 'str' to the hash table. If there's no entry for this
102			* string, a copy will be allocated, and a pointer to that is returned.
103			* Return values:
104			* - pointer to string identical to str
105			*/
106
107			const char *
108			add_string(const char *str) {
109			shared_string *ss;
110			int ind;
111
112			GATHER(add_stats.calls);
113
114			/* Should really core dump here, since functions should not be calling
115			* add_string with a null parameter. But this will prevent a few
116			* core dumps.
117			*/
118			if (str==NULL) {
119			#ifdef MANY_CORES
120			abort();
121			#else
122			return NULL;
123			#endif
124			}
125
126			ind = hashstr(str);
127			ss = hash_table[ind];
128
129			/* Is there an entry for that hash?
130			*/
131			if (ss) {
132			/* Simple case first: See if the first pointer matches.
133			*/
134			if (str != ss->string) {
135			GATHER(add_stats.strcmps);
136			if (strcmp(ss->string, str)) {
137			/* Apparantly, a string with the same hash value has this
138			* slot. We must see in the list if "str" has been
139			* registered earlier.
140			*/
141			while (ss->next) {
142			GATHER(add_stats.search);
143			ss = ss->next;
144			if (ss->string != str) {
145			GATHER(add_stats.strcmps);
146			if (strcmp(ss->string, str)) {
147			/* This wasn't the right string...
148			*/
149			continue;
150			}
151			}
152			/* We found an entry for this string. Fix the
153			* refcount and exit.
154			*/
155			GATHER(add_stats.linked);
156			++(ss->refcount);
157
158			return ss->string;
159			}
160			/* There are no occurences of this string in the hash table.
161			*/
162			{
163			shared_string *new_ss;
164
165			GATHER(add_stats.linked);
166			new_ss = new_shared_string(str);
167			ss->next = new_ss;
168			new_ss->u.previous = ss;
169			return new_ss->string;
170			}
171			}
172			/* Fall through.
173			*/
174			}
175			GATHER(add_stats.hashed);
176			++(ss->refcount);
177			return ss->string;
178			} else {
179			/* The string isn't registered, and the slot is empty.
180			*/
181			GATHER(add_stats.hashed);
182			hash_table[ind] = new_shared_string(str);
183
184			/* One bit in refcount is used to keep track of the union.
185			*/
186			hash_table[ind]->refcount \|= TOPBIT;
187			hash_table[ind]->u.array = &(hash_table[ind]);
188
189			return hash_table[ind]->string;
190			}
191			}
192
193			/*
194			* Description:
195			* This will increase the refcount of the string str, which must
196			* have been returned from a previous add_string().
197			* Return values:
198			* - str
199			*/
200
201			const char *
202			add_refcount(const char *str) {
203			GATHER(add_ref_stats.calls);
204			++(SS(str)->refcount);
205			/* This function should be declared
206			* const char add_refcount(const char )
207			* Unfortunately, that would require changing a lot of structs
208			*
209			* Yup, many changes, but may have make some bugs more visible :)
210			* -- Ryo 2005-08-12
211			*/
212			return (char*)str;
213			}
214
215			/*
216			* Description:
217			* This will return the refcount of the string str, which must
218			* have been returned from a previous add_string().
219			* Return values:
220			* - length
221			*/
222
223			int
224			query_refcount(const char *str) {
225			return SS(str)->refcount;
226			}
227
228			/*
229			* Description:
230			* This will see if str is in the hash table, and return the address
231			* of that string if it exists.
232			* Return values:
233			* - pointer to identical string or NULL
234			*/
235
236			const char *
237			find_string(const char *str) {
238			shared_string *ss;
239			int ind;
240
241			GATHER(find_stats.calls);
242
243			ind = hashstr(str);
244			ss = hash_table[ind];
245
246			/* Is there an entry for that hash?
247			*/
248			if (ss) {
249			/* Simple case first: Is the first string the right one?
250			*/
251			GATHER(find_stats.strcmps);
252			if (!strcmp(ss->string, str)) {
253			GATHER(find_stats.hashed);
254			return ss->string;
255			} else {
256			/* Recurse through the linked list, if there's one.
257			*/
258			while (ss->next) {
259			GATHER(find_stats.search);
260			GATHER(find_stats.strcmps);
261			ss = ss->next;
262			if (!strcmp(ss->string, str)) {
263			GATHER(find_stats.linked);
264			return ss->string;
265			}
266			}
267			/* No match. Fall through.
268			*/
269			}
270			}
271			return NULL;
272			}
273
274			/*
275			* Description:
276			* This will reduce the refcount, and if it has reached 0, str will
277			* be freed.
278			* Return values:
279			* None
280			*/
281
282			void
283			free_string(const char *str) {
284			shared_string *ss;
285
286			GATHER(free_stats.calls);
287
288			ss = SS(str);
289
290			if ((--ss->refcount & ~TOPBIT) == 0) {
291			/* Remove this entry.
292			*/
293			if (ss->refcount & TOPBIT) {
294			/* We must put a new value into the hash_table[].
295			*/
296			if (ss->next) {
297			*(ss->u.array) = ss->next;
298			ss->next->u.array = ss->u.array;
299			ss->next->refcount \|= TOPBIT;
300			} else {
301			*(ss->u.array) = NULL;
302			}
303			free(ss);
304			} else {
305			/* Relink and free this struct.
306			*/
307			if (ss->next)
308			ss->next->u.previous = ss->u.previous;
309			ss->u.previous->next = ss->next;
310			free(ss);
311			}
312			}
313			}
314
315			#ifdef SS_STATISTICS
316
317			extern char errmsg[];
318
319			/*
320			* Description:
321			* The routines will gather statistics if SS_STATISTICS is defined.
322			* A call to this function will cause the statistics to be dumped
323			* into an external string errmsg, which must be large.
324			* Return values:
325			* None
326			*/
327
328			void
329			ss_dump_statistics(void) {
330			static char line[80];
331
332			sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n",
333			"", "calls", "hashed", "strcmp", "search", "linked");
334			sprintf(line, "%-13s %6d %6d %6d %6d %6d\n",
335			"add_string:", add_stats.calls, add_stats.hashed,
336			add_stats.strcmps, add_stats.search, add_stats.linked);
337			strcat(errmsg, line);
338			sprintf(line, "%-13s %6d\n",
339			"add_refcount:", add_ref_stats.calls);
340			strcat(errmsg, line);
341			sprintf(line, "%-13s %6d\n",
342			"free_string:", free_stats.calls);
343			strcat(errmsg, line);
344			sprintf(line, "%-13s %6d %6d %6d %6d %6d\n",
345			"find_string:", find_stats.calls, find_stats.hashed,
346			find_stats.strcmps, find_stats.search, find_stats.linked);
347			strcat(errmsg, line);
348			sprintf(line, "%-13s %6d\n",
349			"hashstr:", hash_stats.calls);
350			strcat(errmsg, line);
351			}
352			#endif /* SS_STATISTICS */
353
354			/*
355			* Description:
356			* If (what & SS_DUMP_TABLE) dump the contents of the hash table to
357			* stderr. If (what & SS_DUMP_TOTALS) return a string which
358			* says how many entries etc. there are in the table.
359			* Return values:
360			* - a string or NULL
361			*/
362
363			const char *
364			ss_dump_table(int what) {
365			static char totals[80];
366			int entries = 0, refs = 0, links = 0;
367			int i;
368
369			for (i = 0; i < TABLESIZE; i++) {
370			shared_string *ss;
371
372			if ((ss = hash_table[i])!=NULL) {
373			++entries;
374			refs += (ss->refcount & ~TOPBIT);
375			#if 1 /* Can't use stderr any longer, need to include global.h and
376			if (what & SS_DUMP_TABLE)
377			* use logfile. */
378			fprintf(stderr, "%4d -- %4d refs '%s' %c\n",
379			i, (ss->refcount & ~TOPBIT), ss->string,
380			(ss->refcount & TOPBIT ? ' ' : '#'));
381			#endif
382			while (ss->next) {
383			ss = ss->next;
384			++links;
385			refs += (ss->refcount & ~TOPBIT);
386			#if 1
387			if (what & SS_DUMP_TABLE)
388			fprintf(stderr, " -- %4d refs '%s' %c\n",
389			(ss->refcount & ~TOPBIT), ss->string,
390			(ss->refcount & TOPBIT ? '*' : ' '));
391			#endif
392			}
393			}
394			}
395
396			if (what & SS_DUMP_TOTALS) {
397			sprintf(totals, "\n%d entries, %d refs, %d links.",
398			entries, refs, links);
399			return totals;
400			}
401			return NULL;
402			}
403
404			/* buf_overflow() - we don't want to exceed the buffer size of
405			* buf1 by adding on buf2! Returns true if overflow will occur.
406			*/
407
408			int
409			buf_overflow (const char buf1, const char buf2, int bufsize)
410			{
411			int len1 = 0, len2 = 0;
412
413			if (buf1)
414			len1 = strlen (buf1);
415			if (buf2)
416			len2 = strlen (buf2);
417			if ((len1 + len2) >= bufsize)
418			return 1;
419			return 0;
420			}
421