AppPkg/Applications/Python/Python-2.7.10/Objects/stringlib/split.h

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