Annotation of parser3/src/main/pa_array.C, revision 1.33
1.23 paf 1: /** @file
1.24 paf 2: Parser: array class.
3:
1.21 paf 4: Copyright (c) 2001 ArtLebedev Group (http://www.artlebedev.com)
1.24 paf 5:
1.22 paf 6: Author: Alexander Petrosyan <paf@design.ru> (http://design.ru/paf)
1.21 paf 7:
1.33 ! parser 8: $Id: pa_array.C,v 1.32 2001/05/15 15:51:05 parser Exp $
1.1 paf 9: */
10:
1.25 paf 11: #include "pa_config_includes.h"
1.1 paf 12:
13: #include "pa_pool.h"
1.8 paf 14: #include "pa_array.h"
1.13 paf 15: #include "pa_exception.h"
1.30 paf 16: #include "pa_common.h"
1.1 paf 17:
1.33 ! parser 18: #include "pa_sapi.h"
! 19: #define ARRAY_STAT_MAX_PIECES 1000
! 20: int array_stat_pieces[ARRAY_STAT_MAX_PIECES];
! 21: void log_array_stats(Pool& pool) {
! 22: for(int i=0; i<ARRAY_STAT_MAX_PIECES; i++)
! 23: if(int v=array_stat_pieces[i])
! 24: SAPI::log(pool, "%i: %10d",
! 25: i, v);
! 26: }
! 27:
! 28: #define ARRAY_STAT_MAX_LEN 1000
! 29: int array_stat_lens[ARRAY_STAT_MAX_LEN];
! 30: void log_array_lens(Pool& pool) {
! 31: for(int i=0; i<ARRAY_STAT_MAX_LEN; i++)
! 32: if(int v=array_stat_lens[i])
! 33: SAPI::log(pool, "%i: %10d",
! 34: i, v);
! 35: }
! 36:
1.10 paf 37: Array::Array(Pool& apool, int initial_rows) :
1.33 ! parser 38: Pooled(apool),expand_times(0) {
! 39: array_stat_pieces[0]++;
! 40: array_stat_lens[0]++;
! 41: initial_rows=max(initial_rows, CR_INITIAL_ROWS_DEFAULT);
1.30 paf 42:
1.6 paf 43: head=tail=static_cast<Chunk *>(
1.17 paf 44: malloc(sizeof(int)+sizeof(Chunk::Row)*initial_rows+sizeof(Chunk *)));
1.6 paf 45: head->count=initial_rows;
1.1 paf 46: append_here=head->rows;
1.6 paf 47: link_row=&head->rows[initial_rows];
1.1 paf 48: link_row->link=0;
49: fused_rows=0;
1.2 paf 50:
1.3 paf 51: cache_chunk_base=0;
52: cache_chunk=head;
1.1 paf 53: }
54:
1.9 paf 55: void Array::expand(int chunk_rows) {
1.33 ! parser 56: {
! 57: int index=min(++expand_times, ARRAY_STAT_MAX_PIECES-1);
! 58: if(index)
! 59: array_stat_pieces[index-1]++;
! 60: array_stat_pieces[index]++;
! 61: }
1.20 paf 62:
1.6 paf 63: Chunk *chunk=tail=static_cast<Chunk *>(
1.17 paf 64: malloc(sizeof(int)+sizeof(Chunk::Row)*chunk_rows+sizeof(Chunk *)));
1.6 paf 65: chunk->count=chunk_rows;
1.1 paf 66: link_row->link=chunk;
67: append_here=chunk->rows;
1.6 paf 68: link_row=&chunk->rows[chunk_rows];
1.1 paf 69: link_row->link=0;
70: }
71:
72:
1.15 paf 73: Array& Array::operator += (Item *src) {
1.1 paf 74: if(chunk_is_full())
1.32 parser 75: expand(tail->count+CR_GROW_COUNT);
1.1 paf 76:
77: append_here->item=src;
78: append_here++; fused_rows++;
1.33 ! parser 79: {
! 80: int index=min(fused_rows, ARRAY_STAT_MAX_LEN-1);
! 81: if(index)
! 82: array_stat_lens[index-1]++;
! 83: array_stat_lens[index]++;
! 84: }
! 85:
1.1 paf 86:
87: return *this;
88: }
89:
1.15 paf 90: Array::Item *Array::get(int index) const {
1.3 paf 91: if(!(index>=0 && index<size())) {
1.17 paf 92: THROW(0, 0, 0,
1.12 paf 93: "Array::get(%d) out of range [0..%d]", index, size()-1);
1.33 ! parser 94: return 0; // never
1.2 paf 95: }
96:
1.3 paf 97: // if they ask index to the left of cached position, forget cache
98: if(index<cache_chunk_base) {
99: cache_chunk_base=0;
100: cache_chunk=head;
101: }
102:
103: // navigate to chunk with "index" row
104: while(!(index>=cache_chunk_base && index<cache_chunk_base+cache_chunk->count)) {
105: int count=cache_chunk->count;
106: cache_chunk_base+=count;
107: cache_chunk=cache_chunk->rows[count].link;
108: }
109:
110: return cache_chunk->rows[index-cache_chunk_base].item;
1.16 paf 111: }
112:
113: void Array::put(int index, Item *item) {
114: if(!(index>=0 && index<size())) {
1.17 paf 115: THROW(0, 0, 0,
1.16 paf 116: "Array::put(%d) out of range [0..%d]", index, size()-1);
1.33 ! parser 117: return; // never
1.16 paf 118: }
119:
120: // if they ask index to the left of cached position, forget cache
121: if(index<cache_chunk_base) {
122: cache_chunk_base=0;
123: cache_chunk=head;
124: }
125:
126: // navigate to chunk with "index" row
127: while(!(index>=cache_chunk_base && index<cache_chunk_base+cache_chunk->count)) {
128: int count=cache_chunk->count;
129: cache_chunk_base+=count;
130: cache_chunk=cache_chunk->rows[count].link;
131: }
132:
133: cache_chunk->rows[index-cache_chunk_base].item=item;
1.4 paf 134: }
135:
1.18 paf 136: Array& Array::append_array(const Array& src, int offset) {
137: int src_rows_to_copy=src.fused_rows-offset;
1.4 paf 138: int last_chunk_rows_left=link_row-append_here;
139:
1.5 paf 140: // our last chunk too small for src to fit?
1.18 paf 141: if(src_rows_to_copy>last_chunk_rows_left) {
1.5 paf 142: // shrink last chunk to used rows
143: tail->count-=last_chunk_rows_left;
144: link_row=append_here;
145:
1.6 paf 146: // append new src_used_rows-ed chunk
1.18 paf 147: expand(src_rows_to_copy);
1.5 paf 148: }
149:
1.18 paf 150: Chunk *src_chunk=src.head;
1.6 paf 151: Chunk::Row *dest_rows=append_here;
1.18 paf 152: int rows_left_to_copy=src.fused_rows;
153: int rows_left_to_skip=offset;
1.6 paf 154: while(true) {
155: int src_count=src_chunk->count;
156: Chunk *next_chunk=src_chunk->rows[src_count].link;
157: if(next_chunk) {
158: // not last source chunk
159: // taking it all
1.18 paf 160: int rows_to_copy_now=src_count-rows_left_to_skip;
161: if(rows_to_copy_now>0)
162: memcpy(dest_rows, src_chunk->rows+rows_left_to_skip,
163: sizeof(Chunk::Row)*rows_to_copy_now);
1.19 paf 164: else
165: rows_left_to_skip-=src_count;
166:
1.18 paf 167: dest_rows+=rows_to_copy_now;
1.6 paf 168: rows_left_to_copy-=src_count;
169: src_chunk=next_chunk;
170: } else {
171: // the last source chunk
172: // taking only those rows of chunk that _left_to_copy
1.18 paf 173: int rows_to_copy_now=rows_left_to_copy-rows_left_to_skip;
174: if(rows_to_copy_now>0)
175: memcpy(dest_rows, src_chunk->rows+rows_left_to_skip,
176: sizeof(Chunk::Row)*rows_to_copy_now);
1.6 paf 177: break;
1.4 paf 178: }
179: }
1.18 paf 180: append_here+=src_rows_to_copy;
181: fused_rows+=src_rows_to_copy;
1.4 paf 182:
183: return *this;
1.26 paf 184: }
185:
1.28 paf 186: void Array::for_each(For_each_func func, void *info) const {
1.26 paf 187: Chunk *chunk=head;
188: while(true) {
189: if(chunk==tail) { // last chunk?
190: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
191: (*func)(row->item, info);
192: break;
193: } else {
194: int count=chunk->count;
195: for(int i=0; i<count; i++)
196: (*func)(chunk->rows[i].item, info);
197: chunk=chunk->rows[count].link;
198: }
199: }
200: }
201:
1.31 paf 202: /*void Array::for_each(For_each_func_const func, const void *info) const {
203: Chunk *chunk=head;
204: while(true) {
205: if(chunk==tail) { // last chunk?
206: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
207: (*func)(row->item, info);
208: break;
209: } else {
210: int count=chunk->count;
211: for(int i=0; i<count; i++)
212: (*func)(chunk->rows[i].item, info);
213: chunk=chunk->rows[count].link;
214: }
215: }
216: }
217: */
1.29 paf 218: Array::Item* Array::first_that(First_that_func_const func, const void *info) const {
219: Chunk *chunk=head;
220: while(true) {
221: if(chunk==tail) { // last chunk?
222: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
223: if((*func)(row->item, info))
224: return row->item;
225: break;
226: } else {
227: int count=chunk->count;
228: for(int i=0; i<count; i++) {
229: Item* item=chunk->rows[i].item;
230: if((*func)(item, info))
231: return item;
232: }
233: chunk=chunk->rows[count].link;
234: }
235: }
236: return 0;
237: }
238:
239: Array::Item* Array::first_that(First_that_func func, void *info) const {
1.26 paf 240: Chunk *chunk=head;
241: while(true) {
242: if(chunk==tail) { // last chunk?
243: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
1.27 paf 244: if((*func)(row->item, info))
245: return row->item;
1.26 paf 246: break;
247: } else {
248: int count=chunk->count;
1.27 paf 249: for(int i=0; i<count; i++) {
250: Item* item=chunk->rows[i].item;
251: if((*func)(item, info))
252: return item;
253: }
1.26 paf 254: chunk=chunk->rows[count].link;
255: }
256: }
257: return 0;
1.4 paf 258: }
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_array.C CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / main