Directory searching method and means

• US 3,916,387 A
• Filed: 11/12/1973
• Issued: 10/28/1975
• Est. Priority Date: 04/23/1971
• Status: Expired due to Term

• Current Assignee: Luther J. Woodrum
• Original Assignee: Luther J. Woodrum
• Inventors: Woodrum, Luther J.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/415,026
• Time in Patent Office: 715 Days
• Field of Search: 340/172.5 444/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An electrical method, and machine apparatus using that method, to efficiently locate objects through an electrical directory entity contained in the machine. An electrical identifier signal for an object is applied to the machine to cause it to automatically follow a connected path in the directory entity from its source location to an object address in the directory entity. To follow the path, a part of the identifier signal is selected by the electrical state of an index part of each current inner vertex in the path to locate the next vertex in the connected path, and so on in a repetitive manner until a sink vertex containing the object address is found at the end of the connected path.

Claims

1. A system for searching among entries represented in a computer system with a search argument, comprising, means for accessing one of said entries, means for selecting from said entry a bit position of said search argument, means for sensing a bit at said bit position in said searchargument to select one among plural output paths from said entry, means for generating from said entry one address of plural possible addresses to represent a selected one of said output paths, means for testing a signal field of said entry, and means for ending said search if said signal field provides an end signal, means for retrieving a next entry with said one address if said ending means does not provide an end signal, and again actuating said prior means for each next entry, which becomes said current entry, until said ending signal is provided, whereby said location of the next entry in said path generated from said entry providing said end signal is a result sought by said search.

2. A system for seaching as defined in claim 1 in which said selecting means comprises means for addressing a bit in said search argument by indexing said bit with the value of a field in said entry.

3. A system for searching as defined in claim 1, in which said generating means generates any one of said plural possible addresses, comprising means for adding the length of said entry to the address of said entry to generate one of said plural possible addresses.

4. A system for searching as defined in claim 1, in which said generating means generates any one of said plural possible addresses, comprising means for adding a value of an offset field in said entry to the address of said entry to generate one of said plural possible addresses.

5. A system for searching among entries as defined in claim 1, in which said testing means comprises means for indexing one of two signal fields in said entry in response to the value of the bit in the search argument obtained by said sensing means, and means for generating a signal in response to the value of the signal field obtained by said indexing means, whereby one condition of saId signal provides said end signal.

6. A system for searching as defined in claim 1 in which said generating step generates any one of said plural possible addresses, comprising means for summing an integral multiple of said entry, and a value of an address field in said entry representing the address of a next entry, whereby said integral multiple is determined by said sensing means.

7. A system for tracing a search path in a directory represented in a computer system with a search argument, comprising means for accessing a next entry in directory beginning with its source, means for selecting from said entry a bit position of said search argument, means for sensing a bit at said bit position in said search-argument and testing the value of said bit to select one output path from said entry, means for generating from an edge field a location of a next entry in a search path, means for testing a flag field of said entry, and means for continuing said search if said flag field indicates an inner vertex end is a next vertex in the search path, means for retrieving said next entry with said location obtained from said generating means, and means for repeating said prior steps for each next entry until a required entry is reached.

8. A method system of searching as defined in claim 7, in which said selecting means comprises means for addressing a bit in said search argument by indexing said bit with the value of a bit-index field in said entry.

9. A system for searching as defined in claim 7, in which said generating means generates the selected location, comprising means for adding one to the index of a successor pair edge representation with said entry to generate the other successor location in response to said sensing means.

10. A system for searching as defined in claim 7, in which said generating means selects said location, further comprising the step of means for adding a value of an offset field in said entry to the address of said entry to generate the location of a successor entry.

