1 /*
2 * Project : tin - a Usenet reader
3 * Module : hashstr.c
4 * Author : I. Lea & R. Skrenta
5 * Created : 1991-04-01
6 * Updated : 2020-05-13
7 * Notes :
8 *
9 * Copyright (c) 1991-2021 Iain Lea <iain@bricbrac.de>, Rich Skrenta <skrenta@pbm.com>
10
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 *
17 * 1. Redistributions of source code must retain the above copyright notice,
18 * this list of conditions and the following disclaimer.
19 *
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in the
22 * documentation and/or other materials provided with the distribution.
23 *
24 * 3. Neither the name of the copyright holder nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
32 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
33 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
36 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
37 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
38 * POSSIBILITY OF SUCH DAMAGE.
39 */
40
41
42 #ifndef TIN_H
43 # include "tin.h"
44 #endif /* !TIN_H */
45
46 /*
47 * Maintain a table of all strings we have seen.
48 * If a new string comes in, add it to the table and return a pointer
49 * to it. If we've seen it before, just return the pointer to it.
50 *
51 * Usage: hash_str("some string") returns char *
52 *
53 * Spillovers are chained on the end
54 */
55
56 static struct t_hashnode *table[HASHNODE_TABLE_SIZE];
57 static struct t_hashnode *add_string(const char *s);
58
59 char *
hash_str(const char * s)60 hash_str(
61 const char *s)
62 {
63 const unsigned char *t = (const unsigned char *) s;
64 int len = 0;
65 long h; /* result of hash: index into hash table */
66 struct t_hashnode **p; /* used to descend the spillover structs */
67
68 if (s == NULL)
69 return NULL;
70
71 h = 0;
72 while (*t) {
73 h = (h << 1) ^ *t++;
74 if (++len & 7)
75 continue;
76 h %= (long) HASHNODE_TABLE_SIZE;
77 }
78 h %= (long) HASHNODE_TABLE_SIZE;
79
80 p = &table[h];
81
82 while (*p) {
83 if (STRCMPEQ(s, (*p)->txt))
84 return (*p)->txt;
85 p = &(*p)->next;
86 }
87
88 *p = add_string(s);
89 return (*p)->txt; /* Return ptr to text, _not_ the struct */
90 }
91
92
93 /*
94 * Add a string to the hash table
95 * Each entry will have the following structure:
96 *
97 * t_hashnode *next Pointer to the next hashnode in chain
98 * int aptr 'magic' ptr used to speed subj threading
99 * T The text itself. The ptr that hash_str()
100 * E returns points here - the earlier fields
101 * X are 'hidden'.
102 * T
103 * \0 String terminator
104 */
105 static struct t_hashnode *
add_string(const char * s)106 add_string(
107 const char *s)
108 {
109 struct t_hashnode *p;
110
111 p = my_malloc(sizeof(struct t_hashnode) + strlen(s));
112
113 p->next = (struct t_hashnode *) 0;
114 p->aptr = -1; /* -1 is the default value */
115
116 strcpy(p->txt, s); /* Copy in the text */
117
118 return p;
119 }
120
121
122 void
hash_init(void)123 hash_init(
124 void)
125 {
126 int i;
127
128 for (i = 0; i < HASHNODE_TABLE_SIZE; i++)
129 table[i] = (struct t_hashnode *) 0;
130 }
131
132
133 void
hash_reclaim(void)134 hash_reclaim(
135 void)
136 {
137 int i;
138 struct t_hashnode *p, *next;
139
140 for (i = 0; i < HASHNODE_TABLE_SIZE; i++) {
141 if (table[i] != NULL) {
142 p = table[i];
143 while (p != NULL) {
144 next = p->next;
145 free(p);
146 p = next;
147 }
148 table[i] = (struct t_hashnode *) 0;
149 }
150 }
151 }
152