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