diff options
| -rw-r--r-- | embed.fnc | 1 | ||||
| -rw-r--r-- | embed.h | 1 | ||||
| -rw-r--r-- | proto.h | 6 | ||||
| -rw-r--r-- | regcomp.c | 42 |
4 files changed, 50 insertions, 0 deletions
@@ -1372,6 +1372,7 @@ EiMR |SV* |invlist_clone |NN SV* const invlist EiMR |UV* |get_invlist_iter_addr |NN SV* invlist EiM |void |invlist_iterinit|NN SV* invlist EsMR |bool |invlist_iternext|NN SV* invlist|NN UV* start|NN UV* end +EsMR |IV |invlist_search |NN SV* const invlist|const UV cp #endif #if defined(PERL_IN_REGCOMP_C) || defined(PERL_IN_UTF8_C) EXpM |void |_invlist_intersection |NN SV* const a|NN SV* const b|NN SV** i @@ -915,6 +915,7 @@ #define invlist_iternext(a,b,c) S_invlist_iternext(aTHX_ a,b,c) #define invlist_len(a) S_invlist_len(aTHX_ a) #define invlist_max(a) S_invlist_max(aTHX_ a) +#define invlist_search(a,b) S_invlist_search(aTHX_ a,b) #define invlist_set_len(a,b) S_invlist_set_len(aTHX_ a,b) #define invlist_trim(a) S_invlist_trim(aTHX_ a) #define join_exact(a,b,c,d,e,f) S_join_exact(aTHX_ a,b,c,d,e,f) @@ -6355,6 +6355,12 @@ PERL_STATIC_INLINE UV S_invlist_max(pTHX_ SV* const invlist) #define PERL_ARGS_ASSERT_INVLIST_MAX \ assert(invlist) +STATIC IV S_invlist_search(pTHX_ SV* const invlist, const UV cp) + __attribute__warn_unused_result__ + __attribute__nonnull__(pTHX_1); +#define PERL_ARGS_ASSERT_INVLIST_SEARCH \ + assert(invlist) + PERL_STATIC_INLINE void S_invlist_set_len(pTHX_ SV* const invlist, const UV len) __attribute__nonnull__(pTHX_1); #define PERL_ARGS_ASSERT_INVLIST_SET_LEN \ @@ -6142,6 +6142,48 @@ Perl__append_range_to_invlist(pTHX_ SV* const invlist, const UV start, const UV } } +STATIC IV +S_invlist_search(pTHX_ SV* const invlist, const UV cp) +{ + /* Searches the inversion list for the entry that contains the input code + * point <cp>. If <cp> is not in the list, -1 is returned. Otherwise, the + * return value is the index into the list's array of the range that + * contains <cp> */ + + IV low = 0; + IV high = invlist_len(invlist); + const UV * const array = invlist_array(invlist); + + PERL_ARGS_ASSERT_INVLIST_SEARCH; + + /* If list is empty or the code point is before the first element, return + * failure. */ + if (high == 0 || cp < array[0]) { + return -1; + } + + /* Binary search. What we are looking for is <i> such that + * array[i] <= cp < array[i+1] + * The loop below converges on the i+1. */ + while (low < high) { + IV mid = (low + high) / 2; + if (array[mid] <= cp) { + low = mid + 1; + + /* We could do this extra test to exit the loop early. + if (cp < array[low]) { + return mid; + } + */ + } + else { /* cp < array[mid] */ + high = mid; + } + } + + return high - 1; +} + void Perl__invlist_union(pTHX_ SV* const a, SV* const b, SV** output) { |