Branch data Line data Source code
1 : : /* stringlib: split implementation */
2 : :
3 : : #ifndef STRINGLIB_FASTSEARCH_H
4 : : #error must include "stringlib/fastsearch.h" before including this module
5 : : #endif
6 : :
7 : : /* Overallocate the initial list to reduce the number of reallocs for small
8 : : split sizes. Eg, "A A A A A A A A A A".split() (10 elements) has three
9 : : resizes, to sizes 4, 8, then 16. Most observed string splits are for human
10 : : text (roughly 11 words per line) and field delimited data (usually 1-10
11 : : fields). For large strings the split algorithms are bandwidth limited
12 : : so increasing the preallocation likely will not improve things.*/
13 : :
14 : : #define MAX_PREALLOC 12
15 : :
16 : : /* 5 splits gives 6 elements */
17 : : #define PREALLOC_SIZE(maxsplit) \
18 : : (maxsplit >= MAX_PREALLOC ? MAX_PREALLOC : maxsplit+1)
19 : :
20 : : #define SPLIT_APPEND(data, left, right) \
21 : : sub = STRINGLIB_NEW((data) + (left), \
22 : : (right) - (left)); \
23 : : if (sub == NULL) \
24 : : goto onError; \
25 : : if (PyList_Append(list, sub)) { \
26 : : Py_DECREF(sub); \
27 : : goto onError; \
28 : : } \
29 : : else \
30 : : Py_DECREF(sub);
31 : :
32 : : #define SPLIT_ADD(data, left, right) { \
33 : : sub = STRINGLIB_NEW((data) + (left), \
34 : : (right) - (left)); \
35 : : if (sub == NULL) \
36 : : goto onError; \
37 : : if (count < MAX_PREALLOC) { \
38 : : PyList_SET_ITEM(list, count, sub); \
39 : : } else { \
40 : : if (PyList_Append(list, sub)) { \
41 : : Py_DECREF(sub); \
42 : : goto onError; \
43 : : } \
44 : : else \
45 : : Py_DECREF(sub); \
46 : : } \
47 : : count++; }
48 : :
49 : :
50 : : /* Always force the list to the expected size. */
51 : : #define FIX_PREALLOC_SIZE(list) Py_SET_SIZE(list, count)
52 : :
53 : : Py_LOCAL_INLINE(PyObject *)
54 : 491607 : STRINGLIB(split_whitespace)(PyObject* str_obj,
55 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
56 : : Py_ssize_t maxcount)
57 : : {
58 : 491607 : Py_ssize_t i, j, count=0;
59 : 491607 : PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
60 : : PyObject *sub;
61 : :
62 [ - + ]: 491607 : if (list == NULL)
63 : 0 : return NULL;
64 : :
65 : 491607 : i = j = 0;
66 [ + + ]: 1721318 : while (maxcount-- > 0) {
67 [ + + + + ]: 3217049 : while (i < str_len && STRINGLIB_ISSPACE(str[i]))
68 : 1497429 : i++;
69 [ + + ]: 1719620 : if (i == str_len) break;
70 : 1308317 : j = i; i++;
71 [ + + + + ]: 9752202 : while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
72 : 8443885 : i++;
73 : : #if !STRINGLIB_MUTABLE
74 [ + + + + : 1308130 : if (j == 0 && i == str_len && STRINGLIB_CHECK_EXACT(str_obj)) {
+ - ]
75 : : /* No whitespace in str_obj, so just use it as list[0] */
76 : 78606 : Py_INCREF(str_obj);
77 : 78606 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
78 : 78606 : count++;
79 : 78606 : break;
80 : : }
81 : : #endif
82 [ - + + + : 1229711 : SPLIT_ADD(str, j, i);
- + ]
83 : : }
84 : :
85 [ + + ]: 491607 : if (i < str_len) {
86 : : /* Only occurs when maxcount was reached */
87 : : /* Skip any remaining whitespace and copy to end of string */
88 [ + + + + ]: 3408 : while (i < str_len && STRINGLIB_ISSPACE(str[i]))
89 : 1734 : i++;
90 [ + + ]: 1674 : if (i != str_len)
91 [ - + + + : 1668 : SPLIT_ADD(str, i, str_len);
- + ]
92 : : }
93 : 491607 : FIX_PREALLOC_SIZE(list);
94 : 491607 : return list;
95 : :
96 : 0 : onError:
97 : 0 : Py_DECREF(list);
98 : 0 : return NULL;
99 : : }
100 : :
101 : : Py_LOCAL_INLINE(PyObject *)
102 : 1356370 : STRINGLIB(split_char)(PyObject* str_obj,
103 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
104 : : const STRINGLIB_CHAR ch,
105 : : Py_ssize_t maxcount)
106 : : {
107 : 1356370 : Py_ssize_t i, j, count=0;
108 : 1356370 : PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
109 : : PyObject *sub;
110 : :
111 [ - + ]: 1356370 : if (list == NULL)
112 : 0 : return NULL;
113 : :
114 : 1356370 : i = j = 0;
115 [ + + + + ]: 3864171 : while ((j < str_len) && (maxcount-- > 0)) {
116 [ + + ]: 21752431 : for(; j < str_len; j++) {
117 : : /* I found that using memchr makes no difference */
118 [ + + ]: 20484038 : if (str[j] == ch) {
119 [ - + + + : 1239408 : SPLIT_ADD(str, i, j);
- + ]
120 : 1239408 : i = j = j + 1;
121 : 1239408 : break;
122 : : }
123 : : }
124 : : }
125 : : #if !STRINGLIB_MUTABLE
126 [ + + + - ]: 1354260 : if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
127 : : /* ch not in str_obj, so just use str_obj as list[0] */
128 : 551200 : Py_INCREF(str_obj);
129 : 551200 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
130 : 551200 : count++;
131 : : } else
132 : : #endif
133 [ + - ]: 805170 : if (i <= str_len) {
134 [ - + + + : 805170 : SPLIT_ADD(str, i, str_len);
- + ]
135 : : }
136 : 1356370 : FIX_PREALLOC_SIZE(list);
137 : 1356370 : return list;
138 : :
139 : 0 : onError:
140 : 0 : Py_DECREF(list);
141 : 0 : return NULL;
142 : : }
143 : :
144 : : Py_LOCAL_INLINE(PyObject *)
145 : 1915792 : STRINGLIB(split)(PyObject* str_obj,
146 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
147 : : const STRINGLIB_CHAR* sep, Py_ssize_t sep_len,
148 : : Py_ssize_t maxcount)
149 : : {
150 : 1915792 : Py_ssize_t i, j, pos, count=0;
151 : : PyObject *list, *sub;
152 : :
153 [ + + ]: 1915792 : if (sep_len == 0) {
154 : 9 : PyErr_SetString(PyExc_ValueError, "empty separator");
155 : 9 : return NULL;
156 : : }
157 [ + + ]: 1915783 : else if (sep_len == 1)
158 : 1356370 : return STRINGLIB(split_char)(str_obj, str, str_len, sep[0], maxcount);
159 : :
160 : 559413 : list = PyList_New(PREALLOC_SIZE(maxcount));
161 [ - + ]: 559413 : if (list == NULL)
162 : 0 : return NULL;
163 : :
164 : 559413 : i = j = 0;
165 [ + + ]: 1014618 : while (maxcount-- > 0) {
166 : 1014368 : pos = FASTSEARCH(str+i, str_len-i, sep, sep_len, -1, FAST_SEARCH);
167 [ + + ]: 1014368 : if (pos < 0)
168 : 559163 : break;
169 : 455205 : j = i + pos;
170 [ - + + + : 455205 : SPLIT_ADD(str, i, j);
- + ]
171 : 455205 : i = j + sep_len;
172 : : }
173 : : #if !STRINGLIB_MUTABLE
174 [ + + + - ]: 559390 : if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
175 : : /* No match in str_obj, so just use it as list[0] */
176 : 141554 : Py_INCREF(str_obj);
177 : 141554 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
178 : 141554 : count++;
179 : : } else
180 : : #endif
181 : : {
182 [ - + + + : 417859 : SPLIT_ADD(str, i, str_len);
- + ]
183 : : }
184 : 559413 : FIX_PREALLOC_SIZE(list);
185 : 559413 : return list;
186 : :
187 : 0 : onError:
188 : 0 : Py_DECREF(list);
189 : 0 : return NULL;
190 : : }
191 : :
192 : : Py_LOCAL_INLINE(PyObject *)
193 : 155 : STRINGLIB(rsplit_whitespace)(PyObject* str_obj,
194 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
195 : : Py_ssize_t maxcount)
196 : : {
197 : 155 : Py_ssize_t i, j, count=0;
198 : 155 : PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
199 : : PyObject *sub;
200 : :
201 [ - + ]: 155 : if (list == NULL)
202 : 0 : return NULL;
203 : :
204 : 155 : i = j = str_len - 1;
205 [ + + ]: 586 : while (maxcount-- > 0) {
206 [ + + + + ]: 1176 : while (i >= 0 && STRINGLIB_ISSPACE(str[i]))
207 : 670 : i--;
208 [ + + ]: 506 : if (i < 0) break;
209 : 431 : j = i; i--;
210 [ + + + + ]: 812 : while (i >= 0 && !STRINGLIB_ISSPACE(str[i]))
211 : 381 : i--;
212 : : #if !STRINGLIB_MUTABLE
213 [ + + - + : 322 : if (j == str_len - 1 && i < 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
- - ]
214 : : /* No whitespace in str_obj, so just use it as list[0] */
215 : 0 : Py_INCREF(str_obj);
216 : 0 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
217 : 0 : count++;
218 : 0 : break;
219 : : }
220 : : #endif
221 [ - + + + : 431 : SPLIT_ADD(str, i + 1, j + 1);
- + ]
222 : : }
223 : :
224 [ + + ]: 155 : if (i >= 0) {
225 : : /* Only occurs when maxcount was reached */
226 : : /* Skip any remaining whitespace and copy to beginning of string */
227 [ + + + + ]: 168 : while (i >= 0 && STRINGLIB_ISSPACE(str[i]))
228 : 112 : i--;
229 [ + + ]: 56 : if (i >= 0)
230 [ - + + + : 52 : SPLIT_ADD(str, 0, i + 1);
- + ]
231 : : }
232 : 155 : FIX_PREALLOC_SIZE(list);
233 [ - + ]: 155 : if (PyList_Reverse(list) < 0)
234 : 0 : goto onError;
235 : 155 : return list;
236 : :
237 : 0 : onError:
238 : 0 : Py_DECREF(list);
239 : 0 : return NULL;
240 : : }
241 : :
242 : : Py_LOCAL_INLINE(PyObject *)
243 : 3721 : STRINGLIB(rsplit_char)(PyObject* str_obj,
244 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
245 : : const STRINGLIB_CHAR ch,
246 : : Py_ssize_t maxcount)
247 : : {
248 : 3721 : Py_ssize_t i, j, count=0;
249 : 3721 : PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
250 : : PyObject *sub;
251 : :
252 [ - + ]: 3721 : if (list == NULL)
253 : 0 : return NULL;
254 : :
255 : 3721 : i = j = str_len - 1;
256 [ + + + + ]: 7653 : while ((i >= 0) && (maxcount-- > 0)) {
257 [ + + ]: 31852 : for(; i >= 0; i--) {
258 [ + + ]: 31790 : if (str[i] == ch) {
259 [ - + + + : 3870 : SPLIT_ADD(str, i + 1, j + 1);
- + ]
260 : 3870 : j = i = i - 1;
261 : 3870 : break;
262 : : }
263 : : }
264 : : }
265 : : #if !STRINGLIB_MUTABLE
266 [ + + + - ]: 3701 : if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
267 : : /* ch not in str_obj, so just use str_obj as list[0] */
268 : 48 : Py_INCREF(str_obj);
269 : 48 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
270 : 48 : count++;
271 : : } else
272 : : #endif
273 [ + - ]: 3673 : if (j >= -1) {
274 [ - + + + : 3673 : SPLIT_ADD(str, 0, j + 1);
- + ]
275 : : }
276 : 3721 : FIX_PREALLOC_SIZE(list);
277 [ - + ]: 3721 : if (PyList_Reverse(list) < 0)
278 : 0 : goto onError;
279 : 3721 : return list;
280 : :
281 : 0 : onError:
282 : 0 : Py_DECREF(list);
283 : 0 : return NULL;
284 : : }
285 : :
286 : : Py_LOCAL_INLINE(PyObject *)
287 : 3832 : STRINGLIB(rsplit)(PyObject* str_obj,
288 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
289 : : const STRINGLIB_CHAR* sep, Py_ssize_t sep_len,
290 : : Py_ssize_t maxcount)
291 : : {
292 : 3832 : Py_ssize_t j, pos, count=0;
293 : : PyObject *list, *sub;
294 : :
295 [ + + ]: 3832 : if (sep_len == 0) {
296 : 8 : PyErr_SetString(PyExc_ValueError, "empty separator");
297 : 8 : return NULL;
298 : : }
299 [ + + ]: 3824 : else if (sep_len == 1)
300 : 3721 : return STRINGLIB(rsplit_char)(str_obj, str, str_len, sep[0], maxcount);
301 : :
302 : 103 : list = PyList_New(PREALLOC_SIZE(maxcount));
303 [ - + ]: 103 : if (list == NULL)
304 : 0 : return NULL;
305 : :
306 : 103 : j = str_len;
307 [ + + ]: 444 : while (maxcount-- > 0) {
308 : 412 : pos = FASTSEARCH(str, j, sep, sep_len, -1, FAST_RSEARCH);
309 [ + + ]: 412 : if (pos < 0)
310 : 71 : break;
311 [ - + + + : 341 : SPLIT_ADD(str, pos + sep_len, j);
- + ]
312 : 341 : j = pos;
313 : : }
314 : : #if !STRINGLIB_MUTABLE
315 [ + + + - ]: 80 : if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
316 : : /* No match in str_obj, so just use it as list[0] */
317 : 17 : Py_INCREF(str_obj);
318 : 17 : PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
319 : 17 : count++;
320 : : } else
321 : : #endif
322 : : {
323 [ - + + + : 86 : SPLIT_ADD(str, 0, j);
- + ]
324 : : }
325 : 103 : FIX_PREALLOC_SIZE(list);
326 [ - + ]: 103 : if (PyList_Reverse(list) < 0)
327 : 0 : goto onError;
328 : 103 : return list;
329 : :
330 : 0 : onError:
331 : 0 : Py_DECREF(list);
332 : 0 : return NULL;
333 : : }
334 : :
335 : : Py_LOCAL_INLINE(PyObject *)
336 : 331291 : STRINGLIB(splitlines)(PyObject* str_obj,
337 : : const STRINGLIB_CHAR* str, Py_ssize_t str_len,
338 : : int keepends)
339 : : {
340 : : /* This does not use the preallocated list because splitlines is
341 : : usually run with hundreds of newlines. The overhead of
342 : : switching between PyList_SET_ITEM and append causes about a
343 : : 2-3% slowdown for that common case. A smarter implementation
344 : : could move the if check out, so the SET_ITEMs are done first
345 : : and the appends only done when the prealloc buffer is full.
346 : : That's too much work for little gain.*/
347 : :
348 : : Py_ssize_t i;
349 : : Py_ssize_t j;
350 : 331291 : PyObject *list = PyList_New(0);
351 : : PyObject *sub;
352 : :
353 [ - + ]: 331291 : if (list == NULL)
354 : 0 : return NULL;
355 : :
356 [ + + ]: 1768985 : for (i = j = 0; i < str_len; ) {
357 : : Py_ssize_t eol;
358 : :
359 : : /* Find a line and append it */
360 [ + + + + : 56515168 : while (i < str_len && !STRINGLIB_ISLINEBREAK(str[i]))
+ + + + +
+ + + ]
361 : 54897069 : i++;
362 : :
363 : : /* Skip the line break reading CRLF as one line break */
364 : 1618099 : eol = i;
365 [ + + ]: 1618099 : if (i < str_len) {
366 [ + + + + : 1405059 : if (str[i] == '\r' && i + 1 < str_len && str[i+1] == '\n')
+ + ]
367 : 33854 : i += 2;
368 : : else
369 : 1371205 : i++;
370 [ + + ]: 1405059 : if (keepends)
371 : 1214297 : eol = i;
372 : : }
373 : : #if !STRINGLIB_MUTABLE
374 [ + + + + : 1617839 : if (j == 0 && eol == str_len && STRINGLIB_CHECK_EXACT(str_obj)) {
+ + ]
375 : : /* No linebreak in str_obj, so just use it as list[0] */
376 [ - + ]: 180405 : if (PyList_Append(list, str_obj))
377 : 0 : goto onError;
378 : 180405 : break;
379 : : }
380 : : #endif
381 [ - + - + ]: 1437694 : SPLIT_APPEND(str, j, eol);
382 : 1437694 : j = i;
383 : : }
384 : 331291 : return list;
385 : :
386 : 0 : onError:
387 : 0 : Py_DECREF(list);
388 : 0 : return NULL;
389 : : }
390 : :
|
