"Fossies" - the Fresh Open Source Software Archive

Member "ne-3.2.1/src/syn_hash.c" (30 Sep 2019, 3362 Bytes) of package /linux/misc/ne-3.2.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 "syn_hash.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 3.1.2_vs_3.2.0.

    1 /* Syntax highlighting from Joe's Own Editor: Simple hash tables.
    2 
    3     Copyright (C) 1992 Joseph H. Allen
    4     Copyright (C) 2009-2019 Todd M. Lewis and Sebastiano Vigna
    5 
    6     This file is part of ne, the nice editor.
    7 
    8     This library is free software; you can redistribute it and/or modify it
    9     under the terms of the GNU General Public License as published by
   10     the Free Software Foundation; either version 3 of the License, or (at your
   11     option) any later version.
   12 
   13     This library is distributed in the hope that it will be useful, but
   14     WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   15     or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   16     for more details.
   17 
   18     You should have received a copy of the GNU General Public License
   19     along with this program; if not, see <http://www.gnu.org/licenses/>.  */
   20 
   21 
   22 #include <stdio.h>
   23 #include <stdlib.h>
   24 #include <stddef.h>
   25 #include <string.h>
   26 
   27 #define PARAMS(protos) protos
   28 #include "syn_types.h"
   29 #include "syn_hash.h"
   30 #include "syn_regex.h"
   31 #include "syn_utf8.h"
   32 #include "syn_utils.h"
   33 
   34 static HENTRY *freentry = NULL;
   35 
   36 /* Compute hash value of string */
   37 
   38 #define hnext(accu, c) (((accu) << 4) + ((accu) >> 28) + (c))
   39 
   40 unsigned long hash(unsigned char *s)
   41 {
   42     unsigned long accu = 0;
   43 
   44     while (*s) {
   45         accu = hnext(accu, *s++);
   46     }
   47     return accu;
   48 }
   49 
   50 /* Create hash table */
   51 
   52 HASH *htmk(int len)
   53 {
   54     HASH *t = (HASH *) joe_malloc(sizeof(HASH));
   55     t->nentries = 0;
   56     t->len = len;
   57     t->tab = (HENTRY **) joe_calloc(sizeof(HENTRY *), len);
   58     return t;
   59 }
   60 
   61 /* Delete hash table.  Only the hash table is deleted, not the names and values */
   62 
   63 void htrm(HASH *ht)
   64 {
   65     int x;
   66     for (x = 0; x != ht->len; ++x) {
   67         HENTRY *p, *n;
   68         for (p = ht->tab[x]; p; p = n) {
   69             n = p->next;
   70             p->next = freentry;
   71             freentry = p;
   72         }
   73     }
   74     joe_free(ht->tab);
   75     joe_free(ht);
   76 }
   77 
   78 /* Expand hash table */
   79 
   80 void htexpand(HASH *h)
   81 {
   82     unsigned x;
   83     /* Allocate new table */
   84     unsigned new_size = h->len * 2;
   85     HENTRY **new_table = (HENTRY **)joe_calloc(new_size, sizeof(HENTRY *));
   86     /* Copy entries from old table to new */
   87     for (x = 0; x != h->len; ++x) {
   88         HENTRY *e;
   89         while ((e = h->tab[x])) {
   90             h->tab[x] = e->next;
   91             e->next = new_table[e->hash_val & (new_size - 1)];
   92             new_table[e->hash_val & (new_size - 1)] = e;
   93         }
   94     }
   95     /* Replace old table with new */
   96     free(h->tab);
   97     h->tab = new_table;
   98     h->len = new_size;
   99 }
  100 
  101 /* Bind a value to a name.  This does not check for duplicate entries.  The
  102  * name and value are not duplicated: it's up to you to keep them around for
  103  * the life of the hash table. */
  104 
  105 void *htadd(HASH *ht, unsigned char *name, void *val)
  106 {
  107     unsigned hval = hash(name);
  108     unsigned idx = hval & (ht->len - 1);
  109     HENTRY *entry;
  110     int x;
  111 
  112     if (!freentry) {
  113         entry = (HENTRY *) joe_malloc(sizeof(HENTRY) * 64);
  114         for (x = 0; x != 64; ++x) {
  115             entry[x].next = freentry;
  116             freentry = entry + x;
  117         }
  118     }
  119     entry = freentry;
  120     freentry = entry->next;
  121     entry->next = ht->tab[idx];
  122     ht->tab[idx] = entry;
  123     entry->name = name;
  124     entry->val = val;
  125     entry->hash_val = hval;
  126     if (++ht->nentries == (ht->len >> 1) + (ht->len >> 2))
  127         htexpand(ht);
  128     return val;
  129 }
  130 
  131 /* Return value associated with name or NULL if there is none */
  132 
  133 void *htfind(HASH *ht, unsigned char *name)
  134 {
  135     HENTRY *e;
  136 
  137     for (e = ht->tab[hash(name) & (ht->len - 1)]; e; e = e->next) {
  138         if (!zcmp(e->name, name)) {
  139             return e->val;
  140         }
  141     }
  142     return NULL;
  143 }