Annotation of src/usr.bin/cvs/strtab.c, Revision 1.7
1.7 ! xsa 1: /* $OpenBSD: strtab.c,v 1.6 2005/07/25 12:05:43 xsa Exp $ */
1.1 jfb 2: /*
3: * Copyright (c) 2005 Jean-Francois Brousseau <jfb@openbsd.org>
4: * All rights reserved.
5: *
6: * Redistribution and use in source and binary forms, with or without
7: * modification, are permitted provided that the following conditions
8: * are met:
9: *
10: * 1. Redistributions of source code must retain the above copyright
11: * notice, this list of conditions and the following disclaimer.
12: * 2. The name of the author may not be used to endorse or promote products
13: * derived from this software without specific prior written permission.
14: *
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
16: * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
17: * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
18: * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
21: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
23: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24: * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25: */
26: /*
27: * The hash table code uses the 32-bit Fowler/Noll/Vo (FNV-1) hash algorithm
28: * for indexing.
29: * http://www.isthe.com/chongo/tech/comp/fnv/
30: */
31:
32: #include <sys/types.h>
33: #include <sys/queue.h>
34:
35: #include <errno.h>
36: #include <stdio.h>
37: #include <stdlib.h>
1.5 xsa 38: #include <string.h>
1.1 jfb 39: #include <unistd.h>
40:
41: #include "cvs.h"
42: #include "log.h"
1.2 jfb 43: #include "strtab.h"
1.1 jfb 44:
1.6 xsa 45: #define CVS_STRTAB_HASHBITS 8
46: #define CVS_STRTAB_NBUCKETS (1 << CVS_STRTAB_HASHBITS)
47: #define CVS_STRTAB_FNVPRIME 0x01000193
48: #define CVS_STRTAB_FNVINIT 0x811c9dc5
1.1 jfb 49:
50: struct cvs_str {
1.6 xsa 51: char *cs_str;
52: int cs_ref;
53: SLIST_ENTRY(cvs_str) cs_link;
1.1 jfb 54: };
55:
56: SLIST_HEAD(cvs_slist, cvs_str);
57:
1.6 xsa 58: static struct cvs_slist cvs_strtab[CVS_STRTAB_NBUCKETS];
1.1 jfb 59:
60:
1.6 xsa 61: static struct cvs_str *cvs_strtab_insert(const char *);
62: static struct cvs_str *cvs_strtab_lookup(const char *);
63: static u_int32_t cvs_strtab_hash(const char *);
64: static void cvs_strtab_free(const char *);
1.1 jfb 65:
66:
67:
68: /*
69: * cvs_strdup()
70: *
71: * Simple interface to the string table.
72: */
1.6 xsa 73: char *
1.1 jfb 74: cvs_strdup(const char *s)
75: {
76: struct cvs_str *csp;
77:
1.4 joris 78: if ((csp = cvs_strtab_lookup(s)) == NULL) {
79: if ((csp = cvs_strtab_insert(s)) == NULL)
80: return (NULL);
81: } else {
1.1 jfb 82: csp->cs_ref++;
1.4 joris 83: }
1.1 jfb 84:
85: return (csp->cs_str);
86: }
87:
88: /*
89: * cvs_strfree()
90: */
91: void
1.2 jfb 92: cvs_strfree(const char *s)
1.1 jfb 93: {
94: cvs_strtab_free(s);
95: }
96:
97: /*
98: *
99: */
100: void
101: cvs_strtab_init(void)
102: {
103: int i;
104:
105: for (i = 0; i < CVS_STRTAB_NBUCKETS; i++)
106: SLIST_INIT(&cvs_strtab[i]);
107: }
108:
109: /*
110: * cvs_strtab_cleanup()
111: *
112: */
113: void
114: cvs_strtab_cleanup(void)
115: {
116: int i, unfreed;
117: struct cvs_str *sp;
118:
119: unfreed = 0;
120: for (i = 0; i < CVS_STRTAB_NBUCKETS; i++) {
1.3 joris 121: SLIST_FOREACH(sp, &cvs_strtab[i], cs_link) {
122: cvs_log(LP_DEBUG, "string '%s' not freed", sp->cs_str);
1.1 jfb 123: unfreed++;
1.3 joris 124: }
1.1 jfb 125: }
126:
127: if (unfreed > 0)
128: cvs_log(LP_WARN, "%d unfreed string references in string table",
129: unfreed);
130: }
131:
132: /*
133: * cvs_strtab_insert()
134: *
135: * Insert the string <str> in the string table.
136: */
1.7 ! xsa 137: static struct cvs_str *
1.1 jfb 138: cvs_strtab_insert(const char *str)
139: {
140: u_int32_t h;
141: struct cvs_str *sp;
142:
143: if ((sp = (struct cvs_str *)malloc(sizeof(*sp))) == NULL) {
144: cvs_log(LP_ERRNO, "failed to insert string `%s'", str);
145: return (NULL);
146: }
147:
148: if ((sp->cs_str = strdup(str)) == NULL) {
149: free(sp);
150: return (NULL);
151: }
152:
153: h = cvs_strtab_hash(str);
154:
155: SLIST_INSERT_HEAD(&cvs_strtab[h], sp, cs_link);
156:
157: sp->cs_ref = 1;
158: return (sp);
159: }
160:
161: /*
162: * cvs_strtab_hash()
163: *
164: * Generate a hash value from the string <str>.
165: * The resulting hash value is bitwise AND'ed with the appropriate mask so
166: * the returned index does not go out of the boundaries of the hash table.
167: */
168: static u_int32_t
169: cvs_strtab_hash(const char *str)
170: {
171: const char *np;
172: u_int32_t h;
173:
174: h = CVS_STRTAB_FNVINIT;
175: for (np = str; *np != '\0'; np++) {
176: h *= CVS_STRTAB_FNVPRIME;
177: h ^= (u_int32_t)*np;
178: }
179:
180: return (h & (CVS_STRTAB_NBUCKETS - 1));
181: }
182:
183: /*
184: * cvs_strtab_lookup()
185: *
186: * Lookup the string <str> in the string table. If the corresponding entry
187: * is found, a pointer to the string is returned and the entry's reference
188: * count is increased.
189: */
1.7 ! xsa 190: static struct cvs_str *
1.1 jfb 191: cvs_strtab_lookup(const char *str)
192: {
193: u_int32_t h;
194: struct cvs_str *sp;
195:
196: h = cvs_strtab_hash(str);
197:
198: SLIST_FOREACH(sp, &(cvs_strtab[h]), cs_link)
199: if (strcmp(str, sp->cs_str) == 0) {
200: break;
201: }
202:
203: return (sp);
204: }
205:
206: /*
207: * cvs_strtab_free()
208: *
209: * Release a reference to the string <str>. If the reference count reaches 0,
210: * the string is removed from the table and freed.
211: */
212: static void
213: cvs_strtab_free(const char *str)
214: {
215: u_int32_t h;
216: struct cvs_str *sp;
217:
218: if ((sp = cvs_strtab_lookup(str)) == NULL) {
219: cvs_log(LP_WARN, "attempt to free unregistered string `%s'",
220: str);
221: return;
222: }
223:
224: sp->cs_ref--;
225: if (sp->cs_ref == 0) {
226: /* no more references, free the file */
1.2 jfb 227: h = cvs_strtab_hash(sp->cs_str);
1.1 jfb 228:
229: SLIST_REMOVE(&(cvs_strtab[h]), sp, cvs_str, cs_link);
230: free(sp->cs_str);
231: free(sp);
232: }
233: }
![[BACK]](/icons/back.gif){kind=icon}
Return to strtab.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / cvs