Methods and apparatus for accelerating data parsing

• US 7,305,615 B2
• Filed: 07/03/2002
• Issued: 12/04/2007
• Est. Priority Date: 07/30/2001
• Status: Expired due to Fees

• Current Assignee: Richard A. Ross, Telemedia Technologies Incorporated
• Original Assignee: Gigalogix, Inc.
• Inventors: Ross, Richard
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Stork; Kyle R
• Application Number:
  US10/189,952
• Publication Number:
  US 20030023633A1
• Time in Patent Office: 1,980 Days
• Field of Search: 715/513, 715/517, 715/523, 715/530
• 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. XML accelerator parsing circuitry connected to a memory, the XML accelerator parsing circuitry comprising:

white space handling subcircuitry configured to remove white space in an XML data string provided to the XML accelerator parsing circuitry;

hash calculation subcircuitry configured to calculate a hash value associated with the XML data string; and

duplication subcircuitry configured to copy the XML data string to permanent memory;

wherein the XML data string is simultaneously input to the white space handling subcircuitry, the hash calculation subcircuitry, and the duplication subcircuitry with a single access to each character in the XML data string,

wherein the white space handling subcircuitry, the hash calculation subcircuitry, and the duplication subcircuitry simultaneously operate on a character in the XML data string.

2. 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, a second component, and a third component of the parsing circuitry with a single access to the character,

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

wherein the first, second, and third components simultaneously perform the hash value calculation, the copying, and the white space handling while the scan of the characters occurs; and

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

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

4. The integrated circuit of claim 2, wherein the parsing circuitry is configured to perform white space handling using a single primitive operation.

5. The integrated circuit of claim 2, 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.

6. The integrated circuit of claim 5, wherein an entry colTesponding 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.

7. The integrated circuit of claim 6, wherein the length of the first preallocated block of memory is set to correspond to the length of the XML element tag after the XML element tag is copied to the first preallocated block of memory.

8. The integrated circuit of claim 5, returning the first preallocated block of memory if a bucket associated with the hash value contains an entry corresponding to the XML element tag.

9. The integrated circuit of claim 5, returning a hash bucket identifier associated with the hash bucket containing the entry corresponding to the XML element tag.

10. The integrated circuit of claim 2, wherein performing white space handling comprises converting a line feed character followed by a carriage return character into a carriage return character.

11. The integrated circuit of claim 10, wherein performing white space handling further comprises converting a line feed character not followed by a carriage return into a carriage return character.

12. The integrated circuit of claim 2, wherein the integrated circuit is a data parsing accelerator.

13. The integrated circuit of claim 2, wherein the integrated circuit is a processor.

14. A computer system, comprising the integrated circuit of claim 2.

15. A server, comprising the integrated circuit of claim 2.

16. A network appliance, comprising the integrated circuit of claim 2.

17. An accelerator card, comprising the integrated circuit of claim 2.

18. A handheld device, comprising the integrated circuit of claim 2.