source: cpp/frams/util/hashtable.cpp @ 275

Last change on this file since 275 was 226, checked in by Maciej Komosinski, 11 years ago
  • SString::hash() and HashTable? use FNV-1a instead of FNV-1
  • fixed the initial hash value
  • Property svn:eol-style set to native
File size: 3.1 KB
Line 
1// This file is a part of the Framsticks GDK.
2// Copyright (C) 1999-2014  Maciej Komosinski and Szymon Ulatowski.  See LICENSE.txt for details.
3// Refer to http://www.framsticks.com/ for further information.
4
5#include "hashtable.h"
6
7int HashTable::hash(const SString &s)
8{
9return s.hash()&0x7fffffff;
10}
11
12void HashTable::init(int initsize,float lo)
13{
14size=initsize;
15load=lo;
16threshold=(int)(load*(float)size);
17tab=(HashEntry**)calloc(size,sizeof(HashEntry*));
18count=0;
19sync=0;
20}
21
22void HashTable::rehash(int newsize)
23{
24if (newsize==size) return;
25HashEntry **newtab=(HashEntry**)calloc(newsize,sizeof(HashEntry*));
26HashEntry **te=tab,*e,*ne;
27int i;
28for (int s=size;s>0;s--,te++)
29    for (e=*te;e;)
30        {
31            ne=e; e=e->next;
32            i=ne->hash%newsize;
33            ne->next=newtab[i];
34            newtab[i]=ne;
35        }
36free(tab);
37tab=newtab;
38size=newsize;
39threshold=int(load*(float)size);
40sync++;
41}
42
43void HashTable::clear()
44{
45HashEntry *e,**te,*next;
46int n;
47for (n=size,te=tab;n>0;n--,te++)
48        for (e=*te;e;e=next)
49                {
50                next=e->next;
51                delete e;
52                }
53if (tab) free(tab);
54tab=0; size=0;
55sync++;
56}
57
58HashTable::~HashTable()
59{
60clear();
61}
62
63void* HashTable::put(const SString& key,void *value)
64{
65int h=hash(key);
66int i=h%size;
67for (HashEntry *e=tab[i];e;e=e->next)
68    {
69    if (e->key==key)
70        {
71        void *v=e->value;
72        e->value=value;
73        return v;
74        }
75    }
76if (count>=threshold) { rehash(2*size+1); i=h%size; }
77HashEntry *e=new HashEntry(h,key,value);
78e->next=tab[i];
79tab[i]=e;
80count++;
81sync++;
82return 0;
83}
84
85void* HashTable::remove(const SString& key)
86{
87int i=hash(key)%size;
88HashEntry **ptr=tab+i,*e;
89for (;e=*ptr;ptr=&e->next)
90    {
91    if (e->key==key)
92        {
93        *ptr=e->next;
94        void *v=e->value;
95        delete e;
96        count--;
97        sync++;
98        return v;
99        }
100    }
101return 0;
102}
103
104void* HashTable::remove(HashEntryIterator& it)
105{
106if (!it.entry) return 0;
107HashEntry **ptr=tab+it.hashindex,*e;
108for (;e=*ptr;ptr=&e->next)
109    {
110    if (e == it.entry)
111        {
112        it++;
113        *ptr=e->next;
114        void *v=e->value;
115        delete e;
116        count--;
117        sync++;
118        it.sync++;
119        return v;
120        }
121    }
122   return NULL;
123}
124
125void* HashTable::get(const SString& key,int *reallygot)
126{
127int i=hash(key)%size;
128for (HashEntry *e=tab[i];e;e=e->next)
129        if (e->key==key) {if (reallygot) *reallygot=1; return e->value;}
130return 0;
131}
132
133/////////
134
135void HashEntryIterator::findNext()
136{
137while (hashindex < (ht->size-1))
138        {
139        hashindex++;
140        if (entry=ht->tab[hashindex]) return;
141        }
142}
143
144
145void HashEntryIterator::operator++()
146{
147if (entry) entry=entry->next;
148if (!entry) findNext();
149}
150
151//////////////////////////
152
153void HashTable::debugprint()
154{
155printf("HashTable: %d/%d (max %d)\n",count,size,threshold);
156HashEntry *e,**te;
157int n;
158for (n=0,te=tab;n<size;n++,te++)
159        if (e=*te)
160        {
161        printf(" %d:",n);
162        for (;e;e=e->next)
163                printf(" (%x)%s=%p",e->hash,(const char*)e->key,e->value);
164        printf("\n");
165        }
166}
167
168/**
169stats[0]=buckets used
170stats[1]=min keys in bucket
171stats[2]=avg keys in bucket
172stats[3]=max keys in bucket
173 */
174void HashTable::getstats(float *stats)
175{
176HashEntry *e,**te;
177int used=0, ma=0, mi=count;
178int c,n;
179for (n=size,te=tab;n>0;n--,te++)
180        {
181        c=0;
182        for (e=*te;e;e=e->next) c++;
183        if (c>ma) ma=c;
184        if ((c<mi)&&(c>0)) mi=c;
185        if (c>0) used++;
186        }
187stats[0]=(float)used;
188stats[1]=(float)((mi==count)?0:mi);
189stats[2]=(float)count/(float)used;
190stats[3]=(float)ma;
191}
Note: See TracBrowser for help on using the repository browser.