38 #ifndef cmplr_segmented_array_INCLUDED
39 #define cmplr_segmented_array_INCLUDED
41 #ifndef __SGI_STL_ALGO_H
43 #if defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
44 #undef short // get around bogus type defs.
47 #endif // defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
55 using std::stable_sort;
59 using std::set_intersection;
60 using std::set_difference;
65 #endif // __SGI_STL_ALGO_H
67 #ifndef __SGI_STL_VECTOR_H
69 #if defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
70 #undef short // get around bogus type defs.
73 #endif // defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
78 #endif // __SGI_STL_VECTOR_H
80 #ifndef __SGI_STL_SLIST_H
82 #if defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
83 #undef short // get around bogus type defs.
86 #endif // defined(defs_INCLUDED) && !defined(USE_STANDARD_TYPES)
92 #endif // __SGI_STL_LIST_H
95 #ifndef ERRORS_INCLUDED
97 #endif // ERRORS_INCLUDED
99 #ifndef mempool_INCLUDED
101 #endif // mempool_INCLUDED
103 #ifndef segmented_array_INCLUDED
105 #endif // segmented_array_INCLUDED
107 #ifndef mempool_allocator_INCLUDED
195 for (kids_type::iterator kid =
kids.begin();
198 (*kid)->Delete_last();
204 for (kids_type::iterator kid =
kids.begin();
207 (*kid)->Delete_last(n);
213 for (kids_type::iterator kid =
kids.begin();
216 (*kid)->Construct_new_entry();
222 for (kids_type::iterator kid =
kids.begin();
225 (*kid)->Construct_new_entry(n);
239 (
"growing_table::Register: child must not be larger "
247 kids.push_front(&kid);
252 kids_type::iterator kid_ptr = std::find(
kids.begin(),
kids.end(), &kid);
253 if (kid_ptr !=
kids.end()) {
258 "an unregistered kid");
263 template <
class T, UINT block_size = 128>
322 UINT mask = block_size - 1;
323 return (s + mask) & ~mask;
350 for ( ; block_idx + 1 <
map.size() &&
351 map[block_idx].first + block_size ==
map[block_idx + 1].first;
354 return block_idx + 1;
369 for ( TempIteratorType entry =
map.begin(); entry !=
map.end(); ++entry ) {
382 Is_True (idx <
size, (
"Array subscript out of bound"));
383 return map[idx / block_size].first[idx % block_size];
387 Is_True (idx <
size, (
"Array subscript out of bound"));
388 return map[idx / block_size].first[idx % block_size];
441 UINT block_idx = idx / block_size;
466 template <
class T, UINT block_size>
474 map.push_back(std::pair<T*, BOOL>(marker, own_memory));
475 new_size -= block_size;
476 marker += block_size;
482 template <
class T, UINT block_size>
486 next_block_size += max_size - block_base;
491 last_map_entry = (map.end() - 1)->first;
493 }
while (last_map_entry != block);
498 (
"RELATED_SEGMENTED_ARRAY: size in limbo"));
499 block_base =
size - block_size;
500 UINT idx = block_base / block_size;
501 block = map[
idx].first;
502 while (idx > 0 && map[idx - 1].first + block_size == block) {
503 block = map[--
idx].first;
504 block_base -= block_size;
508 Is_True(map.begin() == map.end(),
509 (
"RELATED_SEGMENTED_ARRAY::Pop_Map: Map should be empty"));
516 template <
class T, UINT block_size>
520 Is_True (
size == max_size, (
"Invalid internal state in segmented array"));
524 if (next_block_size == 0)
525 new_size = block_size;
527 new_size = Round_up (next_block_size);
532 max_size += new_size;
535 Update_Map (block, new_size,
TRUE);
540 template <
class T, UINT block_size>
544 while (n >=
size - block_base) {
545 n -=
size - block_base;
550 Decrease_kids_size(n);
554 template <
class T, UINT block_size>
559 T &entry = New_entry ();
566 template <
class T, UINT block_size>
571 if (
size + n_elemt <= max_size) {
577 Copy (x, space_left);
578 n_elemt -= space_left;
582 Copy (x + space_left, n_elemt);
588 template <
class T, UINT block_size>
594 if (
size + n_elemt <= max_size) {
600 if (space_left > 0) {
601 Copy (x, space_left);
602 n_elemt -= space_left;
606 if (n_elemt >= block_size) {
607 UINT reused_size = n_elemt & ~(block_size - 1);
609 Update_Map (block, reused_size,
FALSE);
612 max_size += reused_size;
613 n_elemt -= reused_size;
615 if (next_block_size > reused_size)
616 next_block_size -= reused_size;
631 template <
class T, UINT block_size>
638 Is_True(map.begin() == map.end(),
639 (
"RELATED_SEGMENTED_ARRAY::Clear: Map should be empty"));
642 template <
class T, UINT block_size,
class OP>
650 while (first < last) {
651 T *block = &array[first];
653 for (
UINT j = 0; j <
size; ++j, ++block)
654 op (first + j, block);
664 template <
class T, UINT block_size,
class OP>
672 while (first < last) {
673 const T *block = &array[first];
675 for (
UINT j = 0; j <
size; ++j, ++block)
676 op (first + j, block);
683 template <
class T, UINT block_size,
class OP>
690 while (i < max_size) {
691 T *block = &array[i];
699 #define NOT_FOUND ((UINT) -1)
701 template <
class T, UINT block_size,
class PREDICATE>
704 const PREDICATE& pred,
UINT i = 0)
708 while (i < max_size) {
709 const T *block = &array[i];
711 for (
UINT j = 0; j <
size; ++j, ++block)
712 if (pred (i+j, block))
724 template <
class T, UINT block_size>
730 if (last_idx > from_array.
Size ())
731 last_idx = from_array.
Size ();
733 Is_True (last_idx >= first_idx, (
"Invalid copy range"));
735 UINT32 entries = last_idx - first_idx;
739 while (first_idx < last_idx) {
740 const T* block = &from_array[first_idx];
742 if (size > last_idx - first_idx)
743 size = last_idx - first_idx;
745 to_array.
Insert (block, size);
752 #endif // cmplr_segmented_array_INCLUDED