Subversion Repositories filter_foundry

Rev

Rev 532 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /*
  2.     This file is part of "Filter Foundry", a filter plugin for Adobe Photoshop
  3.     Copyright (C) 2003-2009 Toby Thain, toby@telegraphics.net
  4.     Copyright (C) 2018-2021 Daniel Marschall, ViaThinkSoft
  5.  
  6.     This program is free software; you can redistribute it and/or modify
  7.     it under the terms of the GNU General Public License as published by
  8.     the Free Software Foundation; either version 2 of the License, or
  9.     (at your option) any later version.
  10.  
  11.     This program is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program; if not, write to the Free Software
  18.     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <string.h>
  23.  
  24. #include "symtab.h"
  25.  
  26. unsigned long djb2(const char *str);
  27.  
  28. /* following constant (need not) be prime. for a list of prime numbers,
  29.    see https://primes.utm.edu/lists/small/1000.txt */
  30. #define TABLE_SIZE 128 // if you're anticipating many symbols, increase this value!
  31. #define HASH(s) (djb2(s) % TABLE_SIZE)
  32.  
  33. struct sym_rec *hash_table[TABLE_SIZE];
  34. extern struct sym_rec predefs[];
  35.  
  36. // hash function recommended by Ozan Yigit
  37. // http://www.cs.yorku.ca/~oz/hash.html
  38. // "this algorithm (k=33) was first reported by dan bernstein"
  39. unsigned long djb2(const char *str){
  40.         unsigned long hash = 5381;
  41.         int c;
  42.  
  43.         while( (c = *str++) )
  44.                 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  45.  
  46.         return hash;
  47. }
  48.  
  49. void init_symtab(struct sym_rec *pre){
  50.         struct sym_rec *p;
  51.         int i;
  52.  
  53.         for(i=TABLE_SIZE;i--;)
  54.                 hash_table[i] = 0;
  55.         for(p=pre;p->name;p++){
  56.                 if(lookup(p->name))
  57.                         printf("!!!! duplicate predefined symbol: %s\n",p->name);
  58.                 insert(p);
  59.         }
  60. }
  61.  
  62. void dump_symbols(void){
  63.         struct sym_rec *p;
  64.         int i,occ,maxchain,chain;
  65.  
  66.         puts("\nsymbol table:");
  67.         for(i=occ=maxchain=0;i<TABLE_SIZE;i++)
  68.                 if(hash_table[i]){
  69.                         ++occ;
  70.                         for(p=hash_table[i],chain=0;p;p=p->next){
  71.                                 puts(p->name);
  72.                                 ++chain;
  73.                         }
  74.                         if(chain>maxchain)
  75.                                 maxchain = chain;
  76.                 }
  77.         printf("# hash stats: occupancy=%d/%d (%.1f%%) longest chain=%d\n",
  78.                    occ,TABLE_SIZE,(100.*occ)/TABLE_SIZE,maxchain);
  79. }
  80.  
  81.  
  82. struct sym_rec *lookup(const char *s){
  83.         struct sym_rec *p;
  84.         int idx = HASH(s);
  85. //      printf("# lookup \"%s\" hash=%5d\n",s,idx);
  86.         for(p=hash_table[idx];p;p=p->next)
  87.                 if(!strcmp(s,p->name))
  88.                         return p;
  89.         return 0; /* not found */
  90. }
  91. void insert(struct sym_rec *p){
  92.         int idx = HASH(p->name);
  93.         p->next = hash_table[idx];
  94.         hash_table[idx] = p;
  95.         /* DPRINTF("# insert symbol [%5d] \"%s\"\n",idx,p->name);*/
  96. }
  97.