1 /******************************************************************************
2 *
3 * Copyright (C) 2004-2008, The Gentee Group. All rights reserved.
4 * This file is part of the Gentee open source project - http://www.gentee.com.
5 *
6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT").
7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS
8 * ACCEPTANCE OF THE AGREEMENT.
9 *
10 * Author: Alexey Krivonogov ( gentee )
11 *
12 ******************************************************************************/
13
14 /*-----------------------------------------------------------------------------
15 * Id: hash L "Hash"
16 *
17 * Summary: Hash (Associative array). Variables of the hash type allow you to
18 work with associative arrays or hash tables. Each item in such an
19 array corresponds to a unique key string. Items are addresses by
20 specifying the corresponding key strings.
21 *
22 * List: *Operators,hash_opof,hash_oplen,hash_opind,hash_opfor,
23 *Methods,hash_clear,hash_create,hash_del,hash_find,
24 hash_ignorecase,hash_sethashsize,
25 *Type,thash
26 *
27 -----------------------------------------------------------------------------*/
28
29 type hashkey
30 {
31 str key // ключ
32 uint next // Указатель на следующий ключ
33 }
34 //После hashkey идут данные
35
36 type hkeys <index = str>
37 {
38 uint owner
39 }
40
41 type hashfordata <inherit=fordata>{
42 uint curind // текущий индекс для foreach
43 uint curitem // текущий элемент для foreach
44 uint forkeys // 1 если foreach для ключей
45 }
46
47 /*-----------------------------------------------------------------------------
48 * Id: thash T hash
49 *
50 * Summary: The main structure of the hash.
51 *
52 -----------------------------------------------------------------------------*/
53
54 type hash {
55 arr hashes // Array of hash values. Pointers to hashkey.
56 uint itype // The type of the items.
57 uint isize // The type of the item.
58 uint count // The count of items.
59 uint igncase // Equals 1 if the hash ignores case sensetive.
60 hkeys keys // The structure for looking over keys
61 }
62
63 /*-----------------------------------------------------------------------------
64 * Id: hash_opof F4
65 *
66 * Summary: Specifying the type of items. You can specify #b(of) type when you
67 describe #b(hash) variable. In default, the type of the items
68 is #b(uint).
69 *
70 * Title: hash of type
71 *
72 -----------------------------------------------------------------------------*/
73
74 method hash.oftype( uint itype )
75 {
76 this.itype = itype
77 this.isize = sizeof( hashkey ) + sizeof( itype )
78 }
79
80 /*-----------------------------------------------------------------------------
81 * Id: hash_sethashsize F2
82 *
83 * Summary: Set the size of a value table. Set the size of the value table for
84 searching for keys. The method must be called before any items are
85 added. The parameter contains the power of two for calculating the
86 size of the table since the number of items must be the power of
87 two. By default, the size of a table is 4096 items.
88 *
89 * Params: power - The power of two for calculating the size of the table.
90 *
91 * Return: #lng/retf#
92 *
93 -----------------------------------------------------------------------------*/
94
95 method uint hash.sethashsize( uint power )
96 {
97 if this.count : return 0
98 if power < 8 : power = 8
99 if power > 20 : power = 20
100 this.hashes.clear()
101 this.hashes.expand( 1 << power )
102 return 1
103 }
104
105 method hash hash.init()
106 {
107 this.sethashsize( 12 ) // 4096
108 this.oftype( uint )
109 this.keys.owner = &this
110 return this
111 }
112
113 /*-----------------------------------------------------------------------------
114 * Id: hash_oplen F4
115 *
116 * Summary: Get the count of items.
117 *
118 * Return: Count of hash items.
119 *
120 -----------------------------------------------------------------------------*/
121
122 operator uint *( hash left )
123 {
124 return left.count
125 }
126
127 /*-----------------------------------------------------------------------------
128 * Id: hash_ignorecase F3
129 *
130 * Summary: Ignoring the letter case of keys. Work with the keys of this hash
131 table without taking into account the case of letters. The method
132 must be called before any items are added.
133 *
134 * Return: #lng/retf#
135 *
136 -----------------------------------------------------------------------------*/
137
138 method uint hash.ignorecase
139 {
140 if this.count : return 0
141 this.igncase = 1
142 return 1
143 }
144
145 method hash.delete()
146 {
147 uint i
148 uint base
149
150 fornum i, *this.hashes
151 {
152 while this.hashes[ i ]
153 {
154 base = this.hashes[ i ]
155 this.hashes[ i ] = base->hashkey.next
156 if type_hasdelete( this.itype )
157 {
158 type_delete( base + sizeof( hashkey ), this.itype )
159 }
160 type_delete( base, hashkey )
161 mfree( base )
162 }
163 }
164 }
165
166 /*-----------------------------------------------------------------------------
167 * Id: hash_clear F3
168 *
169 * Summary: Clear a hash. The method removes all items from the hash.
170 *
171 -----------------------------------------------------------------------------*/
172
173 method hash.clear()
174 {
175 this.delete()
176 this.count = 0
177 }
178
179 method uint hash.keyfind( str key, uint index )
180 {
181 uint i
182
183 if this.igncase
184 {
185 str lkey = key
186
187 lkey.lower()
188 i = lkey.crc() & ( *this.hashes - 1 )
189 }
190 else : i = key.crc() & ( *this.hashes - 1 )
191 uint ptr = this.hashes[ i ]
192
193 if index : index->uint = i
194 if !ptr : return 0
195 while ptr
196 {
197 if this.igncase
198 {
199 if ptr->hashkey.key %== key : break
200 }
201 elif ptr->hashkey.key == key : break
202 ptr = ptr->hashkey.next
203 }
204 return ?( ptr, ptr + sizeof( hashkey ), 0 )
205 }
206
207 /*-----------------------------------------------------------------------------
208 * Id: hash_find F2
209 *
210 * Summary: Find an item with this key.
211 *
212 * Params: key - Key value.
213 *
214 * Return: Either the pointer to the found item is returned or 0 is returned
215 if there is no item with this key.
216 *
217 -----------------------------------------------------------------------------*/
218
219 method uint hash.find( str key )
220 {
221 return this.keyfind( key, 0 )
222 }
223
224 /*-----------------------------------------------------------------------------
225 * Id: hash_create F2
226 *
227 * Summary: Creating an item with this key. If an item with this key already
228 exists, it will be initiated again. Items are created automatically
229 when they are addressed as array items for the first time -
230 hashname["key string"].
231 *
232 * Params: key - Key value.
233 *
234 * Return: The pointer to the created item is returned.
235 *
236 -----------------------------------------------------------------------------*/
237
238 method uint hash.create( str key )
239 {
240 uint index
241 uint item = this.keyfind( key, &index )
242 uint data
243 if !item
244 {
245 data = malloc( this.isize )
246 type_init( data, hashkey )
247 item = data + sizeof( hashkey )
248 // вставка элемента
249 data->hashkey.key = key
250 data->hashkey.next = this.hashes[ index ]
251 this.hashes[ index ] = data
252 this.count++
253 }
254 else
255 {
256 if type_hasdelete( this.itype ) : type_delete( item, this.itype )
257 }
258 type_init( item, this.itype )
259 return item
260 }
261
262 /*-----------------------------------------------------------------------------
263 * Id: hash_opind F4
264 *
265 * Summary: Getting an item by a key string. In case there is no item,
266 it will be created automatically.
267 *
268 * Title: hash[ name ]
269 *
270 * Return: The #b('["key"]') item of the hash.
271 *
272 -----------------------------------------------------------------------------*/
273
274 method uint hash.index( str key )
275 {
276 uint item = this.find( key )
277
278 if !item : return this.create( key )
279 return item
280 }
281
282 /*-----------------------------------------------------------------------------
283 * Id: hash_del F2
284 *
285 * Summary: Delete an item with this key.
286 *
287 * Params: key - Key value.
288 *
289 * Return: #lng/retf#
290 *
291 -----------------------------------------------------------------------------*/
292
293 method uint hash.del( str key )
294 {
295 uint index
296 uint ptr
297 uint item = this.keyfind( key, &index )
298 uint base
299
300 if !item : return 0
301 // Удаляем из списка
302 ptr = this.hashes[ index ]
303 base = item - sizeof( hashkey )
304 if ptr == base
305 {
306 this.hashes[ index ] = base->hashkey.next
307 }
308 else
309 {
310 while ptr->hashkey.next != base
311 {
312 ptr = ptr->hashkey.next
313 if !ptr : return 0
314 }
315 ptr->hashkey.next = base->hashkey.next
316 }
317 // Удаляем объект
318 if type_hasdelete( this.itype )
319 {
320 type_delete( item, this.itype )
321 }
322 type_delete( base, hashkey )
323 mfree( base )
324 this.count--
325 return 1
326 }
327
328 /*-----------------------------------------------------------------------------
329 * Id: hash_opfor F5
330 *
331 * Summary: Foreach operator. You can use #b(foreach) operator to look over all
332 items of the hash. #b(Variable) is a pointer to the hash item.
333 *
334 * Title: foreach var,hash
335 *
336 * Define: foreach variable,hash {...}
337 *
338 -----------------------------------------------------------------------------*/
339
340 /*-----------------------------------------------------------------------------
341 ** Id: hash_opfor_1 FD
342 *
343 * Summary: You can use #b(foreach) operator to look over all
344 keys of the hash.
345 *
346 * Title: foreach var,hash.keys
347 *
348 * Define: foreach variable,hash.keys {...}
349 *
350 -----------------------------------------------------------------------------*/
351
352 method uint hash.eof( hashfordata fd )
353 {
354 return fd.curind >= *this.hashes
355 }
356
357 method uint hash.next( hashfordata fd )
358 {
359 if fd.curitem
360 {
361 if fd.curitem = fd.curitem->hashkey.next {
362
363 return ?( fd.forkeys, &fd.curitem->hashkey.key,
364 fd.curitem + sizeof( hashkey ))
365 }
366 fd.curind++
367 }
368 while fd.curind < *this.hashes && !this.hashes[ fd.curind ]
369 {
370 fd.curind++
371 }
372 if fd.curind < *this.hashes
373 {
374 fd.curitem = this.hashes[ fd.curind ]
375 return ?( fd.forkeys, &fd.curitem->hashkey.key,
376 fd.curitem + sizeof( hashkey ))
377 }
378 return 0
379 }
380
381 method uint hash.forfirst( hashfordata fd )
382 {
383 fd.curind = 0
384 fd.curitem = 0
385 return this.next( fd )
386 }
387
388 method uint hash.first( hashfordata fd )
389 {
390 fd.forkeys = 0
391 return this.forfirst( fd )
392 }
393
394 method uint hkeys.eof( hashfordata fd )
395 {
396 return this.owner->hash.eof( fd )
397 }
398
399 method uint hkeys.next( hashfordata fd )
400 {
401 return this.owner->hash.next( fd )
402 }
403
404 method uint hkeys.first( hashfordata fd )
405 {
406 fd.forkeys = 1
407 return this.owner->hash.forfirst( fd )
408 }
409