tin  2.6.1
About: TIN is a threaded NNTP and spool based UseNet newsreader.
  Fossies Dox: tin-2.6.1.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

list.c
Go to the documentation of this file.
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-2022 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
50static int group_hash[TABLE_SIZE]; /* group name --> active[] */
51
52/*
53 * local prototypes
54 */
55static 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
61void
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 */
82unsigned long
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 */
105int
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 */
153struct t_group *
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 */
171static t_bool
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 */
212struct t_group *
214 const char *group)
215{
216 if (num_active >= max_active) /* Grow memory area if needed */
218
219 if (!(group_add_to_hash(group, num_active)))
220 return NULL;
221
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 */
231void
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
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) {
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) {
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 */
283static void
284debug_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 */
unsigned t_bool
Definition: bool.h:77
#define TRUE
Definition: bool.h:74
#define FALSE
Definition: bool.h:70
#define DEBUG_MISC
Definition: debug.h:54
int * my_group
Definition: memory.c:64
t_menu selmenu
Definition: select.c:84
int max_active
Definition: memory.c:50
char newsrc[PATH_LEN]
Definition: init.c:96
struct t_config tinrc
Definition: init.c:192
unsigned short debug
Definition: debug.c:51
int num_active
Definition: memory.c:51
struct t_group * active
Definition: memory.c:66
struct t_group * group_find(const char *group_name, t_bool ignore_case)
Definition: list.c:154
void group_rehash(t_bool yanked_out)
Definition: list.c:232
int find_group_index(const char *group, t_bool ignore_case)
Definition: list.c:106
static int group_hash[1409]
Definition: list.c:50
unsigned long hash_groupname(const char *group)
Definition: list.c:83
struct t_group * group_add(const char *group)
Definition: list.c:213
static t_bool group_add_to_hash(const char *groupname, int idx)
Definition: list.c:172
void init_group_hash(void)
Definition: list.c:62
void expand_active(void)
Definition: memory.c:152
void str_lwr(char *str)
Definition: string.c:291
char * my_strdup(const char *str)
Definition: string.c:139
int strcasecmp(const char *p, const char *q)
Definition: string.c:475
static t_bool yanked_out
Definition: select.c:60
const char * name
Definition: signal.c:117
int strip_bogus
Definition: tinrc.h:163
t_bool show_only_unread_groups
Definition: tinrc.h:244
Definition: tin.h:1816
t_bool bogus
Definition: tin.h:1831
int next
Definition: tin.h:1832
t_bool subscribed
Definition: tin.h:1829
char * name
Definition: tin.h:1817
int max
Definition: tin.h:2057
#define TABLE_SIZE
Definition: tin.h:866
#define STRCMPEQ(s1, s2)
Definition: tin.h:822
#define for_each_group(x)
Definition: tin.h:2259
#define BOGUS_SHOW
Definition: tin.h:1212