Methods and apparatus for accelerating data parsing

• US 8,028,228 B2
• Filed: 10/23/2007
• Issued: 09/27/2011
• Est. Priority Date: 07/30/2001
• Status: Expired due to Fees

• Current Assignee: Richard A. Ross
• Original Assignee: Richard A. Ross
• Inventors: Ross, Richard A.
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US11/876,994
• Publication Number:
  US 20080046811A1
• Time in Patent Office: 1,435 Days
• Field of Search: 715/234, 715/243, 715/254
• 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 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 scan for the characters by the parsing circuitry, the hash value calculation by the first component, and the copying by the second component occur in same clock cycles; 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.