server/common/shstr.c

/*
 * static char *rcsid_shstr_c =
 *   "$Id$";
 *
 * 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.2
Committed:	Sun Aug 13 17:16:01 2006 UTC (20 years, 2 months ago) by elmex
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	Made server compile with C++. Removed cfanim plugin and crossedit. C++ here we come.
#	Content
1	/*
2	* static char *rcsid_shstr_c =
3	* "$Id$";
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