18 #ifndef __HERMES_COMMON_ARRAY_H
19 #define __HERMES_COMMON_ARRAY_H
25 #define INVALID_IDX INT_MAX
48 static const int HERMES_PAGE_BITS = 10;
49 static const int HERMES_PAGE_SIZE = 1 << HERMES_PAGE_BITS;
50 static const int HERMES_PAGE_MASK = HERMES_PAGE_SIZE-1;
70 unused = array.unused;
72 nitems = array.nitems;
73 append_only = array.append_only;
75 for (
unsigned i = 0; i <
pages.size(); i++)
77 TYPE* new_page =
new TYPE[HERMES_PAGE_SIZE];
78 memcpy(new_page,
pages[i],
sizeof(TYPE) * HERMES_PAGE_SIZE);
86 for (
unsigned i = 0; i <
pages.size(); i++)
delete []
pages[i];
99 this->append_only = append_only;
105 TYPE* ptr = this->
add();
117 if (unused.empty() || append_only)
119 if (!(size & HERMES_PAGE_MASK))
121 TYPE* new_page =
new TYPE[HERMES_PAGE_SIZE];
122 pages.push_back(new_page);
124 item =
pages[size >> HERMES_PAGE_BITS] + (size & HERMES_PAGE_MASK);
130 int id = unused.back();
132 item =
pages[
id >> HERMES_PAGE_BITS] + (
id & HERMES_PAGE_MASK);
145 assert(
id >= 0 &&
id < size);
146 TYPE* item =
pages[
id >> HERMES_PAGE_BITS] + (
id & HERMES_PAGE_MASK);
149 unused.push_back(
id);
164 while (
get(index).used ==
false)
167 if (index >= nitems)
return INVALID_IDX;
181 while (
get(index).used ==
false)
184 if (index >= nitems)
return INVALID_IDX;
198 if (index > nitems - 1) index = nitems - 1;
199 while (
get(index).used ==
false)
202 if (index < 0)
return INVALID_IDX;
216 if (index > nitems - 1) index = nitems - 1;
217 while (
get(index).used ==
false)
220 if (index < 0)
return INVALID_IDX;
228 if (
get(idx).used ==
true)
return true;
240 TYPE* new_page =
new TYPE[HERMES_PAGE_SIZE];
241 memset(new_page, 0,
sizeof(TYPE) * HERMES_PAGE_SIZE);
242 pages.push_back(new_page);
243 size -= HERMES_PAGE_SIZE;
245 this->size =
pages.size() * HERMES_PAGE_SIZE;
254 for (
int i = start; i < size; i++)
255 if (
get(i).used) nitems++;
256 else unused.push_back(i);
263 if (!(size & HERMES_PAGE_MASK))
265 TYPE* new_page =
new TYPE[HERMES_PAGE_SIZE];
266 pages.push_back(new_page);
268 TYPE* item =
pages[size >> HERMES_PAGE_BITS] + (size & HERMES_PAGE_MASK);
274 int get_size()
const {
return size; }
275 int get_num_items()
const {
return nitems; }
277 TYPE&
get(
int id)
const {
return pages[
id >> HERMES_PAGE_BITS][
id & HERMES_PAGE_MASK]; }
278 TYPE& operator[] (
int id)
const {
return get(id); }
292 const unsigned int page_bits;
293 const unsigned int page_size;
294 const unsigned int page_mask;
298 LightArray(
unsigned int page_bits = 9) : page_bits(page_bits), page_size(1 << page_bits), page_mask((1 << page_bits) - 1)
305 for(
unsigned int i = 0; i < pages.size(); i++)
308 delete [] presence[i];
315 void add(TYPE item,
unsigned int id)
318 while(
id >= pages.size() * page_size)
320 TYPE* new_page =
new TYPE[page_size];
321 pages.push_back(new_page);
323 bool* new_page_presence =
new bool[page_size];
324 memset(new_page_presence, 0, page_size *
sizeof(
bool));
325 presence.push_back(new_page_presence);
328 temp = pages[
id >> page_bits] + (
id & page_mask);
331 presence[
id >> page_bits][
id & page_mask] =
true;
338 unsigned int get_size()
const
348 return presence[
id >> page_bits][
id & page_mask];
352 TYPE&
get(
unsigned int id)
const
355 return pages[
id >> page_bits][
id & page_mask];