11. Apparatus for use in a computer machine for electrically following a connected path in a memory device containing a stored electrical signal network called a directory entity having electrical signal groups interconnected into a tree structure in which are represented one or more object identifiers, said electrical signal groups forming inner connected vertices and end-of-path sinks, each inner connected vertex including an index location signal and a connecting edge signal, said index location signal locating a particular digit location in an inputted object identifier, and said connecting edge signal connecting its vertex to a successor-pair signal group, the object identifier being inputted into a search argument store as a set of digitized electrical signals to be searched for in said directory entity, said apparatus comprising a clocking circuit providing timed electrical clock pulses to gating means for controlling the transfer of electrical signals, a vertex address register for storing an address of an electrical signal group in said stored electrical signal network, beginning with an electrical signal group in a source location of said stored electrical signal network, a group register for receiving the electrical signal group addressed by said vertex address register, said signal group including at least an index location signal and a connecting edge signal, vertex gating means for connecting the stored electrical signal network to said group register to transfer the addressed electrical signal group, index gating means for locating in said search argument store with said index location signal an electrical digit signal in the set of electrical signals comprising said inputted object identifier, means for indicating an electrical state for said electrical digit signal, and adder device for receiving at least the connecting edge signal and said electrical statE for generating a next vertex location electrical signal from said group register and said indicating means, and a vertex address register being set by an output from said adder device for locating a next vertex in the stored electrical signal network.

12. Apparatus as defined in claim 11, further comprising flag-bit gating means for transferring an electrical state of at least one flag bit from said group register to signal when the end of a connected path is being reached in said stored electrical signal network for the inputted object identifier signal.

13. Apparatus as defined in claim 11, in which the connecting edge signals are of the invertible type, said apparatus further comprising vertex address gating means for transferring to said adder device the edge connecting signal in said group register and the prior content of said vertex address register for generating the address for locating a next electrical signal group in said stored electrical signal network.

14. Apparatus as defined in claim 12, said apparatus further comprising incrementing gating means connected to said adder device and actuated by the condition of said electrical state provided by said indicating means for generating the adder output provided to said vertex address register, whereby the address in said vertex address register selects a next vertex which is a right successor or a left successor according to said electrical state provided by said indicating means.

15. Apparatus as defined in claim 11, further comprising flag bit gating means for transferring one of plural sets of condition code signals in the electrical signal group in said group register in response to the condition of the electrical state in said indicating means, whereby one condition code signal applies to a left successor vertex signal group and another condition code signal applies to a right successor vertex signal group in said stored electrical signal network.

16. Apparatus for use in a computer machine for electrically following a connected path in a memory device containing a stored electrical signal network called a directory entity having electrical cells inter-connected into a tree structure in which are represented one or more object identifiers, said electrical cells forming inner and sink vertices, each inner vertex including an index field and an edge field and a flag field, said index field being used for locating a particular digit in an inputted object identifier, and said edge field being used in addressing a next vertex in a connected path in said directory entity, the object identifier being inputted into a search argument store as a set of digitized electrical signals to be searched for in said directory entity, said apparatus comprising a clocking circuit providing a plurality of timed electrical clock pulses for controlling the transfer of electrical signals in said apparatus, a cell addressing register for storing an address of a vertex in said directory entity, beginning with a source vertex in an initial cell in said directory entity, a cell register for receiving a cell addressed by said cell addressing register, a particular clock pulse gate transferring the electrical signal state of the cell from the directory entity to said cell register, a search argument digit store, another clock pulse gate transferring a digit electrical state at an index location in said search argument store determined by the index field in said cell to said search argument digit store, AND gate circuits receiving the electrical signals from respective parts of the flag field in said cell register and also receiving complementary outputs of said search argument digit store to select a part of said flag field by activating part of said AND gate circuits, a condition code register, a further clock pulse gate transferring the part of the flag field outputted by said AND gate circuits to said condition code register, an adder device, othEr clock pulse gates transferring to said adder device the edge field in said cell register and the electrical state in said cell address register, and still other clock pulses transferring output signals from said adder device into said cell address register for accessing any next cell in the connected path in the directory entity, whereby a predetermined electrical state in the condition code register indicates that a sink vertex is in the cell register.

17. Apparatus as defined in claim 16, in which a latch circuit comprises said search argument digit store, whereby binary electrical signal states provide the respective digit positions in said search argument store.