Subversion Repositories filter_foundry

Rev

Rev 237 | Rev 532 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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