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

Last change on this file since 1040 was 793, checked in by Maciej Komosinski, 3 years ago

Code formatting

  • Property svn:eol-style set to native
File size: 3.4 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2015  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#include "hashtable.h"
6
7int HashTable::hash(const SString &s)
8{
9        return s.hash() & 0x7fffffff;
10}
11
12void HashTable::init(int initsize, float lo)
13{
14        size = initsize;
15        load = lo;
16        threshold = (int)(load*(float)size);
17        tab = (HashEntry**)calloc(size, sizeof(HashEntry*));
18        count = 0;
19        sync = 0;
20}
21
22void HashTable::rehash(int newsize)
23{
24        if (newsize == size) return;
25        HashEntry **newtab = (HashEntry**)calloc(newsize, sizeof(HashEntry*));
26        HashEntry **te = tab, *e, *ne;
27        int i;
28        for (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                }
36        free(tab);
37        tab = newtab;
38        size = newsize;
39        threshold = int(load*(float)size);
40        sync++;
41}
42
43void HashTable::clear()
44{
45        HashEntry *e, **te, *next;
46        int n;
47        for (n = size, te = tab; n > 0; n--, te++)
48                for (e = *te; e; e = next)
49                {
50                next = e->next;
51                delete e;
52                }
53        if (tab) free(tab);
54        tab = 0; size = 0;
55        sync++;
56}
57
58HashTable::~HashTable()
59{
60        clear();
61}
62
63void* HashTable::put(const SString& key, void *value)
64{
65        int h = hash(key);
66        int i = h%size;
67        for (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        }
76        if (count >= threshold) { rehash(2 * size + 1); i = h%size; }
77        HashEntry *e = new HashEntry(h, key, value);
78        e->next = tab[i];
79        tab[i] = e;
80        count++;
81        sync++;
82        return 0;
83}
84
85void* HashTable::remove(const SString& key)
86{
87        int i = hash(key) % size;
88        HashEntry **ptr = tab + i, *e;
89        for (; 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        }
101        return 0;
102}
103
104void* HashTable::remove(HashEntryIterator& it)
105{
106        if (!it.entry) return 0;
107        HashEntry **ptr = tab + it.hashindex, *e;
108        for (; 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{
127        int i = hash(key) % size;
128        for (HashEntry *e = tab[i]; e; e = e->next)
129                if (e->key == key) { if (reallygot) *reallygot = 1; return e->value; }
130        return 0;
131}
132
133/////////
134
135void HashEntryIterator::findNext()
136{
137        while (hashindex < (ht->size - 1))
138        {
139                hashindex++;
140                if (entry = ht->tab[hashindex]) return;
141        }
142}
143
144
145void HashEntryIterator::operator++()
146{
147        if (entry) entry = entry->next;
148        if (!entry) findNext();
149}
150
151//////////////////////////
152
153void HashTable::debugprint()
154{
155        printf("HashTable: %d/%d (max %d)\n", count, size, threshold);
156        HashEntry *e, **te;
157        int n;
158        for (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, e->key.c_str(), 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{
176        HashEntry *e, **te;
177        int used = 0, ma = 0, mi = count;
178        int c, n;
179        for (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        }
187        stats[0] = (float)used;
188        stats[1] = (float)((mi == count) ? 0 : mi);
189        stats[2] = (float)count / (float)used;
190        stats[3] = (float)ma;
191}
Note: See TracBrowser for help on using the repository browser.