"Fossies" - the Fresh Open Source Software Archive

Member "tin-2.4.4/src/list.c" (20 Nov 2019, 7314 Bytes) of package /linux/misc/tin-2.4.4.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "list.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.4.3_vs_2.4.4.

    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-2020 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
   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
   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
  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 *
  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
  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 *
  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
  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
  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 */