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