blob: 7265eb04164dfbef9d6cdf58645c90365a2ba5be (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#include "stdafx.h"
#include "CustomMap.h"
CustomMap::CustomMap()
{
m_NodePool = nullptr;
m_NodePoolSize = 0;
m_NodePoolIndex = 0;
m_HashSize = 1024;
m_HashTable = static_cast<SCustomMapNode **>(malloc(m_HashSize * sizeof(SCustomMapNode)));
clear();
}
CustomMap::~CustomMap()
{
for( int i = 0;i < m_NodePoolSize; i += 1 )
{
free(m_NodePool[i]);
}
free(m_NodePool);
free(m_HashTable);
}
void CustomMap::clear()
{
// reset the pool index
m_NodePoolIndex = 0;
// clear the hash table
memset(m_HashTable, 0, m_HashSize * sizeof(SCustomMapNode));
}
SCustomMapNode* CustomMap::find(const ChunkPos &Key)
{
unsigned int Hash = (Key.x & 0x00000001f) | (Key.z << 5); // hopefully this will produce a good hash for a 1024 entry table
unsigned int Index = Hash & (m_HashSize-1);
SCustomMapNode* Node = m_HashTable[Index];
while( Node && Node->Hash != Hash )
{
Node = Node->Next;
}
return Node;
}
int CustomMap::end()
{
return m_NodePoolIndex;
}
SCustomMapNode* CustomMap::get(int index)
{
return m_NodePool[index];
}
void CustomMap::insert(const ChunkPos &Key, bool Value)
{
// see if this key already exists
SCustomMapNode* Node = find(Key);
if( !Node )
{
// do we have any space in the pool
if( m_NodePoolIndex >= m_NodePoolSize )
{
resize();
}
// grab the next node from the pool
Node = m_NodePool[m_NodePoolIndex];
m_NodePoolIndex++;
}
else
{
Node->second = Value;
return;
}
// create the new node;
unsigned int Hash = (Key.x & 0x00000001f) | (Key.z << 5); // hopefully this will produce a good hash for a 1024 entry table
unsigned int Index = Hash & (m_HashSize-1);
Node->Hash = Hash;
Node->first = Key;
Node->second = Value;
Node->Next = nullptr;
// are any nodes in this hash index
if( !m_HashTable[Index] )
{
m_HashTable[Index] = Node;
}
else
{
// loop to the last node in the hash list
SCustomMapNode* OldNode = m_HashTable[Index];
while( OldNode->Next )
{
OldNode = OldNode->Next;
}
// link the old last node to the new one
OldNode->Next = Node;
}
}
void CustomMap::resize()
{
int OldPoolSize = m_NodePoolSize;
m_NodePoolSize += 512;
SCustomMapNode **NodePool;
if( m_NodePool )
{
NodePool = static_cast<SCustomMapNode **>(realloc(m_NodePool, m_NodePoolSize * sizeof(SCustomMapNode)));
}
else
{
NodePool = static_cast<SCustomMapNode **>(malloc(m_NodePoolSize * sizeof(SCustomMapNode)));
}
for( int i = 0;i < m_NodePoolSize - OldPoolSize;i += 1 )
{
NodePool[i + OldPoolSize] = static_cast<SCustomMapNode *>(malloc(sizeof(SCustomMapNode)));
}
m_NodePool = NodePool;
}
|
