Methods and Apparatus For Accelerating Data Parsing

• US 20080046811A1
• Filed: 10/23/2007
• Published: 02/21/2008
• Est. Priority Date: 07/30/2001
• Status: Active Grant

• Current Assignee: Richard A. Ross
• Original Assignee: Gigalogix, Inc.
• Inventors: Ross, Richard
• Granted Patent: US 8,028,228 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting

Abstract

According to the present invention, methods and apparatus are provided for improving the efficiency of data parsing. Data parsing can be applied to a variety of different types of data in various computer systems and appliances. Some of the methods and apparatus provided include techniques for scanning, verifying, calculating hash values, copying, and white space handling.

Claims

1. An integrated circuit for parsing Extensible Markup Language (XML) data, the integrated circuit comprising:

memory;

parsing circuitry configured to parse an element tag provided to the integrated circuit, wherein the parsing circuitry scans for characters associated with the element tag,

wherein each of the characters is simultaneously input into a first component and a second component of the parsing circuitry with a single access to the character,

wherein the first component calculates a hash value for the input character, and the second component copies the input character to a first preallocated block of memory,

wherein the first and second components simultaneously perform the hash value calculation and the copying while the scan of the characters occurs; and

an interface for allowing communication between the parsing circuitry and the memory.

2. The circuit of claim 1, wherein the scans for the characters comprise getting the characters, determining the character type, and calculating a state with the single access to each character.

3. The circuit of claim 1, wherein the parsing circuitry is further configured to determine whether a bucket associated with the hash value contains an entry corresponding to an XML element tag.

4. The circuit of claim 3, wherein an entry corresponding to the XML element tag is added if it is determined that no bucket associated with the hash value contains an entry corresponding to the XML element tag.

5. The circuit of claim 4, wherein a length of a first preallocated block of memory is set to correspond to a length of the XML element tag after the XML element tag is copied to the first preallocated block of memory.

6. The circuit of claim 3, wherein the parsing circuitry is further configured to return the first preallocated block of memory if a bucket associated with the hash value contains an entry corresponding to the XML element tag.

7. The circuit of claim 3, wherein the parsing circuitry is further configured to return a hash bucket identifier associated with the hash bucket containing the entry corresponding to the XML element tag.