Annotation of parser3/src/main/pa_string.C, revision 1.60
1.45 paf 1: /** @file
1.55 paf 2: Parser: string class. @see untasize_t.C.
1.46 paf 3:
1.36 paf 4: Copyright (c) 2001 ArtLebedev Group (http://www.artlebedev.com)
1.46 paf 5:
1.37 paf 6: Author: Alexander Petrosyan <paf@design.ru> (http://design.ru/paf)
1.36 paf 7:
1.60 ! paf 8: $Id: pa_string.C,v 1.59 2001/04/02 15:59:56 paf Exp $
1.4 paf 9: */
10:
1.48 paf 11: #include "pa_config_includes.h"
1.1 paf 12:
1.13 paf 13: #include "pa_pool.h"
1.12 paf 14: #include "pa_string.h"
1.5 paf 15: #include "pa_hash.h"
1.22 paf 16: #include "pa_exception.h"
1.53 paf 17: #include "pa_common.h"
1.60 ! paf 18: #include "pa_array.h"
! 19: #include "pa_globals.h"
! 20:
! 21: //#include "pa_sapi.h"
1.1 paf 22:
1.18 paf 23: // String
24:
1.55 paf 25: String::String(Pool& apool, const char *src, bool tasize_ted) :
1.17 paf 26: Pooled(apool) {
1.28 paf 27: last_chunk=&head;
28: head.count=CR_PREALLOCATED_COUNT;
1.5 paf 29: append_here=head.rows;
1.2 paf 30: head.preallocated_link=0;
1.28 paf 31: link_row=&head.rows[head.count];
1.8 paf 32: fused_rows=fsize=0;
1.41 paf 33:
34: if(src)
1.55 paf 35: if(tasize_ted)
1.41 paf 36: APPEND_TAINTED(src, 0, 0, 0);
37: else
1.53 paf 38: APPEND_CONST(src);
1.1 paf 39: }
40:
41: void String::expand() {
1.55 paf 42: size_t new_chunk_count=last_chunk->count+last_chunk->count*CR_GROW_PERCENT/100;
1.28 paf 43: last_chunk=static_cast<Chunk *>(
1.55 paf 44: malloc(sizeof(size_t)+sizeof(Chunk::Row)*new_chunk_count+sizeof(Chunk *)));
1.28 paf 45: last_chunk->count=new_chunk_count;
46: link_row->link=last_chunk;
47: append_here=last_chunk->rows;
48: link_row=&last_chunk->rows[last_chunk->count];
1.8 paf 49: link_row->link=0;
1.1 paf 50: }
51:
1.40 paf 52: String::String(const String& src) : Pooled(src.pool()) {
1.8 paf 53: head.count=CR_PREALLOCATED_COUNT;
54:
1.55 paf 55: size_t src_used_rows=src.fused_rows;
1.8 paf 56: if(src_used_rows<=head.count) {
1.55 paf 57: // all new rows fit size_to preallocated area
58: size_t curr_chunk_rows=head.count;
1.8 paf 59: memcpy(head.rows, src.head.rows, sizeof(Chunk::Row)*src_used_rows);
60: append_here=&head.rows[src_used_rows];
61: link_row=&head.rows[curr_chunk_rows];
62: } else {
63: // warning:
1.10 paf 64: // heavily relies on the fact
65: // "preallocated area is the same for all strings"
1.8 paf 66: //
67: // info:
68: // allocating only enough mem to fit src string rows
69: // next append would allocate a new chunk
70: //
1.55 paf 71: // new rows don't fit size_to preallocated area: splitting size_to two chunks
1.8 paf 72: // preallocated chunk src to constructing head
73: memcpy(head.rows, src.head.rows, sizeof(Chunk::Row)*head.count);
1.55 paf 74: // remaining rows size_to new_chunk
75: size_t curr_chunk_rows=src_used_rows-head.count;
1.8 paf 76: Chunk *new_chunk=static_cast<Chunk *>(
1.55 paf 77: malloc(sizeof(size_t)+sizeof(Chunk::Row)*curr_chunk_rows+sizeof(Chunk *)));
1.8 paf 78: new_chunk->count=curr_chunk_rows;
79: head.preallocated_link=new_chunk;
1.28 paf 80: append_here=link_row=&new_chunk->rows[new_chunk->count];
1.8 paf 81:
82: Chunk *old_chunk=src.head.preallocated_link;
83: Chunk::Row *new_rows=new_chunk->rows;
1.55 paf 84: size_t rows_left_to_copy=new_chunk->count;
1.8 paf 85: while(true) {
1.55 paf 86: size_t old_count=old_chunk->count;
1.8 paf 87: Chunk *next_chunk=old_chunk->rows[old_count].link;
88: if(next_chunk) {
89: // not last source chunk
90: // taking it all
91: memcpy(new_rows, old_chunk->rows, sizeof(Chunk::Row)*old_count);
92: new_rows+=old_count;
93: rows_left_to_copy-=old_count;
94:
95: old_chunk=next_chunk;
96: } else {
97: // the last source chunk
98: // taking only those rows of chunk that _left_to_copy
99: memcpy(new_rows, old_chunk->rows, sizeof(Chunk::Row)*rows_left_to_copy);
100: break;
101: }
102: }
1.5 paf 103: }
1.8 paf 104: link_row->link=0;
105: fused_rows=src_used_rows;
106: fsize=src.fsize;
1.5 paf 107: }
1.28 paf 108:
1.42 paf 109: String& String::append(const String& src, Untaint_lang lang, bool forced) {
1.60 ! paf 110: const Chunk *chunk=&src.head;
1.40 paf 111: do {
1.60 ! paf 112: const Chunk::Row *row=chunk->rows;
! 113: for(size_t i=0; i<chunk->count; i++, row++) {
! 114: if(row==src.append_here)
1.40 paf 115: goto break2;
1.60 ! paf 116:
! 117: APPEND(row->item.ptr, row->item.size,
! 118: (lang!=UL_PASS_APPENDED && (row->item.lang==UL_TAINTED || forced))?lang:row->item.lang,
! 119: row->item.origin.file, row->item.origin.line);
1.40 paf 120: }
121: chunk=row->link;
122: } while(chunk);
123: break2:
1.60 ! paf 124: return *this;
1.34 paf 125: }
1.60 ! paf 126:
1.13 paf 127: String& String::real_append(STRING_APPEND_PARAMS) {
1.9 paf 128: if(!src)
129: return *this;
1.26 paf 130: if(!size)
131: size=strlen(src);
132: if(!size)
1.9 paf 133: return *this;
134:
1.1 paf 135: if(chunk_is_full())
136: expand();
137:
138: append_here->item.ptr=src;
1.26 paf 139: fsize+=append_here->item.size=size;
1.52 paf 140: append_here->item.lang=lang;
1.13 paf 141: #ifndef NO_STRING_ORIGIN
1.14 paf 142: append_here->item.origin.file=file;
143: append_here->item.origin.line=line;
1.13 paf 144: #endif
1.8 paf 145: append_here++; fused_rows++;
1.1 paf 146:
147: return *this;
148: }
149:
1.16 paf 150: uint String::hash_code() const {
1.7 paf 151: uint result=0;
1.5 paf 152:
1.16 paf 153: const Chunk *chunk=&head;
1.5 paf 154: do {
1.16 paf 155: const Chunk::Row *row=chunk->rows;
1.55 paf 156: for(size_t i=0; i<chunk->count; i++) {
1.5 paf 157: if(row==append_here)
158: goto break2;
159:
1.6 paf 160: result=Hash::generic_code(result, row->item.ptr, row->item.size);
1.5 paf 161: row++;
162: }
163: chunk=row->link;
164: } while(chunk);
165: break2:
166: return result;
167: }
168:
1.60 ! paf 169: /// @todo move 'lang' skipping to pos
! 170: int String::cmp(int& partial, const String& src,
! 171: size_t this_offset, Untaint_lang lang) const {
1.59 paf 172: partial=-1;
1.55 paf 173: this_offset=min(this_offset, size()-1);
174:
1.16 paf 175: const Chunk *a_chunk=&head;
176: const Chunk *b_chunk=&src.head;
177: const Chunk::Row *a_row=a_chunk->rows;
178: const Chunk::Row *b_row=b_chunk->rows;
1.55 paf 179: size_t a_offset=this_offset;
180: size_t b_offset=0;
1.9 paf 181: Chunk::Row *a_end=append_here;
182: Chunk::Row *b_end=src.append_here;
1.55 paf 183: size_t a_countdown=a_chunk->count;
184: size_t b_countdown=b_chunk->count;
1.9 paf 185: bool a_break=false;
186: bool b_break=false;
1.55 paf 187: size_t result;
1.60 ! paf 188: size_t pos=0;
! 189: while(true) {
1.33 paf 190: a_break=a_row==a_end;
191: b_break=b_row==b_end;
192: if(a_break || b_break)
193: break;
194:
1.55 paf 195: if(pos+a_row->item.size > this_offset) {
1.60 ! paf 196: if(lang!=UL_UNKNOWN && a_row->item.lang!=lang)
! 197: return -1; // wrong lang -- bail out
! 198:
1.55 paf 199: int size_diff=
200: (a_row->item.size-a_offset)-
201: (b_row->item.size-b_offset);
202:
203: if(size_diff==0) { // a has same size as b
1.60 ! paf 204: result=memcmp(a_row->item.ptr+a_offset, b_row->item.ptr+b_offset,
! 205: a_row->item.size-a_offset);
1.55 paf 206: if(result)
207: return result;
1.60 ! paf 208: pos+=a_row->item.size;
1.55 paf 209: a_row++; a_countdown--; a_offset=0;
210: b_row++; b_countdown--; b_offset=0;
211: } else if (size_diff>0) { // a longer
1.60 ! paf 212: result=memcmp(a_row->item.ptr+a_offset, b_row->item.ptr+b_offset,
! 213: b_row->item.size-b_offset);
1.55 paf 214: if(result)
215: return result;
216: a_offset+=b_row->item.size-b_offset;
217: b_row++; b_countdown--; b_offset=0;
218: } else { // b longer
1.60 ! paf 219: result=memcmp(a_row->item.ptr+a_offset, b_row->item.ptr+b_offset,
! 220: a_row->item.size-a_offset);
1.55 paf 221: if(result)
222: return result;
223: b_offset+=a_row->item.size-a_offset;
1.60 ! paf 224: pos+=a_row->item.size;
1.55 paf 225: a_row++; a_countdown--; a_offset=0;
226: }
1.60 ! paf 227:
1.55 paf 228: if(!b_countdown) {
229: b_chunk=b_row->link;
230: b_row=b_chunk->rows;
231: b_countdown=b_chunk->count;
232: }
233: } else {
1.60 ! paf 234: a_offset-=a_row->item.size;
! 235: pos+=a_row->item.size;
! 236: a_row++; a_countdown--;
1.9 paf 237: }
238:
1.11 paf 239: if(!a_countdown) {
1.9 paf 240: a_chunk=a_row->link;
241: a_row=a_chunk->rows;
1.11 paf 242: a_countdown=a_chunk->count;
1.9 paf 243: }
1.27 paf 244: }
1.55 paf 245: if(a_break==b_break) { // ended simultaneously
246: partial=0; return 0;
247: } else if(a_break) { // first bytes equal, but a ended before b
248: partial=1; return -1;
249: } else {
250: partial=2; return +1;
251: }
1.27 paf 252: }
253:
1.60 ! paf 254: /// @todo move 'lang' skipping to pos
1.59 paf 255: int String::cmp(int& partial, const char* b_ptr, size_t src_size,
1.60 ! paf 256: size_t this_offset, Untaint_lang lang) const {
1.59 paf 257: partial=-1;
1.50 paf 258: size_t b_size=src_size?src_size:b_ptr?strlen(b_ptr):0;
1.59 paf 259: this_offset=min(this_offset, size()-1);
1.27 paf 260:
261: const Chunk *a_chunk=&head;
262: const Chunk::Row *a_row=a_chunk->rows;
1.59 paf 263: size_t a_offset=this_offset;
1.55 paf 264: size_t b_offset=0;
1.27 paf 265: Chunk::Row *a_end=append_here;
1.55 paf 266: size_t a_countdown=a_chunk->count;
1.27 paf 267: bool a_break=false;
268: bool b_break=false;
1.60 ! paf 269: size_t pos=0;
! 270: while(true) {
1.52 paf 271: a_break=a_row==a_end;
272: if(a_break || b_break)
273: break;
274:
1.59 paf 275: if(pos+a_row->item.size > this_offset) {
1.60 ! paf 276: if(lang!=UL_UNKNOWN && a_row->item.lang!=lang)
! 277: return -1; // wrong lang -- bail out
! 278:
1.59 paf 279: int size_diff=
280: (a_row->item.size-a_offset)-
281: (b_size-b_offset);
282:
283: if(size_diff==0) { // a has same size as b
284: if(size_t result=memcmp(a_row->item.ptr+a_offset, b_ptr+b_offset,
285: a_row->item.size-a_offset)!=0)
286: return result;
1.60 ! paf 287: pos+=a_row->item.size;
1.59 paf 288: a_row++; a_countdown--; a_offset=0;
289: b_break=true;
290: } else if (size_diff>0) { // a longer
291: if(size_t result=memcmp(a_row->item.ptr+a_offset, b_ptr+b_offset,
292: b_size-b_offset)!=0)
293: return result;
294: a_offset+=b_size-b_offset;
295: b_break=true;
296: } else { // b longer
297: if(size_t result=memcmp(a_row->item.ptr+a_offset, b_ptr+b_offset,
298: a_row->item.size-a_offset)!=0)
299: return result;
300: b_offset+=a_row->item.size-a_offset;
1.60 ! paf 301: pos+=a_row->item.size;
1.59 paf 302: a_row++; a_countdown--; a_offset=0;
303: }
304: } else {
1.60 ! paf 305: a_offset-=a_row->item.size;
! 306: pos+=a_row->item.size;
! 307: a_row++; a_countdown--;
1.27 paf 308: }
309:
310: if(!a_countdown) {
311: a_chunk=a_row->link;
312: a_row=a_chunk->rows;
313: a_countdown=a_chunk->count;
1.9 paf 314: }
315: }
1.55 paf 316: if(a_break==b_break) { // ended simultaneously
317: partial=0; return 0;
318: } else if(a_break) { // first bytes equal, but a ended before b
319: partial=1; return -1;
320: } else {
321: partial=2; return +1;
322: }
1.5 paf 323: }
1.46 paf 324:
325: #ifndef NO_STRING_ORIGIN
326: const Origin& String::origin() const {
327: if(!fused_rows)
328: THROW(0, 0,
1.50 paf 329: 0,
330: "String::origin() of empty string called");
1.46 paf 331:
1.49 paf 332: // determining origin by last appended piece
1.50 paf 333: // because first one frequently constant.
334: // ex: ^load[/file] "document_root" + "/file"
1.49 paf 335: return append_here[-1].item.origin;
1.46 paf 336: }
337: #endif
1.53 paf 338:
339: String& String::piece(size_t start, size_t finish) const {
340: start=max(0, start);
341: finish=min(size(), finish);
1.60 ! paf 342: if(start==finish)
! 343: return *empty_string;
1.53 paf 344:
345: String& result=*NEW String(pool());
346:
347: size_t pos=0;
348: const Chunk *chunk=&head;
349: do {
350: const Chunk::Row *row=chunk->rows;
1.55 paf 351: for(size_t i=0; i<chunk->count; pos+=row->item.size, i++, row++) {
1.53 paf 352: if(row==append_here)
353: goto break2;
354:
1.60 ! paf 355: size_t item_finish=pos+row->item.size;
! 356: if(item_finish > start) { // started now or already?
! 357: bool started=result.size()==0; // started now?
! 358: bool finished=finish <= item_finish; // finished now?
1.53 paf 359: size_t offset=started?start-pos:0;
360: size_t size=finished?finish-pos:row->item.size;
361: result.APPEND(
362: row->item.ptr+offset, size-offset,
363: row->item.lang,
364: row->item.origin.file, row->item.origin.line);
365: if(finished)
366: goto break2;
367: }
368: }
369: chunk=row->link;
370: } while(chunk);
371: break2:
1.60 ! paf 372: // SAPI::log(pool(), "piece of '%s' from %d to %d is '%s'",
! 373: //cstr(), start, finish, result.cstr());
1.53 paf 374: return result;
1.54 paf 375: }
376:
1.60 ! paf 377: int String::pos(const String& substr,
! 378: size_t result, Untaint_lang lang) const {
1.58 paf 379: for(; result<size(); result++) {
1.60 ! paf 380: int partial; cmp(partial, substr, result, lang);
1.58 paf 381: if(
382: partial==0 || // full match
383: partial==2) // 'substr' starts 'this'+'result'
384: return result;
385: }
386:
387: return -1;
388: }
389:
1.60 ! paf 390: int String::pos(const char *substr, size_t substr_size,
! 391: size_t result, Untaint_lang lang) const {
1.57 paf 392: for(; result<size(); result++) {
1.60 ! paf 393: int partial; cmp(partial, substr, substr_size, result, lang);
1.55 paf 394: if(
395: partial==0 || // full match
396: partial==2) // 'substr' starts 'this'+'result'
397: return result;
398: }
399:
400: return -1;
1.60 ! paf 401: }
! 402:
! 403: void String::split(Array& result,
! 404: size_t* pos_after_ref,
! 405: const char *delim, size_t delim_size,
! 406: Untaint_lang lang, int limit) const {
! 407: if(delim_size) {
! 408: size_t pos_after=pos_after_ref?*pos_after_ref:0;
! 409: int pos_before;
! 410: // while we have 'delim'...
! 411: for(; (pos_before=pos(delim, delim_size, pos_after, lang))>=0 && limit; limit--) {
! 412: result+=&piece(pos_after, pos_before);
! 413: pos_after=pos_before+delim_size;
! 414: }
! 415: // last piece
! 416: if(pos_after<size() && limit) {
! 417: result+=&piece(pos_after, size());
! 418: pos_after=size();
! 419: }
! 420: if(pos_after_ref)
! 421: *pos_after_ref=pos_after;
! 422: } else { // empty delim
! 423: result+=this;
! 424: if(pos_after_ref)
! 425: *pos_after_ref+=size();
! 426: }
! 427: }
! 428:
! 429: void String::split(Array& result,
! 430: size_t* pos_after_ref,
! 431: const String& delim, Untaint_lang lang,
! 432: int limit) const {
! 433: if(delim.size()) {
! 434: size_t pos_after=pos_after_ref?*pos_after_ref:0;
! 435: int pos_before;
! 436: // while we have 'delim'...
! 437: for(; (pos_before=pos(delim, pos_after, lang))>=0 && limit; limit--) {
! 438: result+=&piece(pos_after, pos_before);
! 439: pos_after=pos_before+delim.size();
! 440: }
! 441: // last piece
! 442: if(pos_after<size() && limit) {
! 443: result+=&piece(pos_after, size());
! 444: pos_after=size();
! 445: }
! 446: if(pos_after_ref)
! 447: *pos_after_ref=pos_after;
! 448: } else { // empty delim
! 449: result+=this;
! 450: if(pos_after_ref)
! 451: *pos_after_ref+=size();
! 452: }
1.53 paf 453: }
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_string.C CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / main