Subversion Repositories Kolibri OS

Rev

Rev 7881 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
7420 pavelyakov 1
// Author: Pavel Iakovlev by. pavelyakov
2
 
7521 leency 3
#ifndef INCLUDE_ARRAY_H
4
#define INCLUDE_ARRAY_H
7420 pavelyakov 5
 
7741 pavelyakov 6
#include "../lib/crc32.h"
7
 
7420 pavelyakov 8
// Array memory: [dword key][byte flags][dword left][dword right][dword value] -> 17 bytes = 1 position
9
// If key don't exists then value == 0
10
:struct Array
11
{
12
	dword memory;
13
	dword offsetMemory;
7430 pavelyakov 14
	dword lenInitSize;
7420 pavelyakov 15
	dword recursiveIndex(dword i, address);
16
	byte set(dword key, data);
17
	dword get(dword key);
7430 pavelyakov 18
	void reallocMemory(dword newSize);
7420 pavelyakov 19
	//dword del(dword key);
20
	byte init(dword size);
21
};
22
 
7430 pavelyakov 23
:void Array::reallocMemory(dword newSize)
24
{
7741 pavelyakov 25
	newSize *= 17;
7430 pavelyakov 26
	memory = realloc(memory, newSize);
27
	lenInitSize = newSize;
28
}
29
 
7420 pavelyakov 30
:dword Array::recursiveIndex(dword key, address)
31
{
32
	dword flags = 0;
7430 pavelyakov 33
	IF (DSDWORD[address] == key) RETURN address;
7420 pavelyakov 34
	flags = DSBYTE[address + 4];
35
	//IF (flags & 100b) RETURN address; // if delete
36
	IF (flags & 010b) && (DSDWORD[address] < key) RETURN recursiveIndex(key, DSDWORD[address + 5]); // left tree
37
	IF (flags & 001b) && (DSDWORD[address] > key) RETURN recursiveIndex(key, DSDWORD[address + 9]); // right tree
38
	RETURN address;
39
}
7741 pavelyakov 40
 
7420 pavelyakov 41
:byte Array::init(dword size)
42
{
7741 pavelyakov 43
	dword pointer = 0;
7972 leency 44
	if (!size) size = 240;
7420 pavelyakov 45
	IF(!memory)
46
	{
7430 pavelyakov 47
		lenInitSize = size * 17;
48
		memory = malloc(lenInitSize);
7741 pavelyakov 49
		pointer = memory;
50
		DSDWORD[pointer] = 0; pointer += 4;
51
		DSBYTE[pointer] = 0; pointer += 1;
52
		DSDWORD[pointer] = 0;pointer += 4;
53
		DSDWORD[pointer] = 0;pointer += 4;
54
		DSDWORD[pointer] = 0;
7420 pavelyakov 55
		offsetMemory = 17;
56
		RETURN 0xFF;
57
	}
7430 pavelyakov 58
	IF(size > lenInitSize)
59
	{
7741 pavelyakov 60
		reallocMemory(size);
7430 pavelyakov 61
		RETURN 0xFF;
62
	}
63
	RETURN 0;
7420 pavelyakov 64
}
65
:byte Array::set(dword key, data)
66
{
67
	dword address = 0;
68
	dword newOffset = 0;
7430 pavelyakov 69
	IF(offsetMemory > lenInitSize) reallocMemory(offsetMemory << 1);
7420 pavelyakov 70
	address = recursiveIndex(key, memory);
71
	/*IF(DSBYTE[address + 4] & 100b)
72
	{
73
		IF(DSDWORD[address] < key)
74
		{
75
			DSBYTE[address + 4] |= 10b;
76
			DSDWORD[address + 5] = newOffset;
77
		}
78
		ELSE IF(DSDWORD[address] > key)
79
		{
80
			DSBYTE[address + 4] |= 01b;
81
			DSDWORD[address + 9] = newOffset;
82
		}
83
		ELSE
84
		{
85
			DSDWORD[address + 13] = data;
86
			RETURN 0xFF;
87
		}
88
	}*/
89
	newOffset = memory + offsetMemory;
90
	IF(DSDWORD[address] < key)
91
	{
7430 pavelyakov 92
		DSBYTE[address + 4] |= 010b; // set flag left address
7420 pavelyakov 93
		DSDWORD[address + 5] = newOffset;
94
	}
95
	ELSE IF(DSDWORD[address] > key)
96
	{
7430 pavelyakov 97
		DSBYTE[address + 4] |= 001b; // set flag right address
7420 pavelyakov 98
		DSDWORD[address + 9] = newOffset;
99
	}
100
	ELSE
101
	{
102
		DSDWORD[address + 13] = data;
103
		RETURN 0xFF;
104
	}
7741 pavelyakov 105
	DSDWORD[newOffset] = key; newOffset+=4;
106
	DSBYTE[newOffset] = 0; newOffset+=1;
107
	DSDWORD[newOffset] = 0; newOffset+=4;
108
	DSDWORD[newOffset] = 0; newOffset+=4;
109
	DSDWORD[newOffset] = data;
7420 pavelyakov 110
	offsetMemory += 17;
111
	RETURN 0xFF;
112
}
113
:dword Array::get(dword key)
114
{
115
	EBX = recursiveIndex(key, memory);
116
	IF(DSDWORD[EBX] != key) RETURN 0;
117
	IF(DSBYTE[EBX + 4] & 100b) RETURN 0;
118
	RETURN DSDWORD[EBX + 13];
119
}
120
/*:dword Array::del(dword key)
121
{
122
	dword address = 0;
123
	address = recursiveIndex(key, memory);
124
	IF(DSDWORD[address] != key) RETURN 0;
125
	DSBYTE[address + 4] |= 100b;
126
	RETURN 0xFF;
127
}*/
128
 
