Tree search unit

• US 20030050925A1
• Filed: 08/20/2002
• Published: 03/13/2003
• Est. Priority Date: 08/21/2001
• Status: Abandoned Application

• Current Assignee: Infocyclone Limited
• Original Assignee: Infocyclone Limited
• Inventors: Levy, Eliezer, Moskovich, Reuven
• Application Number:
  US10/224,713
• Publication Number:
  US 20030050925A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/322 Trees

Abstract

A hardware unit for searching through a tree. The hardware unit includes a memory which stores a plurality of records, which describe the tree, an input interface adapted to receive an input string to be searched for in the tree and a hardware controller, which does not store an internal state, other than an optional position in the input string, adapted to determine a pointer related to the input string, if such a pointer exists.

Claims

1. A hardware unit for searching through a tree, comprising:

a memory which stores a plurality of records, which describe the tree;

an input interface adapted to receive an input string to be searched for in the tree; and

a hardware controller, which does not store an internal state, other than an optional position in the input string, adapted to determine a pointer related to the input string, if such a pointer exists.

2. A hardware unit according to claim 1, wherein the controller does not receive multi-bit commands.

3. A hardware unit according to claim 1, wherein the controller does not receive memory-stored commands.

4. A hardware unit according to claim 1, wherein the plurality of records stored in the memory have the same length and field division.

5. A hardware unit according to claim 4, wherein the records include up to two pointer fields pointing to other records.

6. A hardware unit according to claim 4, wherein the records include a child pointer field and a next record field, pointing to a record having a common parent with the record including the next record field.

7. A hardware unit according to claim 4, wherein the records include up to three pointer fields to other records or to external points.

8. A hardware unit according to claim 1, wherein the controller determines a pointer corresponding to a string represented by the tree, which is identical to the input string.

9. A hardware unit according to claim 1, wherein the controller determines a pointer corresponding to a largest sub-string of the input string that has a corresponding external pointer.

10. A hardware unit according to claim 1, wherein except for a first record of the tree the controller fetches records from the memory using addresses contained in previously fetched records.

11. A hardware unit according to claim 1, wherein the controller comprises a multiplexer which provides addresses of records to be fetched from the tree and wherein the multiplexer has not more than four different input lines from which the addresses are selected.