"Fossies" - the Fresh Open Source Software Archive

Member "tin-2.4.1/src/list.c" (12 Oct 2016, 7728 Bytes) of archive /linux/misc/tin-2.4.1.tar.gz:


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.0_vs_2.4.1.

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