1 /*
2 * Project : tin - a Usenet reader
3 * Module : list.c
4 * Author : I. Lea
5 * Created : 1993-12-18
6 * Updated : 2019-01-18
7 * Notes : Low level functions handling the active[] list and its group_hash index
8 *
9 * Copyright (c) 1993-2021 Iain Lea <iain@bricbrac.de>
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 *
16 * 1. Redistributions of source code must retain the above copyright notice,
17 * this list of conditions and the following disclaimer.
18 *
19 * 2. Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * 3. Neither the name of the copyright holder nor the names of its
24 * contributors may be used to endorse or promote products derived from
25 * this software without specific prior written permission.
26 *
27 * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
31 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
32 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
33 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
34 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
35 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
36 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37 * POSSIBILITY OF SUCH DAMAGE.
38 */
39
40
41 #ifndef TIN_H
42 # include "tin.h"
43 #endif /* !TIN_H */
44 #ifdef DEBUG
45 # ifndef TCURSES_H
46 # include "tcurses.h"
47 # endif /* !TCURSES_H */
48 #endif /* DEBUG */
49
50 static int group_hash[TABLE_SIZE]; /* group name --> active[] */
51
52 /*
53 * local prototypes
54 */
55 static t_bool group_add_to_hash(const char *groupname, int idx);
56 #ifdef DEBUG
57 static void debug_print_active_hash(void);
58 #endif /* DEBUG */
59
60
61 void
init_group_hash(void)62 init_group_hash(
63 void)
64 {
65 int i;
66
67 #if 0
68 if (num_active == -1) {
69 #endif /* 0 */
70 num_active = 0;
71 for (i = 0; i < TABLE_SIZE; i++)
72 group_hash[i] = -1;
73 #if 0
74 }
75 #endif /* 0 */
76 }
77
78
79 /*
80 * hash group name for fast lookup later
81 */
82 unsigned long
hash_groupname(const char * group)83 hash_groupname(
84 const char *group)
85 {
86 unsigned long hash_value = 0L;
87 unsigned int len = 0;
88 const unsigned char *ptr = (const unsigned char *) group;
89
90 while (*ptr) {
91 hash_value = (hash_value << 1) ^ *ptr++;
92 if (++len & 7)
93 continue;
94 hash_value %= TABLE_SIZE;
95 }
96 hash_value %= TABLE_SIZE;
97
98 return hash_value;
99 }
100
101
102 /*
103 * Find group name in active[] array and return index otherwise -1
104 */
105 int
find_group_index(const char * group,t_bool ignore_case)106 find_group_index(
107 const char *group,
108 t_bool ignore_case)
109 {
110 char *group_lcase;
111 int i;
112 unsigned long h;
113
114 group_lcase = my_strdup(group);
115 str_lwr(group_lcase);
116
117 h = hash_groupname(group_lcase);
118 i = group_hash[h];
119
120 free(group_lcase);
121
122 /*
123 * hash linked list chaining
124 * first try to find group in original spelling only
125 */
126 while (i >= 0) {
127 if (STRCMPEQ(group, active[i].name))
128 return i;
129
130 i = active[i].next;
131 }
132
133 /*
134 * group not found in original spelling, try to find not case sensitive
135 * if desired
136 */
137 if (ignore_case) {
138 i = group_hash[h];
139 while (i >= 0) {
140 if (!strcasecmp(group, active[i].name))
141 return i;
142 i = active[i].next;
143 }
144 }
145
146 return -1;
147 }
148
149
150 /*
151 * Find group name in active[] array and return pointer to element
152 */
153 struct t_group *
group_find(const char * group_name,t_bool ignore_case)154 group_find(
155 const char *group_name,
156 t_bool ignore_case)
157 {
158 int i;
159
160 if ((i = find_group_index(group_name, ignore_case)) != -1)
161 return &active[i];
162
163 return (struct t_group *) 0;
164 }
165
166
167 /*
168 * Hash the groupname into group_hash[]
169 * Return FALSE if the group is already present
170 */
171 static t_bool
group_add_to_hash(const char * groupname,int idx)172 group_add_to_hash(
173 const char *groupname,
174 int idx)
175 {
176 char *groupname_lcase;
177 unsigned long h;
178
179 groupname_lcase = my_strdup(groupname);
180 str_lwr(groupname_lcase);
181 h = hash_groupname(groupname_lcase);
182 free(groupname_lcase);
183
184 if (group_hash[h] == -1)
185 group_hash[h] = idx;
186 else {
187 int i;
188
189 /*
190 * hash linked list chaining
191 */
192 for (i = group_hash[h]; active[i].next >= 0; i = active[i].next) {
193 if (STRCMPEQ(active[i].name, groupname))
194 return FALSE; /* Already in chain */
195 }
196
197 if (STRCMPEQ(active[i].name, groupname))
198 return FALSE; /* Already on end of chain */
199
200 active[i].next = idx; /* Append to chain */
201 }
202
203 return TRUE;
204 }
205
206
207 /*
208 * Make sure memory available for next active slot
209 * Adds group to the group_hash of active groups and name it
210 * Return pointer to next free active slot or NULL if duplicate
211 */
212 struct t_group *
group_add(const char * group)213 group_add(
214 const char *group)
215 {
216 if (num_active >= max_active) /* Grow memory area if needed */
217 expand_active();
218
219 if (!(group_add_to_hash(group, num_active)))
220 return NULL;
221
222 active[num_active].name = my_strdup(group);
223
224 return &active[num_active++]; /* NB num_active incremented here */
225 }
226
227
228 /*
229 * Reinitialise group_hash[] after change to ordering of active[]
230 */
231 void
group_rehash(t_bool yanked_out)232 group_rehash(
233 t_bool yanked_out)
234 {
235 int i;
236 int save_num_active = num_active;
237
238 init_group_hash(); /* Clear the existing hash */
239 num_active = save_num_active; /* init_group_hash() resets this */
240
241 for_each_group(i)
242 active[i].next = -1;
243
244 /*
245 * Now rehash each group and rebuild my_group[]
246 */
247 selmenu.max = 0;
248
249 for_each_group(i) {
250 group_add_to_hash(active[i].name, i);
251
252 /*
253 * cf: similar code to toggle_my_groups()
254 * Add a group if all groups are yanked in
255 * If we are yanked out, only consider subscribed groups
256 * Then also honour show_only_unread and BOGUS_SHOW
257 */
258 if (!yanked_out) {
259 my_group[selmenu.max++] = i;
260 continue;
261 }
262
263 if (active[i].subscribed) {
264 if (tinrc.show_only_unread_groups) {
265 if (active[i].newsrc.num_unread > 0 || (active[i].bogus && tinrc.strip_bogus == BOGUS_SHOW))
266 my_group[selmenu.max++] = i;
267 } else
268 my_group[selmenu.max++] = i;
269 }
270 }
271
272 #ifdef DEBUG
273 if (debug & DEBUG_MISC)
274 debug_print_active_hash();
275 #endif /* DEBUG */
276 }
277
278
279 #ifdef DEBUG
280 /*
281 * Prints out hash distribution of active[]
282 */
283 static void
debug_print_active_hash(void)284 debug_print_active_hash(
285 void)
286 {
287 int empty = 0;
288 int collisions[32];
289 int i;
290
291 for (i = 0; i < 32; i++)
292 collisions[i] = 0;
293
294 for (i = 0; i < TABLE_SIZE; i++) {
295 /* my_printf("HASH[%4d] ", i); */
296
297 if (group_hash[i] == -1) {
298 /* my_printf("EMPTY\n"); */
299 empty++;
300 } else {
301 int j;
302 int number = 0;
303
304 for (j = group_hash[i]; active[j].next >= 0; j = active[j].next)
305 number++;
306
307 if (number > 31)
308 fprintf(stderr, "MEGA HASH COLLISION > 31 HASH[%d]=[%d]!!!\n", i, number);
309 else
310 collisions[number]++;
311 }
312 }
313
314 fprintf(stderr, "HashTable Active=[%d] Size=[%d] Filled=[%d] Empty=[%d]\n",
315 num_active, TABLE_SIZE, TABLE_SIZE - empty, empty);
316 fprintf(stderr, "00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32\n");
317 fprintf(stderr, "--------------------------------------------------------------------------------------------------\n");
318 for (i = 0; i < 32; i++)
319 fprintf(stderr, "%2d ", collisions[i]);
320 fprintf(stderr, "\n");
321 sleep(4);
322 }
323 #endif /* DEBUG */
324