blob: 4b96f1aa78e9b4361a7d6ecc384bc3672cce1d37 (
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
|
#include "stdafx.h"
#include "CustomSet.h"
CustomSet::CustomSet()
{
m_NodePool = nullptr;
m_NodePoolSize = 0;
m_NodePoolIndex = 0;
m_HashSize = 1024;
m_HashTable = static_cast<SCustomSetNode **>(malloc(m_HashSize * sizeof(SCustomSetNode)));
clear();
}
CustomSet::~CustomSet()
{
for( int i = 0;i < m_NodePoolSize; i += 1 )
{
free(m_NodePool[i]);
}
free(m_NodePool);
free(m_HashTable);
}
void CustomSet::clear()
{
// reset the pool index
m_NodePoolIndex = 0;
// clear the hash table
memset(m_HashTable, 0, m_HashSize * sizeof(SCustomSetNode));
}
SCustomSetNode* CustomSet::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);
SCustomSetNode* Node = m_HashTable[Index];
while( Node && Node->Hash != Hash )
{
Node = Node->Next;
}
return Node;
}
int CustomSet::end()
{
return m_NodePoolIndex;
}
ChunkPos CustomSet::get(int index)
{
return m_NodePool[index]->key;
}
void CustomSet::insert(const ChunkPos &Key)
{
// see if this key already exists
SCustomSetNode* 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
{
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->key = Key;
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
SCustomSetNode* OldNode = m_HashTable[Index];
while( OldNode->Next )
{
OldNode = OldNode->Next;
}
// link the old last node to the new one
OldNode->Next = Node;
}
}
void CustomSet::resize()
{
int OldPoolSize = m_NodePoolSize;
m_NodePoolSize += 512;
SCustomSetNode **NodePool;
if( m_NodePool )
{
NodePool = static_cast<SCustomSetNode **>(realloc(m_NodePool, m_NodePoolSize * sizeof(SCustomSetNode)));
}
else
{
NodePool = static_cast<SCustomSetNode **>(malloc(m_NodePoolSize * sizeof(SCustomSetNode)));
}
for( int i = 0;i < m_NodePoolSize - OldPoolSize;i += 1 )
{
NodePool[i + OldPoolSize] = static_cast<SCustomSetNode *>(malloc(sizeof(SCustomSetNode)));
}
m_NodePool = NodePool;
}
|
