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