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