129
:struct Dictionary
130
{
131
	Array array;
132
	dword hash(dword text);
133
	byte set(dword key, value);
134
	dword get(dword key);
135
	byte init(dword size);
136
};
137
 
7741 pavelyakov 138
:dword Dictionary::hash(dword text)
7420 pavelyakov 139
{
7741 pavelyakov 140
	RETURN crc32(text, strlen(text));
141
/*
7430 pavelyakov 142
	dword checkSum1 = 1;
143
	dword checkSum2 = 0;
144
	dword beginAddress = 0;
7831 pavelyakov 145
 
7430 pavelyakov 146
	beginAddress = text;
7420 pavelyakov 147
	WHILE(DSBYTE[text])
148
	{
7430 pavelyakov 149
		checkSum1 += DSBYTE[text];
150
		checkSum2 += checkSum1;
7420 pavelyakov 151
		text++;
152
	}
7430 pavelyakov 153
	//IF(h1 > 0x03FFF) RETURN h1 << 8 ^ h2;
154
	//IF(h2 > 0x3FFFF) RETURN h1 << 8 ^ h2;
155
	EAX = text - beginAddress;
156
	EAX <<= 23;
157
	RETURN EAX | checkSum2;
7741 pavelyakov 158
*/
7420 pavelyakov 159
}
160
 
161
:byte Dictionary::set(dword key, value)
162
{
163
	RETURN array.set(hash(key),value);
164
}
165
 
166
:dword Dictionary::get(dword key)
167
{
168
	RETURN array.get(hash(key));
169
}
170
 
171
:byte Dictionary::init(dword size)
172
{
173
	RETURN array.init(size);
7521 leency 174
}
175
 
7881 pavelyakov 176
:dword indexArray(dword address, key)
7831 pavelyakov 177
{
7881 pavelyakov 178
	dword offset = key&0x1FF;
7831 pavelyakov 179
	dword offsetAddress = offset*4+address;
7881 pavelyakov 180
	IF (key==offset) RETURN 4*0x200+offsetAddress;
181
	IF (!DSDWORD[offsetAddress]) DSDWORD[offsetAddress] = malloc(0x1000);
182
	RETURN indexArray(DSDWORD[offsetAddress], key>>9);
7831 pavelyakov 183
}
184
 
7741 pavelyakov 185
#endif