aboutsummaryrefslogtreecommitdiff
path: root/lib/libc/regex/regcomp.c
Commit message (Collapse)AuthorAgeFilesLines
...
* Per Regents of the University of Calfornia letter, remove advertisingWarner Losh2007-01-091-4/+0
| | | | | | | | | clause. # If I've done so improperly on a file, please let me know. Notes: svn path=/head/; revision=165903
* Directly include <runetype.h> for _CurrentRuneLocale, <_ctype.h> doesn'tStefan Farfeleder2004-10-031-0/+1
| | | | | | | include it in all cases. Notes: svn path=/head/; revision=136091
* Fix two problems with REG_ICASE that were introduced with the addition ofTim J. Robbins2004-09-051-13/+10
| | | | | | | | | | | | | | multibyte character support: - In CHadd(), avoid writing past the end of the character set bitmap when the opposite-case counterpart of wide characters with values less than NC have values greater than or equal to NC. - In CHaddtype(), fix a braino that caused alphabetic characters to be added to all character classes! (but only with REG_ICASE) PR: 71367 Notes: svn path=/head/; revision=134802
* Make regular expression matching aware of multibyte characters. The generalTim J. Robbins2004-07-121-261/+255
| | | | | | | | | | | | | | | | | | | | idea is that we perform multibyte->wide character conversion while parsing and compiling, then convert byte sequences to wide characters when they're needed for comparison and stepping through the string during execution. As with tr(1), the main complication is to efficiently represent sets of characters in bracket expressions. The old bitmap representation is replaced by a bitmap for the first 256 characters combined with a vector of individual wide characters, a vector of character ranges (for [A-Z] etc.), and a vector of character classes (for [[:alpha:]] etc.). One other point of interest is that although the Boyer-Moore algorithm had to be disabled in the general multibyte case, it is still enabled for UTF-8 because of its self-synchronizing nature. This greatly speeds up matching by reducing the number of multibyte conversions that need to be done. Notes: svn path=/head/; revision=132019
* Remove incomplete support for multi-character collating elements. RemoveTim J. Robbins2004-07-111-245/+8
| | | | | | | unused character category calculations. Notes: svn path=/head/; revision=131973
* Eliminate 61 warnings emitted at WARNS=2 (leaving 53 to go).Jacques Vidrine2003-02-161-2/+2
| | | | | | | | | | Only warnings that could be fixed without changing the generated object code and without restructuring the source code have been handled. Reviewed by: /sbin/md5 Notes: svn path=/head/; revision=111010
* Add restrict type-qualifier.Mike Barcroft2002-10-021-2/+2
| | | | Notes: svn path=/head/; revision=104358
* Replace various spelling with FALLTHROUGH which is lint()ablePhilippe Charnier2002-08-251-1/+1
| | | | Notes: svn path=/head/; revision=102411
* Fix the style of the SCM ID's.David E. O'Brien2002-03-221-2/+2
| | | | | | | I believe have made all of libc .c's as consistent as possible. Notes: svn path=/head/; revision=92986
* Remove __P() usage.David E. O'Brien2002-03-211-43/+43
| | | | Notes: svn path=/head/; revision=92905
* Remove 'register' keyword.David E. O'Brien2002-03-211-203/+203
| | | | Notes: svn path=/head/; revision=92889
* The algorithm that computes the tables used in the BM search algorithm sometimesDaniel C. Sobral2001-11-091-1/+2
| | | | | | | | | | | | | access an array beyond it's length. This only happens in the last iteration of a loop, and the value fetched is not used then, so the bug is a relatively innocent one. Fix this by not fetching any value on the last iteration of said loop. Submitted by: MKI <mki@mozone.net> MFC after: 1 week Notes: svn path=/head/; revision=86208
* altoffset() always returned whenever it recursed, because at the endDaniel C. Sobral2000-07-091-0/+4
| | | | | | | | | | | | | | | | | of the processing of the recursion, "scan" would be pointing to O_CH (or O_QUEST), which would then be interpreted as being the end character for altoffset(). We avoid this by properly increasing scan before leaving the switch. Without this, something like (a?b?)?cc would result in a g->moffset of 1 instead of 2. I added a case to the soon-to-be-imported regex(3) test code to catch this error. Notes: svn path=/head/; revision=62855
* Add some casts here and there.Daniel C. Sobral2000-07-091-3/+3
| | | | Notes: svn path=/head/; revision=62848
* Do not free NULL pointers.Daniel C. Sobral2000-07-071-1/+1
| | | | Notes: svn path=/head/; revision=62755
* Deal with the signed/unsigned chars issue in a more proper manner. WeDaniel C. Sobral2000-07-071-3/+5
| | | | | | | | | | | | use a CHAR_MIN-based array, like elsewhere in the code. Remove a number of unused variables (some due to the above change, one that was left after a number of optimizing steps through the source). Brucified by: bde Notes: svn path=/head/; revision=62754
* I hate signed chars.^W^W^W^W^WCast to unsigned char before using signedDaniel C. Sobral2000-07-061-1/+1
| | | | | | | chars as array indices. Notes: svn path=/head/; revision=62674
* Correct comment to work with test code.Daniel C. Sobral2000-07-061-2/+2
| | | | | | | Prevent out of bounds array access in some specific cases. Notes: svn path=/head/; revision=62673
* Use UCHAR_MAX consistently.Daniel C. Sobral2000-07-061-1/+1
| | | | Notes: svn path=/head/; revision=62670
* Enhance the optimization provided by pre-matching. Fix style bugs withDaniel C. Sobral2000-07-021-5/+164
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | previous commits. At the time we search the pattern for the "must" string, we now compute the longest offset from the beginning of the pattern at which the must string might be found. If that offset is found to be infinite (through use of "+" or "*"), we set it to -1 to disable the heuristics applied later. After we are done with pre-matching, we use that offset and the point in the text at which the must string was found to compute the earliest point at which the pattern might be found. Special care should be taken here. The variable "start" is passed to the automata-processing functions fast() and slow() to indicate the point in the text at which they should start working from. The real beginning of the text is passed in a struct match variable m, which is used to check for anchors. That variable, though, is initialized with "start", so we must not adjust "start" before "m" is properly initialized. Simple tests showed a speed increase from 100% to 400%, but they were biased in that regexec() was called for the whole file instead of line by line, and parenthized subexpressions were not searched for. This change adds a single integer to the size of the "guts" structure, and does not change the ABI. Further improvements possible: Since the speed increase observed here is so huge, one intuitive optimization would be to introduce a bias in the function that computes the "must" string so as to prefer a smaller string with a finite offset over a larger one with an infinite offset. Tests have shown this to be a bad idea, though, as the cost of false pre-matches far outweights the benefits of a must offset, even in biased situations. A number of other improvements suggest themselves, though: * identify the cases where the pattern is identical to the must string, and avoid entering fast() and slow() in these cases. * compute the maximum offset from the must string to the end of the pattern, and use that to set the point at which fast() and slow() should give up trying to find a match, and return then return to pre-matching. * return all the way to pre-matching if a "match" was found and later invalidated by back reference processing. Since back references are evil and should be avoided anyway, this is of little use. Notes: svn path=/head/; revision=62391
* Initialize variables used by the Boyer-Moore algorithm.Daniel C. Sobral2000-06-291-0/+2
| | | | | | | | | | This should fix core dumps when the must pattern is of length three or less. Bug found by: knu Notes: svn path=/head/; revision=62263
* Add Boyler-Moore algorithm to pre-matching test.Daniel C. Sobral2000-06-291-0/+144
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The BM algorithm works by scanning the pattern from right to left, and jumping as many characters as viable based on the text's mismatched character and the pattern's already matched suffix. This typically enable us to test only a fraction of the text's characters, but has a worse performance than the straight-forward method for small patterns. Because of this, the BM algorithm will only be used if the pattern size is at least 4 characters. Notice that this pre-matching is done on the largest substring of the regular expression that _must_ be present on the text for a succesful match to be possible at all. For instance, "(xyzzy|grues)" will yield a null "must" substring, and, therefore, not benefit from the BM algorithm at all. Because of the lack of intelligence of the algorithm that finds the "must" string, things like "charjump|matchjump" will also yield a null string. To optimize that, "(char|match)jump" should be used. The setup time (at regcomp()) for the BM algorithm will most likely outweight any benefits for one-time matches. Given the slow regex(3) we have, this is unlikely to be even perceptible, though. The size of a regex_t structure is increased by 2*sizeof(char*) + 256*sizeof(int) + strlen(must)*sizeof(int). This is all inside the regex_t's "guts", which is allocated dynamically by regcomp(). If allocation of either of the two tables fail, the other one is freed. In this case, the straight-forward algorithm is used for pre-matching. Tests exercising the code path affected have shown a speed increase of 50% for "must" strings of length four or five. API and ABI remain unchanged by this commit. The patch submitted on the PR was not used, as it was non-functional. PR: 14342 Notes: svn path=/head/; revision=62232
* unsigned char cleanupAndrey A. Chernov1999-07-261-17/+17
| | | | | | | | | | fix wrong index from p_simp_re() PR: 8790 Submitted by: Alexander Viro <viro@math.psu.edu> (partially) Notes: svn path=/head/; revision=49094
* Replace memory leaking instances of realloc with non-leaking reallocf.Warner Losh1998-09-161-4/+4
| | | | | | | | | | | | | | In some cases replace if (a == null) a = malloc(x); else a = realloc(a, x); with simple reallocf(a, x). Per ANSI-C, this is guaranteed to be the same thing. I've been running these on my system here w/o ill effects for some time. However, the CTM-express is at part 6 of 34 for the CAM changes, so I've not been able to do a build world with the CAM in the tree with these changes. Shouldn't impact anything, but... Notes: svn path=/head/; revision=39327
* Speedup in case locale not usedAndrey A. Chernov1997-04-041-5/+11
| | | | Notes: svn path=/head/; revision=24637
* collate_range_cmp -> __collate_range_cmpAndrey A. Chernov1996-10-311-4/+5
| | | | Notes: svn path=/head/; revision=19277
* Convert to newly aded collate compare functionAndrey A. Chernov1996-08-121-4/+4
| | | | Notes: svn path=/head/; revision=17552
* Remove static collcmp, use new internal function nowAndrey A. Chernov1996-08-121-37/+4
| | | | Notes: svn path=/head/; revision=17532
* Use collate data for national alpha character ranges like [a-z]Andrey A. Chernov1996-08-111-4/+45
| | | | Notes: svn path=/head/; revision=17514
* Short value is better for hash due to easy overflow in 8bit charactersAndrey A. Chernov1996-08-111-1/+1
| | | | Notes: svn path=/head/; revision=17509
* Use locale for character classes instead of hardcoded valuesAndrey A. Chernov1996-08-111-6/+66
| | | | | | | Misc 8bit cleanup Notes: svn path=/head/; revision=17508
* General -Wall warning cleanup, part I.Jordan K. Hubbard1996-07-121-28/+32
| | | | | | | Submitted-By: Kent Vander Velden <graphix@iastate.edu> Notes: svn path=/head/; revision=17141
* 8bit clean fixesAndrey A. Chernov1996-03-251-3/+5
| | | | Notes: svn path=/head/; revision=14815
* More cleanup.Poul-Henning Kamp1995-10-221-2/+0
| | | | | | | Uhm, I also forgot: I took "EXTRA_SANITY" out of malloc.c Notes: svn path=/head/; revision=11664
* BSD 4.4 Lite Lib SourcesRodney W. Grimes1994-05-271-0/+1698
Notes: svn path=/cvs2svn/branches/unlabeled-1.1.1/; revision=1573
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-04 14:34:11 +0000