|
507
|
1 #include <stdio.h>
|
|
|
2 #include <string.h>
|
|
|
3 #include <stdlib.h>
|
|
|
4 #include "TileHash.h"
|
|
|
5
|
|
|
6 #if 0
|
|
|
7
|
|
|
8 not used now
|
|
|
9
|
|
|
10 static unsigned short PRIME[8] = {
|
|
|
11 0x002, 0x065, 0x0c7, 0x133, 0x191, 0x1f3, 0x259, 0x2bd,
|
|
|
12 };
|
|
|
13
|
|
|
14 int
|
|
|
15 TileHash::hash(memaddr data)
|
|
|
16 {
|
|
|
17 int value = 0;
|
|
|
18 int n = 0;
|
|
|
19 int key;
|
|
|
20
|
|
|
21 for (uint32 i = 0; i < sizeof(memaddr) * 2; i ++) {
|
|
|
22 key = data & 0xf;
|
|
|
23 value += key * PRIME[n++ & 7];
|
|
|
24 data >>= 4;
|
|
|
25 }
|
|
|
26
|
|
|
27 return value % hashSize;
|
|
|
28 }
|
|
|
29
|
|
|
30 TileHash::TileHash(void)
|
|
|
31 {
|
|
|
32 //hashSize = 263;
|
|
|
33 //tableSize = sizeof(TilePtr)*hashSize;
|
|
|
34
|
|
|
35 table = (TilePtr*)malloc(tableSize);
|
|
|
36 clear();
|
|
|
37 }
|
|
|
38
|
|
|
39 int
|
|
|
40 TileHash::put(memaddr key, TilePtr data)
|
|
|
41 {
|
|
|
42 int hashval = hash(key);
|
|
|
43
|
|
|
44 for (int i = 0; i < hashSize/2; i++) {
|
|
|
45 int index = (hashval + i*i)%hashSize;
|
|
|
46
|
|
|
47 if (table[index] == 0) { // 空の table に入れる
|
|
|
48 table[index] = data;
|
|
|
49 return index;
|
|
|
50 }
|
|
|
51 }
|
|
|
52
|
|
|
53 return -1;
|
|
|
54 }
|
|
|
55
|
|
|
56 TilePtr
|
|
|
57 TileHash::get(memaddr key)
|
|
|
58 {
|
|
|
59 int hashval = hash(key);
|
|
|
60
|
|
|
61 for (int i = 0; i < hashSize/2; i++) {
|
|
|
62 int index = (hashval + i*i)%hashSize;
|
|
|
63
|
|
|
64 if (table[index] != NULL &&
|
|
|
65 table[index]->address == key) {
|
|
|
66 return table[index];
|
|
|
67 }
|
|
|
68 }
|
|
|
69
|
|
|
70 return NULL;
|
|
|
71 }
|
|
|
72
|
|
|
73 void
|
|
|
74 TileHash::remove(memaddr key)
|
|
|
75 {
|
|
|
76 int hashval = hash(key);
|
|
|
77
|
|
|
78 for (int i = 0; i < hashSize/2; i++) {
|
|
|
79 int index = (hashval + i*i)%hashSize;
|
|
|
80
|
|
|
81 if (table[index] != NULL &&
|
|
|
82 table[index]->address == key) {
|
|
|
83 table[index] = NULL;
|
|
|
84 }
|
|
|
85 }
|
|
|
86 }
|
|
|
87
|
|
|
88 void
|
|
|
89 TileHash::clear(void)
|
|
|
90 {
|
|
|
91 bzero(table, tableSize);
|
|
|
92 }
|
|
|
93 #endif
|
|
|
94
|
