Debian Codegraph @

cuneiform_src/Kern/lns32/src/bambuk.h

raw
1 /*
2 Copyright (c) 1993-2008, Cognitive Technologies
3 All rights reserved.
4
5 Разрешается повторное распространение и использование как в виде исходного кода,
6 так и в двоичной форме, с изменениями или без, при соблюдении следующих условий:
7
8 * При повторном распространении исходного кода должны оставаться указанное
9 выше уведомление об авторском праве, этот список условий и последующий
10 отказ от гарантий.
11 * При повторном распространении двоичного кода в документации и/или в
12 других материалах, поставляемых при распространении, должны сохраняться
13 указанная выше информация об авторском праве, этот список условий и
14 последующий отказ от гарантий.
15 * Ни название Cognitive Technologies, ни имена ее сотрудников не могут
16 быть использованы в качестве средства поддержки и/или продвижения
17 продуктов, основанных на этом ПО, без предварительного письменного
18 разрешения.
19
20 ЭТА ПРОГРАММА ПРЕДОСТАВЛЕНА ВЛАДЕЛЬЦАМИ АВТОРСКИХ ПРАВ И/ИЛИ ДРУГИМИ ЛИЦАМИ "КАК
21 ОНА ЕСТЬ" БЕЗ КАКОГО-ЛИБО ВИДА ГАРАНТИЙ, ВЫРАЖЕННЫХ ЯВНО ИЛИ ПОДРАЗУМЕВАЕМЫХ,
22 ВКЛЮЧАЯ ГАРАНТИИ КОММЕРЧЕСКОЙ ЦЕННОСТИ И ПРИГОДНОСТИ ДЛЯ КОНКРЕТНОЙ ЦЕЛИ, НО НЕ
23 ОГРАНИЧИВАЯСЬ ИМИ. НИ ВЛАДЕЛЕЦ АВТОРСКИХ ПРАВ И НИ ОДНО ДРУГОЕ ЛИЦО, КОТОРОЕ
24 МОЖЕТ ИЗМЕНЯТЬ И/ИЛИ ПОВТОРНО РАСПРОСТРАНЯТЬ ПРОГРАММУ, НИ В КОЕМ СЛУЧАЕ НЕ
25 НЕСЁТ ОТВЕТСТВЕННОСТИ, ВКЛЮЧАЯ ЛЮБЫЕ ОБЩИЕ, СЛУЧАЙНЫЕ, СПЕЦИАЛЬНЫЕ ИЛИ
26 ПОСЛЕДОВАВШИЕ УБЫТКИ, СВЯЗАННЫЕ С ИСПОЛЬЗОВАНИЕМ ИЛИ ПОНЕСЕННЫЕ ВСЛЕДСТВИЕ
27 НЕВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ ПРОГРАММЫ (ВКЛЮЧАЯ ПОТЕРИ ДАННЫХ, ИЛИ ДАННЫЕ,
28 СТАВШИЕ НЕГОДНЫМИ, ИЛИ УБЫТКИ И/ИЛИ ПОТЕРИ ДОХОДОВ, ПОНЕСЕННЫЕ ИЗ-ЗА ДЕЙСТВИЙ
29 ТРЕТЬИХ ЛИЦ И/ИЛИ ОТКАЗА ПРОГРАММЫ РАБОТАТЬ СОВМЕСТНО С ДРУГИМИ ПРОГРАММАМИ,
30 НО НЕ ОГРАНИЧИВАЯСЬ ЭТИМИ СЛУЧАЯМИ), НО НЕ ОГРАНИЧИВАЯСЬ ИМИ, ДАЖЕ ЕСЛИ ТАКОЙ
31 ВЛАДЕЛЕЦ ИЛИ ДРУГОЕ ЛИЦО БЫЛИ ИЗВЕЩЕНЫ О ВОЗМОЖНОСТИ ТАКИХ УБЫТКОВ И ПОТЕРЬ.
32
33 Redistribution and use in source and binary forms, with or without modification,
34 are permitted provided that the following conditions are met:
35
36 * Redistributions of source code must retain the above copyright notice,
37 this list of conditions and the following disclaimer.
38 * Redistributions in binary form must reproduce the above copyright notice,
39 this list of conditions and the following disclaimer in the documentation
40 and/or other materials provided with the distribution.
41 * Neither the name of the Cognitive Technologies nor the names of its
42 contributors may be used to endorse or promote products derived from this
43 software without specific prior written permission.
44
45 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
46 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
47 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
48 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
49 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
51 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
52 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
53 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
54 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
55 */
56
57 #ifndef __BAMBUK_H
58 # define __BAMBUK_H
59
60 /* "Bambuk" is a grass that grows...
61 * 1) ...from number of fixed previously roots
62 * 2) ...always upward
63 * 3) ...as fast as possible;
64 */
65
66 #ifndef __LNSLANG_H
67 # include "lnslang.h"
68 #endif
69
70
71 #ifndef __FARARRAY_H
72 # include "fararray.h"
73 #endif
74
75 typedef int32_t BHandle ;
76 typedef int32_t BEntry ;
77
78 #define NULLBHandle (BHandle) 0xFFFF
79 #define NULLBEntry (BEntry) 0xFFFF
80
81 struct EntryInfo
82 {
83 BHandle first;
84 BHandle last;
85 BHandle count;
86 };
87
88 template <class T> class TBambuk //: public TFarHeap
89 {
90 public :
91
92 TBambuk( void )
93 {};
94
95 TBambuk( BHandle max_members_count, BEntry max_entry_count )
96 {
97 createBambuk( max_members_count, max_entry_count);
98 if (!isOk())
99 destroyBambuk();
100 };
101
102
103 /* virtual */ Bool isOk( void )
104 { return (ok); };
105
106 Bool createBambuk( BHandle max_members_count, BEntry max_entry_count )
107 { //assert( max_members_count > 0 );
108 //assert( max_entry_count > 0 );
109
110 nextHandle = 0;
111 ok = ( members.create( max_members_count) &&
112 links .create( max_members_count ) &&
113 entries.create( max_entry_count )
114 );
115 if (ok){
116 cleanLinks();
117 cleanEntries();
118 };
119 return (ok);
120 };
121
122 void appendMember( BEntry entry_point, BHandle member_handle )
123 {
124 assert(entry_point < entries.lastHandle());
125 assert( member_handle != NULLBHandle );
126 assert( links[ member_handle ] == NULLBHandle ); // member is single
127 if (noEntry( entry_point )) {
128 entries[ entry_point ].first =
129 entries[ entry_point ].last = member_handle;
130 entries[ entry_point ].count = 1;
131 }
132 else {
133 assert( links[ entries[ entry_point ].last ] == NULLBHandle );
134 links[ entries[ entry_point ].last ] = member_handle;
135 entries[ entry_point ].last = member_handle;
136 entries[ entry_point ].count++;
137 };
138 };
139
140
141 BHandle addMember( BEntry entry_point )
142 {
143 assert(entry_point <= entries.lastHandle());
144 if (nextHandle >= members.lastHandle())
145 return NULLBHandle;
146
147
148 links[ nextHandle ] = NULLBHandle;
149 if (noEntry( entry_point )) {
150 entries[ entry_point ].first =
151 entries[ entry_point ].last = nextHandle;
152 entries[ entry_point ].count = 1;
153 }
154 else {
155 assert( links[ entries[ entry_point ].last ] == NULLBHandle );
156 links[ entries[ entry_point ].last ] = nextHandle;
157 entries[ entry_point ].last = nextHandle;
158 entries[ entry_point ].count++;
159 };
160 return (nextHandle++);
161 };
162
163 BHandle firstEntryMember( BEntry entry_point )
164 { return entries[ entry_point ].first; }
165
166 BHandle lastEntryMember( BEntry entry_point )
167 { return entries[ entry_point ].last; }
168
169 BHandle memberEntryCount( BEntry entry_point )
170 { return entries[ entry_point ].count; }
171
172 BHandle memberTotalCount( void )
173 { return (nextHandle); }
174
175 BHandle memberVolume( void )
176 { return (members.volume()); }
177
178 BHandle memberRestCount( void )
179 { return (members.volume() - nextHandle); }
180
181 BHandle nextMember( BHandle cur_member )
182 { return links[ cur_member ]; }
183
184 BEntry lastEntry( void )
185 { return (entries.lastHandle()); }
186
187 void appendMemberList( BEntry senior, BEntry junior )
188 { assert( !noEntry(junior) );
189 assert( !noEntry(senior) );
190
191 assert( links[ entries[ senior ].last ] == NULLBHandle );
192 assert( links[ entries[ junior ].last ] == NULLBHandle );
193
194 links[ entries[ senior ].last ] = entries[ junior ].first;
195 entries[ senior ].last = entries[ junior ].last;
196 entries[ senior ].count += entries[ junior ].count;
197
198 entries[ junior ].first = NULLBHandle;
199 entries[ junior ].last = NULLBHandle;
200 entries[ junior ].count = 0;
201 };
202
203 T & operator [] ( BHandle cur_member)
204 { return members[cur_member];};
205
206 Bool shrinkBambuk( BHandle new_members_count,
207 BEntry new_entries_count = 0 )
208 {
209 assert( isOk() );
210 // assert( new_members_count > 0 );
211 BHandle old_members_count = members.volume();
212 assert( new_members_count < old_members_count );
213 BEntry old_entries_count = entries.volume();
214 assert( new_entries_count < old_entries_count );
215
216 if (!members.shrink(new_members_count))
217 return WRONG();
218 if (!links.shrink(new_members_count))
219 return WRONG();
220
221 if ( (new_entries_count > 0)
222 &&
223 (!entries.shrink(new_entries_count))
224 ) return WRONG();
225
226 /*
227 if (old_members_count < new_members_count)
228 cleanLinks( old_members_count );
229 if (old_entries_count < new_entries_count)
230 cleanEntries( old_members_count );
231 */
232 return TRUE;
233 };
234
235 void destroyBambuk( void )
236 {
237 members.flash();
238 links .flash();
239 entries.flash();
240 nextHandle = 0;
241 ok = FALSE;
242 };
243 void cleanMembers( T * zero_member, int32_t from );
244 void cleanLinks( int32_t from = 0 );
245 void cleanEntries( int32_t from = 0 );
246
247
248
249 ~TBambuk( void )
250 { destroyBambuk(); };
251
252 private :
253
254 TArray<T> members; // members data
255 TArray<BHandle> links; // next member links
256 TArray<EntryInfo> entries; // entries info (first, last, count);
257 BHandle nextHandle; // next free member handle
258 Bool ok; // FALSE if object is not correct
259
260 Bool noEntry( BEntry entry )
261 { return (entries[ entry ].count == 0);
262 };
263 };
264 /*
265 template <class T>
266 void TBambuk<T>::appendMemberList( BEntry senior, BEntry junior )
267 {
268 assert( !noEntry(junior) );
269 assert( !noEntry(senior) );
270
271 assert( links[ entries[ senior ].last ] == NULLBHandle );
272
273 links[ entries[ senior ].last ] = links[ entries[ junior ].first ];
274 entries[ senior ].last = entries[ junior ].last;
275 entries[ senior ].count += entries[ junior ].count;
276
277 entries[ junior ].first = NULLBHandle;
278 entries[ junior ].last = NULLBHandle;
279 entries[ junior ].count = 0;
280 };
281 */
282 template <class T>
283 void TBambuk<T>::cleanEntries( int32_t from )
284 { assert( isOk() );
285 EntryInfo zeroEntry = { NULLBHandle, NULLBHandle, 0 };
286 entries.fill( &zeroEntry, from );
287 }
288
289 template <class T>
290 void TBambuk<T>::cleanMembers( T * zero_member, int32_t from )
291 { assert( isOk() );
292 members.fill( zero_member, from );
293 }
294
295 template <class T>
296 void TBambuk<T>::cleanLinks( int32_t from )
297 { assert( isOk() );
298 BHandle handle = NULLBHandle;
299 links.fill( &handle, from );
300 }
301
302 /* HUGE version for large member count */
303 template <class T> class THugeBambuk //: public TFarHeap
304 {
305
306 public :
307
308
309
310 THugeBambuk( void )
311 {};
312
313 THugeBambuk( BHandle max_members_count, BEntry max_entry_count )
314 {
315 createBambuk( max_members_count, max_entry_count);
316 if (!isOk())
317 destroyBambuk();
318 };
319
320
321
322 /* virtual */ Bool isOk( void )
323 { return (ok); };
324
325 Bool createBambuk( BHandle max_members_count, BEntry max_entry_count )
326 { // assert( max_members_count > 0 );
327 // assert( max_entry_count > 0 );
328
329 nextHandle = 0;
330 ok = ( members.create( max_members_count) &&
331 links .create( max_members_count ) &&
332 entries.create( max_entry_count )
333 );
334 if (ok){
335 cleanLinks();
336 cleanEntries();
337 };
338 return (ok);
339 };
340
341 void appendMember( BEntry entry_point, BHandle member_handle )
342 { assert( member_handle != NULLBHandle );
343 assert( links[ member_handle ] == NULLBHandle ); // member is single
344 if (noEntry( entry_point )) {
345 entries[ entry_point ].first =
346 entries[ entry_point ].last = member_handle;
347 entries[ entry_point ].count = 1;
348 }
349 else {
350 assert( links[ entries[ entry_point ].last ] == NULLBHandle );
351 links[ entries[ entry_point ].last ] = member_handle;
352 entries[ entry_point ].last = member_handle;
353 entries[ entry_point ].count++;
354 };
355 };
356
357 Bool GrowMembers(void)
358 {
359 if (!members.Grow()) // increase twice
360 return FALSE;
361 if (!links.Grow()) // increase twice
362 return FALSE;
363 return TRUE;
364 }
365
366 BHandle addMember( BEntry entry_point )
367 {
368
369 #ifndef NO_REALLOCATION
370 if (nextHandle >= members.lastHandle())
371 {
372 if (!GrowMembers())
373 return NULLBHandle;
374 if (nextHandle >= members.lastHandle())
375 return NULLBHandle;
376 }
377 #else
378 if (nextHandle >= members.lastHandle())
379 return NULLBHandle;
380 #endif // NO_REALLOCATION
381
382
383 links[ nextHandle ] = NULLBHandle;
384 if (noEntry( entry_point )) {
385 entries[ entry_point ].first =
386 entries[ entry_point ].last = nextHandle;
387 entries[ entry_point ].count = 1;
388 }
389 else {
390 assert( links[ entries[ entry_point ].last ] == NULLBHandle );
391 links[ entries[ entry_point ].last ] = nextHandle;
392 entries[ entry_point ].last = nextHandle;
393 entries[ entry_point ].count++;
394 };
395 return (nextHandle++);
396 };
397
398 BHandle firstEntryMember( BEntry entry_point )
399 { return entries[ entry_point ].first; }
400
401 BHandle lastEntryMember( BEntry entry_point )
402 { return entries[ entry_point ].last; }
403
404 BHandle memberEntryCount( BEntry entry_point )
405 { return entries[ entry_point ].count; }
406
407 BHandle memberTotalCount( void )
408 { return (nextHandle); }
409
410 BHandle memberVolume( void )
411 { return (members.volume()); }
412
413 BHandle memberRestCount( void )
414 { return (members.volume() - nextHandle); }
415
416 BHandle nextMember( BHandle cur_member )
417 { return links[ cur_member ]; }
418
419 BEntry lastEntry( void )
420 { return (entries.lastHandle()); }
421
422 void appendMemberList( BEntry senior, BEntry junior )
423 { assert( !noEntry(junior) );
424 assert( !noEntry(senior) );
425
426 assert( links[ entries[ senior ].last ] == NULLBHandle );
427 assert( links[ entries[ junior ].last ] == NULLBHandle );
428
429 links[ entries[ senior ].last ] = entries[ junior ].first;
430 entries[ senior ].last = entries[ junior ].last;
431 entries[ senior ].count += entries[ junior ].count;
432
433 entries[ junior ].first = NULLBHandle;
434 entries[ junior ].last = NULLBHandle;
435 entries[ junior ].count = 0;
436 };
437
438 T & operator [] ( BHandle cur_member)
439 { return members[cur_member];};
440
441 Bool shrinkBambuk( BHandle new_members_count,
442 BEntry new_entries_count = 0 )
443 {
444 assert( isOk() );
445 // assert( new_members_count > 0 );
446 BHandle old_members_count = members.volume();
447 assert( new_members_count < old_members_count );
448 BEntry old_entries_count = entries.volume();
449 assert( new_entries_count < old_entries_count );
450
451 if (!members.shrink(new_members_count))
452 return WRONG();
453 if (!links.shrink(new_members_count))
454 return WRONG();
455
456 if ( (new_entries_count > 0)
457 &&
458 (!entries.shrink(new_entries_count))
459 ) return WRONG();
460
461 /*
462 if (old_members_count < new_members_count)
463 cleanLinks( old_members_count );
464 if (old_entries_count < new_entries_count)
465 cleanEntries( old_members_count );
466 */
467 return TRUE;
468 };
469
470 void destroyBambuk( void )
471 {
472 members.flash();
473 links .flash();
474 entries.flash();
475 nextHandle = 0;
476 ok = FALSE;
477 };
478 void cleanMembers( T * zero_member, int32_t from );
479 void cleanLinks( int32_t from = 0 );
480 void cleanEntries( int32_t from = 0 );
481
482
483
484 ~THugeBambuk( void )
485 { destroyBambuk(); };
486
487 private :
488
489 TArray<T> members; // members data
490 TArray<BHandle> links; // next member links
491 TArray<EntryInfo> entries; // entries info (first, last, count);
492 BHandle nextHandle; // next free member handle
493 Bool ok; // FALSE if object is not correct
494
495 Bool noEntry( BEntry entry )
496 { return (entries[ entry ].count == 0);
497 };
498 };
499 /*
500 template <class T>
501 void THugeBambuk<T>::appendMemberList( BEntry senior, BEntry junior )
502 {
503 assert( !noEntry(junior) );
504 assert( !noEntry(senior) );
505
506 assert( links[ entries[ senior ].last ] == NULLBHandle );
507
508 links[ entries[ senior ].last ] = links[ entries[ junior ].first ];
509 entries[ senior ].last = entries[ junior ].last;
510 entries[ senior ].count += entries[ junior ].count;
511
512 entries[ junior ].first = NULLBHandle;
513 entries[ junior ].last = NULLBHandle;
514 entries[ junior ].count = 0;
515 };
516 */
517 template <class T>
518 void THugeBambuk<T>::cleanEntries( int32_t from )
519 { assert( isOk() );
520 EntryInfo zeroEntry = { NULLBHandle, NULLBHandle, 0 };
521 entries.fill( &zeroEntry, from );
522 }
523
524 template <class T>
525 void THugeBambuk<T>::cleanMembers( T * zero_member, int32_t from )
526 { assert( isOk() );
527 members.fill( zero_member, from );
528 }
529
530 template <class T>
531 void THugeBambuk<T>::cleanLinks( int32_t from )
532 { assert( isOk() );
533 BHandle handle = NULLBHandle;
534 links.fill( &handle, from );
535 }
536
537 #endif