# US 8,572,106 B1 · Memory management in a token stitcher for a content search system having pipelined engines > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,572,106 B1 - Document ID: US8572106B1 - Status: Granted - Kind: B1 - Application number: 12/946,440 - Filed: 2010-11-15 - Granted: 2013-10-29 - Earliest claimed: 2010-07-16 - Assignees: NetLogic Microsystems, Inc. - Applicants: Cristian Estan - Inventors: Cristian Estan - Web page: https://patentgrep.com/patent/US8572106B1 ## CPC - G06F 16/90344: {by using string matching techniques} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A content search system includes multiple pipelined search engines that implement different portions of a regular expression search operation. For some embodiments, the search pipeline includes a DFA engine, an NFA engine, and a token stitcher that combines partial match results generated by the DFA and NFA engines. The token stitcher can be configured to implement unbounded sub-expressions without utilizing resources of the DFA or NFA engines. The token stitcher may comprise a flag bank for storing a number of flags. Each flag may identify a sub-expression that matches the input string. The flag bank may be configured to discard one or more flags upon satisfaction of a predetermined condition for purposes of recapturing hardware resources to provide a certain level of performance. ## Claims ### Claim 1 A token stitcher for determining whether an input string of characters matches a regular expression comprising a number of sub-expressions, the token stitcher comprising: a flag bank storing a number of flags, where each flag identifies one or more of the sub-expressions that match the input string; and a token stitcher engine configured to implement an unbounded sub-expression without utilizing resources of a deterministic finite state automaton (DFA) engine or a non-deterministic finite state automaton (NFA) engine and to identify one or lore programs stored in a program memory that are associated with a new token received by the token stitcher, wherein a particular program in the program memory is configured to indicate a match when a particular set of flags in the flag bank are asserted, and wherein the flag bank is configured to discard one or more flags upon satisfaction of a predetermined condition and wherein the token stitcher is implemented by at least one processor-based computing device. ### Claim 2 (depends on 1) The token stitcher of claim 1, wherein the predetermined condition is whether the token stitcher has examined a particular number of input characters of the input string since a sub-expression matched the input string. ### Claim 3 (depends on 1) The token stitcher of claim 1, wherein the predetermined condition is whether a particular number of flags have been stored in the flag bank. ### Claim 4 (depends on 1) The token stitcher of claim 1, wherein the predetermined condition is whether the token stitcher has received an instruction to save a state of the token stitcher. ### Claim 5 (depends on 1) The token stitcher of claim 1, wherein the predetermined condition is whether a current character being examined in the input string is a new line character. ### Claim 6 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, one flag associated with a sub-expression that was matched at an offset which is further from a current offset being examined in the input string than any other sub-expression. ### Claim 7 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, all flags associated with sub-expressions that were matched at an offset which is further from a current offset being examined in the input string than any other sub-expression. ### Claim 8 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, any flag that is associated with a partial match whose relevance in evaluating a match condition has been rendered moot by another flag stored in the flag bank. ### Claim 9 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to discard flags associated with sub-expressions that cannot result in a match across multiple lines when a current character in input string being examined is a new line character. ### Claim 10 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to discard, upon satisfaction of the predetermined condition, any number of flags that are each associated with an offset that is more than a predetermined distance away from a current offset being examined. ### Claim 11 (depends on 1) The token stitcher of claim 1, wherein the flag bank is configured to store an offset associated with a first occurrence of a sub-expression, but not any other occurrence of the sub-expression, for a flag stored in the flag bank. ### Claim 12 An apparatus for determining whether an input string of characters matches a regular expression comprising a number of sub-expressions, comprising: means for storing a record of which sub-expressions match the input string; and means for implementing an unbounded sub-expression without utilizing resources of a deterministic finite state automaton (DFA) engine or a non-deterministic finite state automaton (NFA) engine and for identifying one or more programs responsible for processing a sub-expression that matches the input string, and wherein the means for storing is configured to discard one or more records upon satisfaction of a predetermined condition and wherein the means for implementing the unbounded sub-expression is implemented by at least one processor-based computing device. ### Claim 13 (depends on 12) The apparatus of claim 12, wherein the predetermined condition is whether a particular number of input characters of the input string has been examined since a sub-expression matched the input string. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein the predetermined condition is whether a particular number of records have been stored by the means for storing. ### Claim 15 (depends on 12) The apparatus of claim 12, wherein the predetermined condition is whether an instruction to save a state of the apparatus has been received. ### Claim 16 (depends on 12) The apparatus of claim 12, wherein the predetermined condition is whether a current character being examined in the input string is a new line character. ### Claim 17 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, one record associated with a sub-expression that was matched at an offset which is further from a current offset being examined in the input string than any other sub-expression. ### Claim 18 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, all records associated with sub-expressions that were matched at an offset which is further from a current offset being examined in the input string than any other sub-expression. ### Claim 19 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, any record that is associated with a partial match whose relevance in evaluating a match condition has been rendered moot by another record stored in the means for storing. ### Claim 20 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to discard records associated with sub-expressions that cannot result in a match across multiple lines when a current character in the input string being examined is a new line character. ### Claim 21 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to discard, upon satisfaction of the predetermined condition, any number of records that are each associated with an offset that is more than a predetermined distance away from a current offset being examined. ### Claim 22 (depends on 12) The apparatus of claim 12, wherein the means for storing is configured to store an offset associated with a first occurrence of a sub-expression, but not any other occurrence of the sub-expression, for a record stored in the means for storing.