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

Last change on this file since 197 was 197, checked in by Maciej Komosinski, 7 years ago

GDK used by developers since 1999, distributed on the web since 2002

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