src/common/savestr.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#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 standard.h
 */

/* ====================================================================
 * The Radiance Software License, Version 1.0
 *
 * Copyright (c) 1990 - 2002 The Regents of the University of California,
 * through Lawrence Berkeley National Laboratory.   All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *         notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *           if any, must include the following acknowledgment:
 *             "This product includes Radiance software
 *                 (http://radsite.lbl.gov/)
 *                 developed by the Lawrence Berkeley National Laboratory
 *               (http://www.lbl.gov/)."
 *       Alternately, this acknowledgment may appear in the software itself,
 *       if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
 *       and "The Regents of the University of California" must
 *       not be used to endorse or promote products derived from this
 *       software without prior written permission. For written
 *       permission, please contact [email protected].
 *
 * 5. Products derived from this software may not be called "Radiance",
 *       nor may "Radiance" appear in their name, without prior written
 *       permission of Lawrence Berkeley National Laboratory.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.   IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
 * information on Lawrence Berkeley National Laboratory, please see
 * <http://www.lbl.gov/>.
 */

#ifndef  NHASH
#define  NHASH          509             /* hash table size (prime!) */
#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)

extern char  *savestr(), *strcpy(), *malloc();

#define  NULL           0

#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(str)                            /* save a string */
char  *str;
{
        register int  hval;
        register S_HEAD  *sp;

        if (str == NULL)
                return(NULL);
        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(s)                              /* free a string */
char  *s;
{
        int  hval;
        register S_HEAD  *spl, *sp;

        if (s == NULL)
                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(s)
register char  *s;
{
        register int  h = 0;

        while (*s)
                h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
        return(h);
}
Revision:	2.5
Committed:	Sat Feb 22 02:07:22 2003 UTC (22 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.4:	+62 -8 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.5	static const char RCSid[] = "$Id$";
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.5	* External symbols declared in standard.h
19			*/
20
21			/* ====================================================================
22			* The Radiance Software License, Version 1.0
23			*
24			* Copyright (c) 1990 - 2002 The Regents of the University of California,
25			* through Lawrence Berkeley National Laboratory. All rights reserved.
26			*
27			* Redistribution and use in source and binary forms, with or without
28			* modification, are permitted provided that the following conditions
29			* are met:
30			*
31			* 1. Redistributions of source code must retain the above copyright
32			* notice, this list of conditions and the following disclaimer.
33			*
34			* 2. Redistributions in binary form must reproduce the above copyright
35			* notice, this list of conditions and the following disclaimer in
36			* the documentation and/or other materials provided with the
37			* distribution.
38			*
39			* 3. The end-user documentation included with the redistribution,
40			* if any, must include the following acknowledgment:
41			* "This product includes Radiance software
42			* (http://radsite.lbl.gov/)
43			* developed by the Lawrence Berkeley National Laboratory
44			* (http://www.lbl.gov/)."
45			* Alternately, this acknowledgment may appear in the software itself,
46			* if and wherever such third-party acknowledgments normally appear.
47			*
48			* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
49			* and "The Regents of the University of California" must
50			* not be used to endorse or promote products derived from this
51			* software without prior written permission. For written
52			* permission, please contact [email protected].
53			*
54			* 5. Products derived from this software may not be called "Radiance",
55			* nor may "Radiance" appear in their name, without prior written
56			* permission of Lawrence Berkeley National Laboratory.
57			*
58			* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
59			* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
60			* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
61			* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
62			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
63			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
64			* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
65			* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
66			* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
67			* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
68			* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69			* SUCH DAMAGE.
70			* ====================================================================
71			*
72			* This software consists of voluntary contributions made by many
73			* individuals on behalf of Lawrence Berkeley National Laboratory. For more
74			* information on Lawrence Berkeley National Laboratory, please see
75			* <http://www.lbl.gov/>.
76	greg	1.1	*/
77
78			#ifndef NHASH
79			#define NHASH 509 /* hash table size (prime!) */
80			#endif
81
82			typedef struct s_head {
83			struct s_head next; / next in hash list */
84			int nl; /* links count */
85			} S_HEAD; /* followed by the string itself */
86
87			static S_HEAD *stab[NHASH];
88
89	greg	2.3	#define hash(s) (shash(s)%NHASH)
90	greg	1.3
91	greg	1.1	extern char savestr(), strcpy(), *malloc();
92
93			#define NULL 0
94
95			#define string(sp) ((char *)((sp)+1))
96
97			#define salloc(str) (S_HEAD *)malloc(sizeof(S_HEAD)+1+strlen(str))
98
99	greg	2.5	#define sfree(sp) free((void *)(sp))
100	greg	1.1
101
102			char *
103			savestr(str) /* save a string */
104			char *str;
105			{
106			register int hval;
107			register S_HEAD *sp;
108
109			if (str == NULL)
110			return(NULL);
111	greg	2.3	hval = hash(str);
112	greg	1.1	for (sp = stab[hval]; sp != NULL; sp = sp->next)
113			if (!strcmp(str, string(sp))) {
114			sp->nl++;
115			return(string(sp));
116			}
117			if ((sp = salloc(str)) == NULL) {
118			eputs("Out of memory in savestr\n");
119			quit(1);
120			}
121			strcpy(string(sp), str);
122			sp->nl = 1;
123			sp->next = stab[hval];
124			stab[hval] = sp;
125			return(string(sp));
126			}
127
128
129	greg	2.5	void
130	greg	1.1	freestr(s) /* free a string */
131			char *s;
132			{
133			int hval;
134			register S_HEAD spl, sp;
135
136			if (s == NULL)
137			return;
138	greg	2.3	hval = hash(s);
139	greg	1.1	for (spl = NULL, sp = stab[hval]; sp != NULL; spl = sp, sp = sp->next)
140			if (s == string(sp)) {
141			if (--sp->nl > 0)
142			return;
143			if (spl != NULL)
144			spl->next = sp->next;
145			else
146			stab[hval] = sp->next;
147			sfree(sp);
148			return;
149			}
150			}
151
152
153	greg	2.3	int
154			shash(s)
155	greg	1.1	register char *s;
156			{
157			register int h = 0;
158
159			while (*s)
160	greg	2.4	h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
161	greg	2.3	return(h);
162	greg	1.1	}