Annotation of parser3/src/main/pa_array.C, revision 1.50
1.23 paf 1: /** @file
1.24 paf 2: Parser: array class.
3:
1.46 paf 4: Copyright (c) 2001, 2002 ArtLebedev Group (http://www.artlebedev.com)
1.47 paf 5: Author: Alexandr Petrosian <paf@design.ru> (http://paf.design.ru)
1.49 paf 6: */
1.24 paf 7:
1.50 ! paf 8: static const char* IDENT_ARRAY_C="$Date: pa_array.C,v 1.49 2002/08/01 11:26:49 paf Exp $";
1.1 paf 9:
10: #include "pa_pool.h"
1.8 paf 11: #include "pa_array.h"
1.13 paf 12: #include "pa_exception.h"
1.30 paf 13: #include "pa_common.h"
1.1 paf 14:
1.45 paf 15: void Array::construct_new(int initial_rows) {
1.6 paf 16: head=tail=static_cast<Chunk *>(
1.41 paf 17: malloc(sizeof(int)+sizeof(Chunk::Row)*initial_rows+sizeof(Chunk *), 19));
1.6 paf 18: head->count=initial_rows;
1.1 paf 19: append_here=head->rows;
1.6 paf 20: link_row=&head->rows[initial_rows];
1.1 paf 21: link_row->link=0;
22: fused_rows=0;
1.45 paf 23: }
24:
25: Array::Array(Pool& apool, int initial_rows) : Pooled(apool) {
26: construct_new(max(initial_rows, CR_INITIAL_ROWS_DEFAULT));
27: }
28:
29: Array::Array(const Array& source, int offset) : Pooled(source.pool()) {
30: construct_new(source.size());
31: append_array(source, offset);
1.1 paf 32: }
33:
1.9 paf 34: void Array::expand(int chunk_rows) {
1.6 paf 35: Chunk *chunk=tail=static_cast<Chunk *>(
1.41 paf 36: malloc(sizeof(int)+sizeof(Chunk::Row)*chunk_rows+sizeof(Chunk *), 2));
1.6 paf 37: chunk->count=chunk_rows;
1.1 paf 38: link_row->link=chunk;
39: append_here=chunk->rows;
1.6 paf 40: link_row=&chunk->rows[chunk_rows];
1.1 paf 41: link_row->link=0;
42: }
43:
44:
1.15 paf 45: Array& Array::operator += (Item *src) {
1.1 paf 46: if(chunk_is_full())
1.32 parser 47: expand(tail->count+CR_GROW_COUNT);
1.1 paf 48:
49: append_here->item=src;
50: append_here++; fused_rows++;
51:
52: return *this;
53: }
54:
1.15 paf 55: Array::Item *Array::get(int index) const {
1.3 paf 56: if(!(index>=0 && index<size())) {
1.48 paf 57: throw Exception(0, 0,
1.12 paf 58: "Array::get(%d) out of range [0..%d]", index, size()-1);
1.33 parser 59: return 0; // never
1.2 paf 60: }
61:
1.42 paf 62: int base=0;
63: Chunk *chunk=head;
1.3 paf 64:
65: // navigate to chunk with "index" row
1.42 paf 66: while(!(index>=base && index<base+chunk->count)) {
67: int count=chunk->count;
68: base+=count;
69: chunk=chunk->rows[count].link;
1.3 paf 70: }
71:
1.42 paf 72: return chunk->rows[index-base].item;
1.16 paf 73: }
74:
75: void Array::put(int index, Item *item) {
76: if(!(index>=0 && index<size())) {
1.48 paf 77: throw Exception(0, 0,
1.16 paf 78: "Array::put(%d) out of range [0..%d]", index, size()-1);
1.33 parser 79: return; // never
1.16 paf 80: }
81:
1.42 paf 82: int base=0;
83: Chunk *chunk=head;
1.16 paf 84:
85: // navigate to chunk with "index" row
1.42 paf 86: while(!(index>=base && index<base+chunk->count)) {
87: int count=chunk->count;
88: base+=count;
89: chunk=chunk->rows[count].link;
1.16 paf 90: }
91:
1.42 paf 92: chunk->rows[index-base].item=item;
1.4 paf 93: }
94:
1.18 paf 95: Array& Array::append_array(const Array& src, int offset) {
96: int src_rows_to_copy=src.fused_rows-offset;
1.4 paf 97: int last_chunk_rows_left=link_row-append_here;
98:
1.5 paf 99: // our last chunk too small for src to fit?
1.18 paf 100: if(src_rows_to_copy>last_chunk_rows_left) {
1.5 paf 101: // shrink last chunk to used rows
102: tail->count-=last_chunk_rows_left;
103: link_row=append_here;
104:
1.6 paf 105: // append new src_used_rows-ed chunk
1.18 paf 106: expand(src_rows_to_copy);
1.5 paf 107: }
108:
1.18 paf 109: Chunk *src_chunk=src.head;
1.6 paf 110: Chunk::Row *dest_rows=append_here;
1.18 paf 111: int rows_left_to_copy=src.fused_rows;
112: int rows_left_to_skip=offset;
1.6 paf 113: while(true) {
114: int src_count=src_chunk->count;
115: Chunk *next_chunk=src_chunk->rows[src_count].link;
116: if(next_chunk) {
117: // not last source chunk
118: // taking it all
1.18 paf 119: int rows_to_copy_now=src_count-rows_left_to_skip;
120: if(rows_to_copy_now>0)
121: memcpy(dest_rows, src_chunk->rows+rows_left_to_skip,
122: sizeof(Chunk::Row)*rows_to_copy_now);
1.19 paf 123: else
124: rows_left_to_skip-=src_count;
125:
1.18 paf 126: dest_rows+=rows_to_copy_now;
1.6 paf 127: rows_left_to_copy-=src_count;
128: src_chunk=next_chunk;
129: } else {
130: // the last source chunk
131: // taking only those rows of chunk that _left_to_copy
1.18 paf 132: int rows_to_copy_now=rows_left_to_copy-rows_left_to_skip;
133: if(rows_to_copy_now>0)
134: memcpy(dest_rows, src_chunk->rows+rows_left_to_skip,
135: sizeof(Chunk::Row)*rows_to_copy_now);
1.6 paf 136: break;
1.4 paf 137: }
138: }
1.18 paf 139: append_here+=src_rows_to_copy;
140: fused_rows+=src_rows_to_copy;
1.4 paf 141:
142: return *this;
1.26 paf 143: }
144:
1.28 paf 145: void Array::for_each(For_each_func func, void *info) const {
1.26 paf 146: Chunk *chunk=head;
147: while(true) {
148: if(chunk==tail) { // last chunk?
149: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
150: (*func)(row->item, info);
151: break;
152: } else {
153: int count=chunk->count;
154: for(int i=0; i<count; i++)
155: (*func)(chunk->rows[i].item, info);
156: chunk=chunk->rows[count].link;
157: }
158: }
159: }
1.44 paf 160:
161: /*void Array::for_each(For_each_func_storage func, void *info) {
162: Chunk *chunk=head;
163: while(true) {
164: if(chunk==tail) { // last chunk?
165: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
166: (*func)(&row->item, info);
167: break;
168: } else {
169: int count=chunk->count;
170: for(int i=0; i<count; i++)
171: (*func)(&chunk->rows[i].item, info);
172: chunk=chunk->rows[count].link;
173: }
174: }
175: }
176: */
1.26 paf 177:
1.31 paf 178: /*void Array::for_each(For_each_func_const func, const void *info) const {
179: Chunk *chunk=head;
180: while(true) {
181: if(chunk==tail) { // last chunk?
182: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
183: (*func)(row->item, info);
184: break;
185: } else {
186: int count=chunk->count;
187: for(int i=0; i<count; i++)
188: (*func)(chunk->rows[i].item, info);
189: chunk=chunk->rows[count].link;
190: }
191: }
192: }
193: */
1.38 parser 194: void* Array::first_that(Item_that_func_const func, const void *info) const {
1.29 paf 195: Chunk *chunk=head;
196: while(true) {
197: if(chunk==tail) { // last chunk?
198: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
1.38 parser 199: if(void *result=(*func)(row->item, info))
200: return result;
1.29 paf 201: break;
202: } else {
203: int count=chunk->count;
204: for(int i=0; i<count; i++) {
205: Item* item=chunk->rows[i].item;
1.38 parser 206: if(void *result=(*func)(item, info))
207: return result;
1.29 paf 208: }
209: chunk=chunk->rows[count].link;
210: }
211: }
212: return 0;
213: }
214:
1.38 parser 215: void* Array::first_that(Item_that_func func, void *info) const {
1.26 paf 216: Chunk *chunk=head;
217: while(true) {
218: if(chunk==tail) { // last chunk?
219: for(Chunk::Row *row=chunk->rows; row!=append_here; row++)
1.38 parser 220: if(void *result=(*func)(row->item, info))
221: return result;
1.26 paf 222: break;
223: } else {
224: int count=chunk->count;
1.27 paf 225: for(int i=0; i<count; i++) {
226: Item* item=chunk->rows[i].item;
1.38 parser 227: if(void *result=(*func)(item, info))
228: return result;
1.27 paf 229: }
1.26 paf 230: chunk=chunk->rows[count].link;
231: }
232: }
233: return 0;
1.4 paf 234: }
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