home *** CD-ROM | disk | FTP | other *** search
/ linuxmafia.com 2016 / linuxmafia.com.tar / linuxmafia.com / pub / linux / backup / star-1.3.1.tar.gz / star-1.3.1.tar / star-1.3.1 / star / lhash.c < prev    next >
C/C++ Source or Header  |  2000-05-07  |  3KB  |  136 lines
  1. /* @(#)lhash.c    1.8 00/05/07 Copyright 1988 J. Schilling */
  2. #ifndef lint
  3. static    char sccsid[] =
  4.     "@(#)lhash.c    1.8 00/05/07 Copyright 1988 J. Schilling";
  5. #endif
  6. /*
  7.  *    Copyright (c) 1988 J. Schilling
  8.  */
  9. /*
  10.  * This program is free software; you can redistribute it and/or modify
  11.  * it under the terms of the GNU General Public License as published by
  12.  * the Free Software Foundation; either version 2, or (at your option)
  13.  * any later version.
  14.  *
  15.  * This program is distributed in the hope that it will be useful,
  16.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18.  * GNU General Public License for more details.
  19.  *
  20.  * You should have received a copy of the GNU General Public License
  21.  * along with this program; see the file COPYING.  If not, write to
  22.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  23.  */
  24.  
  25. /*
  26.  * Hash table name lookup.
  27.  *
  28.  *    Implemented 1988 with help from B. Mueller-Zimmermann
  29.  *
  30.  *    hash_build(fp, nqueue) FILE *fp;
  31.  *
  32.  *        Liest das File `fp' zeilenweise. Jede Zeile enthaelt genau
  33.  *        einen Namen. Blanks werden nicht entfernt. Alle so
  34.  *        gefundenen Namen werden in der Hashtabelle gespeichert.
  35.  *        `nqueue' ist ein tuning parameter und gibt die Zahl der
  36.  *        Hash-queues an. Pro Hashqueue werden 4 Bytes benoetigt.
  37.  *
  38.  *    hash_lookup(str) char *str;
  39.  *
  40.  *        Liefert TRUE, wenn der angegebene String in der
  41.  *        Hashtabelle vorkommt.
  42.  *
  43.  * Scheitert malloc(), gibt es eine Fehlermeldung und exit().
  44.  */
  45.  
  46. #include <mconfig.h>
  47. #include <stdio.h>
  48. #include <standard.h>
  49. #include "star.h"
  50. #include <stdxlib.h>
  51. #include <strdefs.h>
  52. #include <schily.h>
  53.  
  54. extern    BOOL    notpat;
  55.  
  56. static struct h_elem {
  57.     struct h_elem *h_next;
  58.     char             h_data[1];            /* Variable size. */
  59. } **h_tab;
  60.  
  61. static unsigned    h_size;
  62.  
  63. EXPORT    void    hash_build    __PR((FILE * fp, unsigned int size));
  64. EXPORT    BOOL    hash_lookup    __PR((char* str));
  65. LOCAL    int    hashval        __PR((unsigned char* str, unsigned int maxsize));
  66. LOCAL    struct h_elem* _malloc    __PR((unsigned int len));
  67.  
  68. EXPORT void
  69. hash_build(fp, size)
  70.     FILE    *fp;
  71.     unsigned size;
  72. {
  73.     register struct h_elem    *hp;
  74.     register    int    i;
  75.     register    int    len;
  76.     register    int    hv;
  77.             char    buf[PATH_MAX+1];
  78.  
  79.     h_size = size;
  80.     h_tab = (struct h_elem **)_malloc(size * sizeof (struct h_elem *));
  81.     for (i=0; i<size; i++) h_tab[i] = 0;
  82.     while ((len = fgetline(fp, buf, sizeof buf)) >= 0) {
  83.         if (len == 0)
  84.             continue;
  85.         if (len >= PATH_MAX) {
  86.             errmsgno(EX_BAD, "%s: Name too long (%d > %d).\n",
  87.                             buf, len, PATH_MAX);
  88.             continue;
  89.         }
  90.         hp = _malloc((unsigned)len + 1 + sizeof (struct h_elem *));
  91.         strcpy(hp->h_data, buf);
  92.         hv = hashval((unsigned char *)buf, size);
  93.         hp->h_next = h_tab[hv];
  94.         h_tab[hv] = hp;
  95.     }
  96. }
  97.  
  98. EXPORT BOOL
  99. hash_lookup(str)
  100.     char    *str;
  101. {
  102.     register struct h_elem *hp;
  103.     register int        hv;
  104.  
  105.     hv = hashval((unsigned char *)str, h_size);
  106.     for (hp = h_tab[hv]; hp; hp=hp->h_next)
  107.         if (streql(str, hp->h_data))
  108.         return (!notpat);
  109.     return (notpat);
  110. }
  111.  
  112. LOCAL int
  113. hashval(str, maxsize)
  114.     register unsigned char *str;
  115.          unsigned    maxsize;
  116. {
  117.     register int    sum = 0;
  118.     register int    i;
  119.     register int    c;
  120.  
  121.     for (i=0; (c = *str++) != '\0'; i++)
  122.         sum ^= (c << (i&7));
  123.     return sum % maxsize;
  124. }
  125.  
  126. LOCAL struct h_elem *
  127. _malloc(len)
  128.     unsigned len;
  129. {
  130.     char *ret;
  131.  
  132.     if ((ret = malloc(len)) == NULL)
  133.         comerr("No memory for list option.\n");
  134.     return (struct h_elem *)ret;
  135. }
  136.