LCOV - code coverage report
Current view: | top level - Objects/stringlib - split.h (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 103 | 189 | 54.5 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 6 | 35 | 17.1 %
|  |  | Branches: | 95 | 232 | 40.9 %

               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                 :       5258 : STRINGLIB(split_whitespace)(PyObject* str_obj,
          55                 :            :                            const STRINGLIB_CHAR* str, Py_ssize_t str_len,
          56                 :            :                            Py_ssize_t maxcount)
          57                 :            : {
          58                 :       5258 :     Py_ssize_t i, j, count=0;
          59                 :       5258 :     PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
          60                 :            :     PyObject *sub;
          61                 :            :
          62         [ -  + ]:       5258 :     if (list == NULL)
          63                 :          0 :         return NULL;
          64                 :            :
          65                 :       5258 :     i = j = 0;
          66         [ +  + ]:      20445 :     while (maxcount-- > 0) {
          67   [ +  +  +  + ]:      39164 :         while (i < str_len && STRINGLIB_ISSPACE(str[i]))
          68                 :      18720 :             i++;
          69         [ +  + ]:      20444 :         if (i == str_len) break;
          70                 :      15190 :         j = i; i++;
          71   [ +  +  +  + ]:     136621 :         while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
          72                 :     121431 :             i++;
          73                 :            : #if !STRINGLIB_MUTABLE
          74   [ +  +  +  +  :      15190 :         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                 :          3 :             Py_INCREF(str_obj);
          77                 :          3 :             PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
          78                 :          3 :             count++;
          79                 :          3 :             break;
          80                 :            :         }
          81                 :            : #endif
          82   [ -  +  +  +  :      15187 :         SPLIT_ADD(str, j, i);
                       -  + ]
          83                 :            :     }
          84                 :            :
          85         [ +  + ]:       5258 :     if (i < str_len) {
          86                 :            :         /* Only occurs when maxcount was reached */
          87                 :            :         /* Skip any remaining whitespace and copy to end of string */
          88   [ +  -  +  + ]:          2 :         while (i < str_len && STRINGLIB_ISSPACE(str[i]))
          89                 :          1 :             i++;
          90         [ +  - ]:          1 :         if (i != str_len)
          91   [ -  +  +  -  :          1 :             SPLIT_ADD(str, i, str_len);
                       -  - ]
          92                 :            :     }
          93                 :       5258 :     FIX_PREALLOC_SIZE(list);
          94                 :       5258 :     return list;
          95                 :            :
          96                 :          0 :   onError:
          97                 :          0 :     Py_DECREF(list);
          98                 :          0 :     return NULL;
          99                 :            : }
         100                 :            :
         101                 :            : Py_LOCAL_INLINE(PyObject *)
         102                 :        277 : 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                 :        277 :     Py_ssize_t i, j, count=0;
         108                 :        277 :     PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
         109                 :            :     PyObject *sub;
         110                 :            :
         111         [ -  + ]:        277 :     if (list == NULL)
         112                 :          0 :         return NULL;
         113                 :            :
         114                 :        277 :     i = j = 0;
         115   [ +  +  +  - ]:        595 :     while ((j < str_len) && (maxcount-- > 0)) {
         116         [ +  + ]:       8813 :         for(; j < str_len; j++) {
         117                 :            :             /* I found that using memchr makes no difference */
         118         [ +  + ]:       8583 :             if (str[j] == ch) {
         119   [ -  +  +  -  :         88 :                 SPLIT_ADD(str, i, j);
                       -  - ]
         120                 :         88 :                 i = j = j + 1;
         121                 :         88 :                 break;
         122                 :            :             }
         123                 :            :         }
         124                 :            :     }
         125                 :            : #if !STRINGLIB_MUTABLE
         126   [ +  +  +  - ]:        277 :     if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
         127                 :            :         /* ch not in str_obj, so just use str_obj as list[0] */
         128                 :        216 :         Py_INCREF(str_obj);
         129                 :        216 :         PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
         130                 :        216 :         count++;
         131                 :            :     } else
         132                 :            : #endif
         133         [ +  - ]:         61 :     if (i <= str_len) {
         134   [ -  +  +  -  :         61 :         SPLIT_ADD(str, i, str_len);
                       -  - ]
         135                 :            :     }
         136                 :        277 :     FIX_PREALLOC_SIZE(list);
         137                 :        277 :     return list;
         138                 :            :
         139                 :          0 :   onError:
         140                 :          0 :     Py_DECREF(list);
         141                 :          0 :     return NULL;
         142                 :            : }
         143                 :            :
         144                 :            : Py_LOCAL_INLINE(PyObject *)
         145                 :       2807 : 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                 :       2807 :     Py_ssize_t i, j, pos, count=0;
         151                 :            :     PyObject *list, *sub;
         152                 :            :
         153         [ -  + ]:       2807 :     if (sep_len == 0) {
         154                 :          0 :         PyErr_SetString(PyExc_ValueError, "empty separator");
         155                 :          0 :         return NULL;
         156                 :            :     }
         157         [ +  + ]:       2807 :     else if (sep_len == 1)
         158                 :        277 :         return STRINGLIB(split_char)(str_obj, str, str_len, sep[0], maxcount);
         159                 :            :
         160                 :       2530 :     list = PyList_New(PREALLOC_SIZE(maxcount));
         161         [ -  + ]:       2530 :     if (list == NULL)
         162                 :          0 :         return NULL;
         163                 :            :
         164                 :       2530 :     i = j = 0;
         165         [ +  - ]:       5060 :     while (maxcount-- > 0) {
         166                 :       5060 :         pos = FASTSEARCH(str+i, str_len-i, sep, sep_len, -1, FAST_SEARCH);
         167         [ +  + ]:       5060 :         if (pos < 0)
         168                 :       2530 :             break;
         169                 :       2530 :         j = i + pos;
         170   [ -  +  +  -  :       2530 :         SPLIT_ADD(str, i, j);
                       -  - ]
         171                 :       2530 :         i = j + sep_len;
         172                 :            :     }
         173                 :            : #if !STRINGLIB_MUTABLE
         174   [ -  +  -  - ]:       2530 :     if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
         175                 :            :         /* No match in str_obj, so just use it as list[0] */
         176                 :          0 :         Py_INCREF(str_obj);
         177                 :          0 :         PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
         178                 :          0 :         count++;
         179                 :            :     } else
         180                 :            : #endif
         181                 :            :     {
         182   [ -  +  +  -  :       2530 :         SPLIT_ADD(str, i, str_len);
                       -  - ]
         183                 :            :     }
         184                 :       2530 :     FIX_PREALLOC_SIZE(list);
         185                 :       2530 :     return list;
         186                 :            :
         187                 :          0 :   onError:
         188                 :          0 :     Py_DECREF(list);
         189                 :          0 :     return NULL;
         190                 :            : }
         191                 :            :
         192                 :            : Py_LOCAL_INLINE(PyObject *)
         193                 :          0 : STRINGLIB(rsplit_whitespace)(PyObject* str_obj,
         194                 :            :                             const STRINGLIB_CHAR* str, Py_ssize_t str_len,
         195                 :            :                             Py_ssize_t maxcount)
         196                 :            : {
         197                 :          0 :     Py_ssize_t i, j, count=0;
         198                 :          0 :     PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
         199                 :            :     PyObject *sub;
         200                 :            :
         201         [ #  # ]:          0 :     if (list == NULL)
         202                 :          0 :         return NULL;
         203                 :            :
         204                 :          0 :     i = j = str_len - 1;
         205         [ #  # ]:          0 :     while (maxcount-- > 0) {
         206   [ #  #  #  # ]:          0 :         while (i >= 0 && STRINGLIB_ISSPACE(str[i]))
         207                 :          0 :             i--;
         208         [ #  # ]:          0 :         if (i < 0) break;
         209                 :          0 :         j = i; i--;
         210   [ #  #  #  # ]:          0 :         while (i >= 0 && !STRINGLIB_ISSPACE(str[i]))
         211                 :          0 :             i--;
         212                 :            : #if !STRINGLIB_MUTABLE
         213   [ #  #  #  #  :          0 :         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   [ #  #  #  #  :          0 :         SPLIT_ADD(str, i + 1, j + 1);
                       #  # ]
         222                 :            :     }
         223                 :            :
         224         [ #  # ]:          0 :     if (i >= 0) {
         225                 :            :         /* Only occurs when maxcount was reached */
         226                 :            :         /* Skip any remaining whitespace and copy to beginning of string */
         227   [ #  #  #  # ]:          0 :         while (i >= 0 && STRINGLIB_ISSPACE(str[i]))
         228                 :          0 :             i--;
         229         [ #  # ]:          0 :         if (i >= 0)
         230   [ #  #  #  #  :          0 :             SPLIT_ADD(str, 0, i + 1);
                       #  # ]
         231                 :            :     }
         232                 :          0 :     FIX_PREALLOC_SIZE(list);
         233         [ #  # ]:          0 :     if (PyList_Reverse(list) < 0)
         234                 :          0 :         goto onError;
         235                 :          0 :     return list;
         236                 :            :
         237                 :          0 :   onError:
         238                 :          0 :     Py_DECREF(list);
         239                 :          0 :     return NULL;
         240                 :            : }
         241                 :            :
         242                 :            : Py_LOCAL_INLINE(PyObject *)
         243                 :         23 : 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                 :         23 :     Py_ssize_t i, j, count=0;
         249                 :         23 :     PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
         250                 :            :     PyObject *sub;
         251                 :            :
         252         [ -  + ]:         23 :     if (list == NULL)
         253                 :          0 :         return NULL;
         254                 :            :
         255                 :         23 :     i = j = str_len - 1;
         256   [ +  -  +  + ]:         46 :     while ((i >= 0) && (maxcount-- > 0)) {
         257         [ +  - ]:        273 :         for(; i >= 0; i--) {
         258         [ +  + ]:        273 :             if (str[i] == ch) {
         259   [ -  +  +  -  :         23 :                 SPLIT_ADD(str, i + 1, j + 1);
                       -  - ]
         260                 :         23 :                 j = i = i - 1;
         261                 :         23 :                 break;
         262                 :            :             }
         263                 :            :         }
         264                 :            :     }
         265                 :            : #if !STRINGLIB_MUTABLE
         266   [ -  +  -  - ]:         23 :     if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
         267                 :            :         /* ch not in str_obj, so just use str_obj as list[0] */
         268                 :          0 :         Py_INCREF(str_obj);
         269                 :          0 :         PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
         270                 :          0 :         count++;
         271                 :            :     } else
         272                 :            : #endif
         273         [ +  - ]:         23 :     if (j >= -1) {
         274   [ -  +  +  -  :         23 :         SPLIT_ADD(str, 0, j + 1);
                       -  - ]
         275                 :            :     }
         276                 :         23 :     FIX_PREALLOC_SIZE(list);
         277         [ -  + ]:         23 :     if (PyList_Reverse(list) < 0)
         278                 :          0 :         goto onError;
         279                 :         23 :     return list;
         280                 :            :
         281                 :          0 :   onError:
         282                 :          0 :     Py_DECREF(list);
         283                 :          0 :     return NULL;
         284                 :            : }
         285                 :            :
         286                 :            : Py_LOCAL_INLINE(PyObject *)
         287                 :         23 : 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                 :         23 :     Py_ssize_t j, pos, count=0;
         293                 :            :     PyObject *list, *sub;
         294                 :            :
         295         [ -  + ]:         23 :     if (sep_len == 0) {
         296                 :          0 :         PyErr_SetString(PyExc_ValueError, "empty separator");
         297                 :          0 :         return NULL;
         298                 :            :     }
         299         [ +  - ]:         23 :     else if (sep_len == 1)
         300                 :         23 :         return STRINGLIB(rsplit_char)(str_obj, str, str_len, sep[0], maxcount);
         301                 :            :
         302                 :          0 :     list = PyList_New(PREALLOC_SIZE(maxcount));
         303         [ #  # ]:          0 :     if (list == NULL)
         304                 :          0 :         return NULL;
         305                 :            :
         306                 :          0 :     j = str_len;
         307         [ #  # ]:          0 :     while (maxcount-- > 0) {
         308                 :          0 :         pos = FASTSEARCH(str, j, sep, sep_len, -1, FAST_RSEARCH);
         309         [ #  # ]:          0 :         if (pos < 0)
         310                 :          0 :             break;
         311   [ #  #  #  #  :          0 :         SPLIT_ADD(str, pos + sep_len, j);
                       #  # ]
         312                 :          0 :         j = pos;
         313                 :            :     }
         314                 :            : #if !STRINGLIB_MUTABLE
         315   [ #  #  #  # ]:          0 :     if (count == 0 && STRINGLIB_CHECK_EXACT(str_obj)) {
         316                 :            :         /* No match in str_obj, so just use it as list[0] */
         317                 :          0 :         Py_INCREF(str_obj);
         318                 :          0 :         PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
         319                 :          0 :         count++;
         320                 :            :     } else
         321                 :            : #endif
         322                 :            :     {
         323   [ #  #  #  #  :          0 :         SPLIT_ADD(str, 0, j);
                       #  # ]
         324                 :            :     }
         325                 :          0 :     FIX_PREALLOC_SIZE(list);
         326         [ #  # ]:          0 :     if (PyList_Reverse(list) < 0)
         327                 :          0 :         goto onError;
         328                 :          0 :     return list;
         329                 :            :
         330                 :          0 :   onError:
         331                 :          0 :     Py_DECREF(list);
         332                 :          0 :     return NULL;
         333                 :            : }
         334                 :            :
         335                 :            : Py_LOCAL_INLINE(PyObject *)
         336                 :        108 : 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                 :        108 :     PyObject *list = PyList_New(0);
         351                 :            :     PyObject *sub;
         352                 :            :
         353         [ -  + ]:        108 :     if (list == NULL)
         354                 :          0 :         return NULL;
         355                 :            :
         356         [ +  + ]:      25617 :     for (i = j = 0; i < str_len; ) {
         357                 :            :         Py_ssize_t eol;
         358                 :            :
         359                 :            :         /* Find a line and append it */
         360   [ +  +  +  -  :    1338689 :         while (i < str_len && !STRINGLIB_ISLINEBREAK(str[i]))
              +  +  -  -  -
                    -  -  - ]
         361                 :    1313113 :             i++;
         362                 :            :
         363                 :            :         /* Skip the line break reading CRLF as one line break */
         364                 :      25576 :         eol = i;
         365         [ +  + ]:      25576 :         if (i < str_len) {
         366   [ -  +  -  -  :      25536 :             if (str[i] == '\r' && i + 1 < str_len && str[i+1] == '\n')
                       -  - ]
         367                 :          0 :                 i += 2;
         368                 :            :             else
         369                 :      25536 :                 i++;
         370         [ +  + ]:      25536 :             if (keepends)
         371                 :         66 :                 eol = i;
         372                 :            :         }
         373                 :            : #if !STRINGLIB_MUTABLE
         374   [ +  +  +  +  :      25576 :         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         [ -  + ]:         67 :             if (PyList_Append(list, str_obj))
         377                 :          0 :                 goto onError;
         378                 :         67 :             break;
         379                 :            :         }
         380                 :            : #endif
         381   [ -  +  -  + ]:      25509 :         SPLIT_APPEND(str, j, eol);
         382                 :      25509 :         j = i;
         383                 :            :     }
         384                 :        108 :     return list;
         385                 :            :
         386                 :          0 :   onError:
         387                 :          0 :     Py_DECREF(list);
         388                 :          0 :     return NULL;
         389                 :            : }
         390                 :            :

Generated by: LCOV version 1.14