1 : #define VSTR_SRCH_C
2 : /*
3 : * Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 James Antill
4 : *
5 : * This library is free software; you can redistribute it and/or
6 : * modify it under the terms of the GNU Lesser General Public
7 : * License as published by the Free Software Foundation; either
8 : * version 2 of the License, or (at your option) any later version.
9 : *
10 : * This library is distributed in the hope that it will be useful,
11 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 : * Lesser General Public License for more details.
14 : *
15 : * You should have received a copy of the GNU Lesser General Public
16 : * License along with this library; if not, write to the Free Software
17 : * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 : *
19 : * email: james@and.org
20 : */
21 : /* functions for searching within a vstr */
22 : #include "main.h"
23 :
24 : size_t vstr_srch_chr_fwd(const Vstr_base *base, size_t pos, size_t len,
25 : char srch)
26 156290 : {
27 156290 : Vstr_iter iter[1];
28 156290 : char *found = NULL;
29 :
30 156290 : if (!vstr_iter_fwd_beg(base, pos, len, iter))
31 643 : return (0);
32 :
33 182897 : ASSERT(len == vstr_iter_len(iter));
34 :
35 190131 : do
36 : {
37 190131 : if (iter->node->type != VSTR_TYPE_NODE_NON)
38 : {
39 190127 : found = vstr_wrap_memchr(iter->ptr, srch, iter->len);
40 190127 : if (found)
41 35799 : return (vstr_iter_pos(iter, pos, len) + (found - iter->ptr));
42 : }
43 154332 : } while (vstr_iter_fwd_nxt(iter));
44 :
45 119848 : return (0);
46 : }
47 :
48 : static size_t vstr__srch_chr_rev_slow(const Vstr_base *base,
49 : size_t pos, size_t len,
50 : char srch)
51 302 : {
52 302 : size_t ret = 0;
53 302 : size_t scan_pos = pos;
54 302 : size_t scan_len = len;
55 :
56 776 : while (scan_len)
57 : {
58 697 : size_t tmp = 0;
59 :
60 697 : assert(scan_pos < (pos + len));
61 :
62 697 : if (!(tmp = vstr_srch_chr_fwd(base, scan_pos, scan_len, srch)))
63 223 : break;
64 :
65 474 : ret = tmp;
66 :
67 474 : scan_pos = ret + 1;
68 474 : scan_len = len - VSTR_SC_POSDIFF(pos, ret);
69 : }
70 :
71 302 : return (ret);
72 : }
73 :
74 : static size_t vstr__srch_chr_rev_fast(const Vstr_base *base,
75 : size_t pos, size_t len,
76 : char srch)
77 104 : {
78 104 : unsigned int num = 0;
79 104 : unsigned int type = 0;
80 104 : char *scan_str = NULL;
81 104 : size_t scan_len = 0;
82 104 : char *found = NULL;
83 :
84 104 : if (!vstr__base_scan_rev_beg(base, pos, &len, &num, &type,
85 : &scan_str, &scan_len))
86 16 : return (0);
87 :
88 260 : do
89 : {
90 260 : if (type != VSTR_TYPE_NODE_NON)
91 : {
92 256 : found = vstr_wrap_memrchr(scan_str, srch, scan_len);
93 256 : if (found)
94 80 : return (pos + len + (found - scan_str));
95 : }
96 180 : } while (vstr__base_scan_rev_nxt(base, &len, &num, &type,
97 : &scan_str, &scan_len));
98 :
99 8 : return (0);
100 : }
101 :
102 : size_t vstr_srch_chr_rev(const Vstr_base *base, size_t pos, size_t len,
103 : char srch)
104 406 : {
105 406 : if (base->iovec_upto_date)
106 104 : return (vstr__srch_chr_rev_fast(base, pos, len, srch));
107 :
108 302 : return (vstr__srch_chr_rev_slow(base, pos, len, srch));
109 : }
110 :
111 : size_t vstr_srch_chrs_fwd(const Vstr_base *base, size_t pos, size_t len,
112 : const char *srch, size_t chrs_len)
113 49842 : {
114 49842 : size_t num = vstr_cspn_chrs_fwd(base, pos, len, srch, chrs_len);
115 :
116 49842 : if (num == len)
117 9880 : return (0);
118 :
119 39962 : return (pos + num);
120 : }
121 :
122 : size_t vstr_srch_chrs_rev(const Vstr_base *base, size_t pos, size_t len,
123 : const char *srch, size_t chrs_len)
124 125 : {
125 125 : size_t num = vstr_cspn_chrs_rev(base, pos, len, srch, chrs_len);
126 :
127 125 : if (num == len)
128 25 : return (0);
129 :
130 100 : return (pos + ((len - num) - 1));
131 : }
132 :
133 : size_t vstr_csrch_chrs_fwd(const Vstr_base *base, size_t pos, size_t len,
134 : const char *srch, size_t chrs_len)
135 45 : {
136 45 : size_t num = vstr_spn_chrs_fwd(base, pos, len, srch, chrs_len);
137 :
138 45 : if (num == len)
139 5 : return (0);
140 :
141 40 : return (pos + num);
142 : }
143 :
144 : size_t vstr_csrch_chrs_rev(const Vstr_base *base, size_t pos, size_t len,
145 : const char *srch, size_t chrs_len)
146 45 : {
147 45 : size_t num = vstr_spn_chrs_rev(base, pos, len, srch, chrs_len);
148 :
149 45 : if (num == len)
150 5 : return (0);
151 :
152 40 : return (pos + ((len - num) - 1));
153 : }
154 :
155 : size_t vstr_srch_buf_fwd(const Vstr_base *base, size_t pos, size_t len,
156 : const void *const str, const size_t str_len)
157 138719 : {
158 138719 : Vstr_iter iter[1];
159 :
160 138719 : if (!len || (str_len > len))
161 3433 : return (0);
162 :
163 135286 : if (!str_len)
164 1232 : return (pos);
165 :
166 134054 : if (!str && !base->node_non_used)
167 4 : return (0);
168 :
169 134050 : if (str && (str_len == 1))
170 22693 : return (vstr_srch_chr_fwd(base, pos, len, *(const char *)str));
171 :
172 111357 : if (!vstr_iter_fwd_beg(base, pos, len, iter))
173 8 : return (0);
174 :
175 3554680 : assert(len == vstr_iter_len(iter));
176 :
177 5334465 : do
178 : {
179 5334465 : if ((iter->node->type == VSTR_TYPE_NODE_NON) && !str)
180 : {
181 596 : if (!vstr_cmp_buf(base, vstr_iter_pos(iter, pos, len), str_len,
182 : NULL, str_len))
183 484 : return (vstr_iter_pos(iter, pos, len));
184 5333869 : goto next_loop;
185 : }
186 5333869 : if (!str)
187 778 : goto next_loop;
188 :
189 5333091 : if (iter->node->type == VSTR_TYPE_NODE_NON)
190 20 : goto next_loop;
191 :
192 : /* find buf */
193 5487996 : while (vstr_iter_len(iter) >= str_len)
194 : {
195 5484367 : size_t tmp = 0;
196 5484367 : size_t beg_pos = 0;
197 :
198 5484367 : assert(iter->len);
199 :
200 5484367 : if (*iter->ptr != *(const char *)str)
201 : {
202 5343268 : char *som = NULL; /* start of a possible match */
203 :
204 5343268 : if (!(som = vstr_wrap_memchr(iter->ptr, *(const char *)str,iter->len)))
205 5236560 : goto next_loop;
206 106708 : iter->len -= (som - iter->ptr);
207 106708 : iter->ptr = som;
208 106708 : continue;
209 : }
210 :
211 141099 : tmp = iter->len;
212 141099 : if (tmp > str_len)
213 101940 : tmp = str_len;
214 :
215 141099 : beg_pos = vstr_iter_pos(iter, pos, len);
216 :
217 141099 : if (!vstr_wrap_memcmp(iter->ptr, str, tmp) &&
218 : ((tmp == str_len) ||
219 : !vstr_cmp_buf(base, beg_pos + tmp, str_len - tmp,
220 : (const char *)str + tmp, str_len - tmp)))
221 80798 : return (beg_pos);
222 :
223 60301 : ++iter->ptr;
224 60301 : --iter->len;
225 :
226 60301 : if (!iter->len) break;
227 : }
228 :
229 : next_loop:
230 5253183 : continue;
231 5253183 : } while (vstr_iter_fwd_nxt(iter) && (vstr_iter_len(iter) >= str_len));
232 :
233 30067 : return (0);
234 : }
235 :
236 : static size_t vstr__srch_buf_rev_slow(const Vstr_base *base,
237 : size_t pos, size_t len,
238 : const void *const str,
239 : const size_t str_len)
240 120 : {
241 120 : size_t ret = 0;
242 120 : size_t scan_pos = pos;
243 120 : size_t scan_len = len;
244 :
245 304 : while (scan_len >= str_len)
246 : {
247 288 : size_t tmp = 0;
248 :
249 288 : assert(scan_pos < (pos + len));
250 :
251 288 : if (!(tmp = vstr_srch_buf_fwd(base, scan_pos, scan_len, str, str_len)))
252 104 : break;
253 :
254 184 : ret = tmp;
255 :
256 184 : scan_pos = ret + 1;
257 184 : scan_len = len - VSTR_SC_POSDIFF(pos, ret);
258 : }
259 :
260 120 : return (ret);
261 : }
262 :
263 : /* only to be used from srch_buf_rev_fast ... assumes a bunch of crap */
264 : static int vstr__cmp_eq_rev_buf(const Vstr_base *base, size_t len,
265 : unsigned int num, unsigned int type,
266 : const char *str, size_t str_len,
267 : char *scan_str, size_t scan_len)
268 140 : {
269 140 : assert((type != VSTR_TYPE_NODE_NON) && str && str_len &&
270 : scan_str && scan_len);
271 :
272 140 : if (str_len > (len + scan_len))
273 8 : return (FALSE);
274 :
275 216 : while (str_len)
276 : {
277 168 : size_t tmp = scan_len;
278 :
279 168 : if (type == VSTR_TYPE_NODE_NON)
280 4 : return (FALSE);
281 :
282 164 : if (tmp > str_len)
283 76 : tmp = str_len;
284 :
285 164 : if (vstr_wrap_memcmp((str + str_len) - tmp,
286 : (scan_str + scan_len) - tmp, tmp))
287 80 : return (FALSE);
288 84 : ASSERT(tmp);
289 :
290 84 : str_len -= tmp;
291 84 : scan_len -= tmp;
292 84 : if (!scan_len)
293 60 : tmp = vstr__base_scan_rev_nxt(base, &len, &num, &type,
294 : &scan_str, &scan_len);
295 66 : ASSERT(tmp || (!str_len && !scan_len));
296 : }
297 :
298 48 : return (TRUE);
299 : }
300 :
301 : /* only to be used from srch_buf_rev_fast ... assumes a bunch of crap */
302 : static int vstr__cmp_eq_rev_non(const Vstr_base *base, size_t len,
303 : unsigned int num, unsigned int type,
304 : size_t str_len, size_t scan_len)
305 32 : {
306 32 : char *scan_str = NULL;
307 32 : int tmp = FALSE;
308 :
309 32 : assert(type == VSTR_TYPE_NODE_NON);
310 :
311 32 : if (str_len > (len + scan_len))
312 4 : return (FALSE);
313 :
314 60 : while (type == VSTR_TYPE_NODE_NON)
315 : {
316 48 : if (str_len <= scan_len)
317 16 : return (TRUE);
318 :
319 32 : str_len -= scan_len;
320 :
321 32 : tmp = vstr__base_scan_rev_nxt(base, &len, &num, &type,
322 : &scan_str, &scan_len);
323 32 : ASSERT(tmp);
324 : }
325 :
326 12 : return (FALSE);
327 : }
328 :
329 : static size_t vstr__srch_buf_rev_fast(const Vstr_base *base,
330 : size_t pos, size_t len,
331 : const void *const str,
332 : size_t str_len)
333 136 : {
334 136 : unsigned int num = 0;
335 136 : unsigned int type = 0;
336 136 : char *scan_str = NULL;
337 136 : size_t scan_len = 0;
338 136 : size_t orig_len = len;
339 136 : const char *end_str = ((const char *)str) + (str_len - 1);
340 :
341 136 : if (!vstr__base_scan_rev_beg(base, pos, &len, &num, &type,
342 : &scan_str, &scan_len))
343 8 : return (0);
344 :
345 566 : assert(orig_len == (len + scan_len));
346 :
347 712 : do
348 : {
349 712 : size_t count = 0;
350 :
351 712 : if ((type == VSTR_TYPE_NODE_NON) && !str)
352 : {
353 32 : if (vstr__cmp_eq_rev_non(base, len, num, type, str_len, scan_len))
354 16 : return ((pos + len + scan_len) - str_len);
355 680 : continue;
356 : }
357 :
358 680 : if (!str)
359 172 : continue;
360 :
361 508 : if (type == VSTR_TYPE_NODE_NON)
362 32 : continue;
363 :
364 : /* find buf */
365 2264 : while (count < scan_len)
366 : {
367 1836 : size_t rest = 0;
368 1836 : size_t len_end = 0;
369 :
370 1836 : ++count;
371 1836 : rest = scan_len - count;
372 1836 : if (scan_str[scan_len - count] != end_str[0])
373 : {
374 1804 : char *som = NULL; /* start of a possible match */
375 :
376 1804 : if (!rest || !(som = vstr_wrap_memrchr(scan_str, end_str[0], rest)))
377 1280 : continue;
378 108 : count += ((scan_str + rest) - som);
379 108 : rest = scan_len - count;
380 : }
381 140 : assert(scan_str[scan_len - count] == end_str[0]);
382 :
383 140 : len_end = VSTR_SC_POSDIFF(count, scan_len);
384 140 : if (vstr__cmp_eq_rev_buf(base, len, num, type,
385 : str, str_len,
386 : scan_str, len_end))
387 48 : return ((pos + len + len_end) - str_len);
388 : }
389 648 : } while (vstr__base_scan_rev_nxt(base, &len, &num, &type,
390 : &scan_str, &scan_len));
391 :
392 64 : return (0);
393 : }
394 :
395 : size_t vstr_srch_buf_rev(const Vstr_base *base, size_t pos, size_t len,
396 : const void *const str, const size_t str_len)
397 1624 : {
398 1624 : if (!len || (str_len > len))
399 64 : return (0);
400 :
401 1560 : if (!str_len)
402 1252 : return (pos + len - 1);
403 :
404 308 : if (str && (str_len == 1))
405 52 : return (vstr_srch_chr_rev(base, pos, len, *(const char *)str));
406 :
407 256 : if (base->iovec_upto_date)
408 136 : return (vstr__srch_buf_rev_fast(base, pos, len, str, str_len));
409 :
410 120 : return (vstr__srch_buf_rev_slow(base, pos, len, str, str_len));
411 : }
412 :
413 : size_t vstr_srch_vstr_fwd(const Vstr_base *base, size_t pos, size_t len,
414 : const Vstr_base *ndl_base,
415 : size_t ndl_pos, size_t ndl_len)
416 336 : { /* TODO: this could be faster, esp. with NON nodes */
417 336 : Vstr_iter iter[1];
418 336 : size_t scan_pos = pos;
419 336 : size_t scan_len = len;
420 :
421 336 : if (ndl_len > len)
422 40 : return (0);
423 :
424 296 : if (!vstr_iter_fwd_beg(ndl_base, ndl_pos, ndl_len, iter))
425 8 : return (0);
426 :
427 436 : while ((scan_pos < vstr_sc_poslast(pos, len)) && (scan_len >= ndl_len))
428 : {
429 432 : if (!vstr_cmp(base, scan_pos, ndl_len, ndl_base, ndl_pos, ndl_len))
430 184 : return (scan_pos);
431 :
432 248 : --scan_len;
433 248 : ++scan_pos;
434 :
435 248 : if (iter->node->type != VSTR_TYPE_NODE_NON)
436 : {
437 248 : size_t tmp = 0;
438 :
439 248 : if (!(tmp = vstr_srch_buf_fwd(base, scan_pos, scan_len,
440 : iter->ptr, iter->len)))
441 100 : return (0);
442 :
443 148 : ASSERT(tmp >= scan_pos);
444 148 : scan_len -= tmp - scan_pos;
445 148 : scan_pos = tmp;
446 : }
447 : }
448 :
449 4 : return (0);
450 : }
451 :
452 : static size_t vstr__srch_vstr_rev_slow(const Vstr_base *base,
453 : size_t pos, size_t len,
454 : const Vstr_base *ndl_base,
455 : size_t ndl_pos, size_t ndl_len)
456 140 : {
457 140 : size_t ret = 0;
458 140 : size_t scan_pos = pos;
459 140 : size_t scan_len = len;
460 :
461 240 : while (scan_len >= ndl_len)
462 : {
463 180 : size_t tmp = 0;
464 :
465 180 : assert(scan_pos < (pos + len));
466 :
467 180 : if (!(tmp = vstr_srch_vstr_fwd(base, scan_pos, scan_len,
468 : ndl_base, ndl_pos, ndl_len)))
469 80 : break;
470 :
471 100 : ret = tmp;
472 :
473 100 : scan_pos = ret + 1;
474 100 : scan_len = len - VSTR_SC_POSDIFF(pos, ret);
475 : }
476 :
477 140 : return (ret);
478 : }
479 :
480 : size_t vstr_srch_vstr_rev(const Vstr_base *base, size_t pos, size_t len,
481 : const Vstr_base *ndl_base,
482 : size_t ndl_pos, size_t ndl_len)
483 140 : {
484 140 : return (vstr__srch_vstr_rev_slow(base, pos, len, ndl_base, ndl_pos, ndl_len));
485 : }
486 :
|
