src/common/savestr.c

#ifndef lint
static const char       RCSid[] = "$Id: savestr.c,v 2.14 2023/06/08 17:48:01 greg Exp $";
#endif
/*
 *  savestr.c - routines for efficient string storage.
 *
 *      Savestr(s) stores a shared read-only string.
 *  Freestr(s) indicates a client is finished with a string.
 *      All strings must be null-terminated.  There is
 *  no imposed length limit.
 *      Strings stored with savestr(s) can be equated
 *  reliably using their pointer values.
 *      Calls to savestr(s) and freestr(s) should be
 *  balanced (obviously).  The last call to freestr(s)
 *  frees memory associated with the string; it should
 *  never be referenced again.
 *
 *  External symbols declared in rtio.h
 */

#include "copyright.h"

#include <stdlib.h>

#include "rterror.h"
#include "rtio.h"

#ifndef  NHASH
#ifdef  SMLMEM
#define  NHASH          2039            /* hash table size (prime!) */
#else
#define  NHASH          17117           /* hash table size (prime!) */
#endif
#endif

typedef struct s_head {
        struct s_head  *next;           /* next in hash list */
        int  nl;                        /* links count */
}  S_HEAD;                              /* followed by the string itself */

static S_HEAD  *stab[NHASH];

#define  hash(s)        (shash(s)%NHASH)

#define  string(sp)     ((char *)((sp)+1))

#define  salloc(str)    (S_HEAD *)malloc(sizeof(S_HEAD)+1+strlen(str))

#define  sfree(sp)      free((void *)(sp))


char *
savestr(const char *str)                        /* save a string */
{
        int  hval;
        S_HEAD  *sp;

        if (str == NULL)
                return(NULL);
        if (!*str)
                return "";
        hval = hash(str);
        for (sp = stab[hval]; sp != NULL; sp = sp->next)
                if (!strcmp(str, string(sp))) {
                        sp->nl++;
                        return(string(sp));
                }
        if ((sp = salloc(str)) == NULL) {
                eputs("Out of memory in savestr\n");
                quit(1);
        }
        strcpy(string(sp), str);
        sp->nl = 1;
        sp->next = stab[hval];
        stab[hval] = sp;
        return(string(sp));
}


void
freestr(char *s)                                /* free a string */
{
        int  hval;
        S_HEAD  *spl, *sp;

        if (s == NULL || !*s)
                return;
        hval = hash(s);
        for (spl = NULL, sp = stab[hval]; sp != NULL; spl = sp, sp = sp->next)
                if (s == string(sp)) {
                        if (--sp->nl > 0)
                                return;
                        if (spl != NULL)
                                spl->next = sp->next;
                        else
                                stab[hval] = sp->next;
                        sfree(sp);
                        return;
                }
}


int
shash(const char *s)
{
        int  h = 0;

        while (*s)
                h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
        return(h);
}
Revision:	2.15
Committed:	Mon Jun 23 19:55:51 2025 UTC (3 weeks, 6 days ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 2.14:	+5 -1 lines
Log Message:	perf: Added larger hash table when !SMLMEM
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.15	static const char RCSid[] = "$Id: savestr.c,v 2.14 2023/06/08 17:48:01 greg Exp $";
3	greg	1.1	#endif
4	greg	1.2	/*
5	greg	1.1	* savestr.c - routines for efficient string storage.
6			*
7			* Savestr(s) stores a shared read-only string.
8			* Freestr(s) indicates a client is finished with a string.
9			* All strings must be null-terminated. There is
10			* no imposed length limit.
11			* Strings stored with savestr(s) can be equated
12	greg	2.5	* reliably using their pointer values.
13	greg	1.1	* Calls to savestr(s) and freestr(s) should be
14			* balanced (obviously). The last call to freestr(s)
15			* frees memory associated with the string; it should
16			* never be referenced again.
17			*
18	greg	2.13	* External symbols declared in rtio.h
19	greg	2.5	*/
20
21	greg	2.6	#include "copyright.h"
22	greg	1.1
23	schorsch	2.7	#include <stdlib.h>
24
25	schorsch	2.9	#include "rterror.h"
26			#include "rtio.h"
27	schorsch	2.7
28	greg	1.1	#ifndef NHASH
29	greg	2.15	#ifdef SMLMEM
30	greg	2.10	#define NHASH 2039 /* hash table size (prime!) */
31	greg	2.15	#else
32			#define NHASH 17117 /* hash table size (prime!) */
33			#endif
34	greg	1.1	#endif
35
36			typedef struct s_head {
37			struct s_head next; / next in hash list */
38			int nl; /* links count */
39			} S_HEAD; /* followed by the string itself */
40
41			static S_HEAD *stab[NHASH];
42
43	greg	2.3	#define hash(s) (shash(s)%NHASH)
44	greg	1.1
45			#define string(sp) ((char *)((sp)+1))
46
47			#define salloc(str) (S_HEAD *)malloc(sizeof(S_HEAD)+1+strlen(str))
48
49	greg	2.5	#define sfree(sp) free((void *)(sp))
50	greg	1.1
51
52			char *
53	greg	2.14	savestr(const char str) / save a string */
54	greg	1.1	{
55	greg	2.11	int hval;
56			S_HEAD *sp;
57	greg	1.1
58			if (str == NULL)
59			return(NULL);
60	greg	2.11	if (!*str)
61			return "";
62	greg	2.3	hval = hash(str);
63	greg	1.1	for (sp = stab[hval]; sp != NULL; sp = sp->next)
64			if (!strcmp(str, string(sp))) {
65			sp->nl++;
66			return(string(sp));
67			}
68			if ((sp = salloc(str)) == NULL) {
69			eputs("Out of memory in savestr\n");
70			quit(1);
71			}
72			strcpy(string(sp), str);
73			sp->nl = 1;
74			sp->next = stab[hval];
75			stab[hval] = sp;
76			return(string(sp));
77			}
78
79
80	greg	2.5	void
81	schorsch	2.9	freestr(char s) / free a string */
82	greg	1.1	{
83			int hval;
84	greg	2.11	S_HEAD spl, sp;
85	greg	1.1
86	greg	2.11	if (s == NULL \|\| !*s)
87	greg	1.1	return;
88	greg	2.3	hval = hash(s);
89	greg	1.1	for (spl = NULL, sp = stab[hval]; sp != NULL; spl = sp, sp = sp->next)
90			if (s == string(sp)) {
91			if (--sp->nl > 0)
92			return;
93			if (spl != NULL)
94			spl->next = sp->next;
95			else
96			stab[hval] = sp->next;
97			sfree(sp);
98			return;
99			}
100			}
101
102
103	greg	2.3	int
104	greg	2.14	shash(const char *s)
105	greg	1.1	{
106	greg	2.11	int h = 0;
107	greg	1.1
108			while (*s)
109	greg	2.4	h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
110	greg	2.3	return(h);
111	greg	1.1	}