"Fossies" - the Fresh Open Source Software Archive

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