1. A hashed lookup table structure comprising:
hardware gates or a processor for executing a lookup operation;
a memory for storing data used by the lookup operation;
input means for receiving an input key for the lookup operation;
key hashing means, receiving the input key, for generating a hashed key that is a compressed hash of the input key;
stride table means for locating a final-level entry using strides of bits from the hashed key to index stride tables arranged in multiple levels;
a first bucket pointer stored in the final-level entry;
a first discriminant bit-position locator stored in the final-level entry;
a plurality of bucket tables, each bucket table for storing a plurality of key entries, each key entry for storing a stored key and a result pointer;
bucket locator means, receiving the first bucket pointer from the final-level entry, for locating a selected bucket table in the plurality of bucket tables using the first bucket pointer;
key-select-bit locator means for locating and reading a key-select bit in the input key located at a bit-position within the input key indicated by the first discriminant bit-position locator stored in the final-level entry;
bucket index means for selecting a selected key entry in the selected bucket table pointed to by the first bucket pointer, the bucket index means reading a state of the key-select bit read from the input key by the key-select-bit locator means to determine which key entry in the selected bucket table to select as the selected key entry; and
verify means for comparing a selected stored key in the selected key entry to the input key, and for outputting a lookup result generated from a selected result pointer associated with the selected stored key when a match occurs, whereby the selected stored key is indexed using the key-select bit within the selected bucket table pointed to by the final-level entry of the stride tables.
2. The hashed lookup table structure of claim 1 further comprising:
a second bucket pointer stored in the final-level entry;
a second discriminant bit-position locator stored in the final-level entry;
second bucket locator means, receiving the second bucket pointer from the final-level entry, for locating a selected second bucket table in the plurality of bucket tables using the second bucket pointer;
second key-select-bit locator means for locating and reading a second key-select bit in the input key located at a second bit-position within the input key indicated by the second discriminant bit-position locator stored in the final-level entry;
second bucket index means for selecting a selected second key entry in the selected second bucket table pointed to by the second bucket pointer, the second bucket index means reading a state of the second key-select bit read from the input key by the second key-select-bit locator means to determine which key entry in the selected second bucket table to select as the selected second key entry; and
second verify means for comparing a selected second stored key in the selected second key entry to the input key, and for outputting a lookup result generated from a selected second result pointer associated with the selected second stored key when a match occurs,
whereby two bucket tables are pointed to by the final-level entry.
3. The hashed lookup table structure of claim 2 wherein the stride table means further comprises:
hash table means for storing a plurality of the final-level entries in a single table that is indexed by a subset of S0 bits from the hashed key;
and wherein the key hashing means further comprises a seed value, the seed value being input to the key hashing means to alter generation of the hashed key from the input key,
whereby seeded input keys generate hashed keys.
4. The hashed lookup table structure of claim 1 wherein the first discriminant bit-position locator stored in the final-level entry identifies a pair of bit-positions within the input key;
wherein the key-select-bit locator means locates and reads a pair of the key-select bits in the input key;
wherein the bucket index means selects the selected key entry in the selected bucket table by reading states of both bits in the pair of the key-select bit,
whereby the pair of the key-select bits selects the selected key entry in the selected bucket table.
5. The hashed lookup table structure of claim 4 wherein the stride table means further comprises:
stride means for extracting multi-bit strides from the hashed key, each of the multi-bit strides for selecting a selected entry from stride tables at a level of tables corresponding to a location of the multi-bit stride within the hashed key;
compress means, receiving a multi-bit stride for a level L in the level of tables, and receiving a function indicator stored in a prior selected entry in a stride table in a prior level L\u22121 in the level of tables, for compressing the multi-bit stride to form a compressed index having fewer bits than the multi-bit stride, wherein the function indicator indicates a type of operation to combine bits within the multi-bit stride;
locator means, receiving a table pointer from the prior selected entry and receiving the compressed index generated by the compress means, wherein a selected stride table is selected by the table pointer, for locating a selected entry within the selected stride table, the selected entry being selected by the compressed index; and
next-level pointer means for reading a next-table pointer from the selected entry to locate a stride table for a next level L+1 in the level of tables;
wherein when the selected entry is in a final level in the level of tables, the selected entry is a final-level entry.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
What is claimed is:
1. An adapter for supplying electrical energy from a first power cable by way of a power-in plug and mating adapter port array to a first electrical distribution terminal block and from the adapter by way of a power-out port array, power-out plug, and power jumper to a second electrical distribution block, comprising an insulating housing having a plurality of contact receiving cavities, a plurality of electrical contacts, each disposed within a corresponding cavity and each having at least three radially extending electrically conductive arms terminating near respective ports within the housing, one arm of each contact extending to the multiconductor power-in plug receiving port array, another arm of each contact extending to the multiconductor power out-plug receiving port array, and a further arm of each contact adapted to electrically connect to a corresponding terminal of the first electrical distribution block.
2. The adapter of claim 1, wherein two of said conductive arms comprise relatively flat coplanar elongated blades.
3. The adapter of claim 1, wherein the first electrical distribution terminal block includes a plurality of interleaved insulating wafers and conductive terminals, each terminal including an elongated prong for electrical connection to one of an adapter contact and an electrical receptacle terminal.
4. The adapter of claim 1, further including a receptacle terminal accepting port array wherein each electrical contact includes a fourth radially extending arm, the fourth arm of each contact extending to the receptacle terminal accepting port array.
5. The adapter of claim 4, wherein three of said conductive arms comprise relatively flat coplanar elongated blades and the fourth of said conductive arms comprises a resilient clip for receiving a corresponding terminal block prong.
6. The adapter of claim 5, wherein the three elongated blades are generally equiangularly located and the fourth of said conductive arms extends radially generally bisecting the angle between two elongated blades.
7. The adapter of claim 1, wherein there are exactly three generally equiangularly located electrically conductive arms.
8. The adapter of claim 1, wherein the insulating housing comprises first and second matable housing portions, each portion having two sets of alignable recesses, each recess receiving a portion of one electrically conductive arm, the first housing portion having a set of centrally located cavities each aligned with corresponding first housing portion recesses to receive a third conductive arm of a corresponding contact whereby, one arm of each contact may be introduced into each centrally located cavity with two other arms seated in corresponding recesses, and the second housing portion mated to the first housing portion capturing the contacts therein.
9. The adapter of claim 8, wherein the first housing portion further includes a plurality of parallel alignment pins extending therefrom in a direction generally opposite the centrally located cavities, and the second housing portion includes corresponding pin receiving apertures, the pins and apertures interengaging when the housing portions are mated to align and secure the housing portions together.
10. The adapter of claim 8, wherein the first and second housing portions each include a centrally disposed screw aperture for securing the housing portions together and securing the adapter to an electrical distribution terminal block.
11. The adapter of claim 8, wherein the power-in and power-out plugs each include a centrally located retaining screw aperture and one of the housing portions includes corresponding retaining screw receptacles located intermediate an adjacent pair of recesses in each set of recesses.
12. The adapter of claim 8, wherein the sets of alignable recesses, when joined, form the port arrays.
13. The adapter of claim 8, further comprising a set of centrally located cavities in the second housing portion determining a receptacle terminal accepting port array, each electrical contact including a fourth radially extending arm, the fourth arm of each contact extending to a corresponding port of the receptacle terminal accepting port array.
14. The adapter of claim 13, wherein three of said conductive arms comprise relatively flat coplanar elongated blades and the fourth of said conductive arms comprises a resilient clip for receiving a corresponding terminal block prong.
15. The adapter of claim 14, wherein the three elongated blades are generally equiangularly located and the fourth of said conductive arms extends radially generally bisecting the angle between two elongated blades.
16. The adapter of claim 15, further comprising a retaining screw receptacle located centrally in the second housing portion for receiving a receptacle assembly retaining screw.
17. An adapter for distributing electrical energy, comprising an insulating housing and a plurality of electrical contacts, each contact having at least three radially extending electrically conductive arms terminating near respective ports within the housing, the insulating housing comprising first and second matable housing portions, each portion having two sets of alignable recesses, each recess receiving a portion of one electrically conductive arm, the first housing portion having a set of centrally located cavities each aligned with corresponding first housing portion recesses to receive a third conductive arm of a corresponding contact whereby, one arm of each contact may be introduced into each cavity with two other arms seated in corresponding recesses, and the second housing portion mated to the first housing portion capturing the contacts therein.
18. The adapter of claim 17, wherein the housing further includes a receptacle terminal accepting port array and each electrical contact includes a fourth radially extending arm, the fourth arm of each contact extending to the receptacle terminal accepting port array.
19. The adapter of claim 18, wherein three of said conductive arms comprise relatively flat coplanar elongated blades and the fourth of said conductive arms comprises a resilient clip.
20. The adapter of claim 18, wherein the three elongated blades are generally equiangularly located and the fourth of said conductive arms extends radially generally bisecting the angle between two elongated blades.