RegexMatchCache
Declared in <folly/container/RegexMatchCache.h>
class RegexMatchCache;A cache around boost::regex_match(string, regex).
For efficiency, assumes several constraints and makes several guarantees.
The data structure owns regexes but does not own strings. The lifetimes of all strings in the cache must surround their additions to the cache and their subsequent removals from the cache or destruction of the cache.
The data structure is in two parts: * A bidirectional match-cache contains all known matches. * a bidirectional string-queue contains unknown, hypothetical matches.
Cached lookup operates only over the match-cache. When the string-queue for a given regex is not empty, that regex is said to be uncoalesced. Cached lookups are not permitted for an uncoalesced regex; that regex must first be coalesced.
Addition of a string adds the string to the string-queue corresponding to all known regexes. It does not perform any regex-match operations.
Addition and coalesce of a regex performs regex-matches for that regex only. The string-queue for the given regex is removed and all elements matched against the regex, and matching strings are added to the match-cache.
Lookup must follow a pattern like this:
if (!cache.isReadyToFindMatches(regex)) { // const cache.prepareToFindMatches(regex); // non-const } auto matches = cache.findMatches(regex); // const
This is to support concurrent lookups, where the cache is protected by a shared mutex.
The data structure is exception-safe in a sense. If an exception is thrown within any non-const member function and escapes, the data structure may purge all cached regexes while leaving all strings. In most such member functions, only a memory-allocation failure would cause an exception to be thrown. But in prepareToFindMatches, the provided regex may be syntactically invalid and parsing it may throw, or it may be pathological and evaluating it over a string may throw. In any event, the resolution is to clear out all added regexes and to leave only the added strings. The reason is that this resolution is simple and likely to be correct, while any other mechanism would be complex and would be likely to have bugs.
| Name | Description |
|---|---|
ConsistencyReportMatcher | Recomputes regex/string matches for the consistency check. |
FindMatchesUnsafeResult | A non-owning view over a regex's set of matching strings. |
InspectView | A printable view of a cache's internal state. |
KeyMap | Interface mapping regex keys back to their string views. |
| Name | Description |
|---|---|
clock | The clock used for regex last-access timestamps. |
regex_key | The key type identifying a regex. |
regex_key_and_view | The composite key and view type identifying a regex. |
time_point | The time point type produced by the cache's clock. |
| Name | Description |
|---|---|
RegexMatchCache [constructor] | Constructs an empty cache with no regexes or strings. |
~RegexMatchCache [destructor] | Destroys the cache and its owned regexes. |
addRegex | Adds a regex to the cache. |
addString | Adds a string to the cache without performing any regex matches. |
clear | Removes all regexes and strings from the cache. |
consistency | Checks the cache for internal consistency, reporting any problems found. |
eraseRegex | Removes a regex from the cache. |
eraseString | Removes a string from the cache. |
findMatches | Returns a copy of the cached matches for a regex. |
findMatchesUncached | Computes the strings matching a regex without consulting the cache. |
findMatchesUnsafe | Returns the cached matches for a regex as a view over internal storage. |
getRegexList | Returns the views of all regexes currently in the cache. |
getStringList | Returns pointers to all strings currently in the cache. |
hasItemsToPurge | Returns whether any regex has not been accessed since the expiry time. |
hasRegex | Returns whether the given regex is in the cache. |
hasString | Returns whether the given string is in the cache. |
inspect | Returns a printable view of the cache's internal state. |
isReadyToFindMatches | Returns whether cached matches for the regex are ready to query. |
prepareToFindMatches | Coalesces queued strings for a regex so its matches can be queried. |
purge | Removes regexes not accessed since the expiry time. |