Apparatus for enhancing searches of data tables

Claim 2

1 . An apparatus for searching a table of data, comprising: table storage means for storing a table of a plurality of lines of data; line linking means for associating subsets of said plurality of lines into a plurality of exclusive lists; list header means for accessing the first entry in one of said plurality of exclusive lists in which a desired line is associated; and table search means for searching said table storage means beginning with said first entry in one said plurality of exclusive lists and proceeding according to said line linking means to each succeeding entry in said exclusive ordered list.

Claim 3

The apparatus of claim 1, wherein: said table storage means is accessed by table addresses; and said line linking means includes link address means for storing the table address of said first entry in said list header means and the table address of other entries in said list along with said line of data immediately preceeding said other entries.

Claim 4

The apparatus of claim 1, further including: end indicator means associated with the last entry in each of said exclusive lists for indicating to the table search means that the end of said exclusive list has been reached.

Claim 5

The apparatus of claim 1, wherein: said table of said plurality of lines of data includes the system address portion of a translation means for translation from a virtual address to a system address.

Claim 6

The apparatus of claim 1, wherein: said list linking means associates said plurality of lines in a predetermined order.

Claim 7

The apparatus of claim 5, further including: search end means for detecting the position in said order of each succeeding entry in said list and comparing the position of succeeding entries with the searched for entry and signalling the table search means when the search has passed the position of the searched for entry.

Claim 8

The apparatus of claim 1, wherein: said table search means further monitors the validity of each entry in said list to determine list end conditions.

Claim 9

The apparatus of claim 2, wherein: said table search means includes an interference register for holding the table address of an entry to be searched when the search is interrupted.

Claim 10

The apparatus of claim 1, wherein: said table search means includes interruption control means for controlling interruptions in said searching.

Claim 11

In a data processing machine, an apparatus for storing data, comprising: a primary storage means for storing data; primary addressing means for uniquely addressing said data with unique primary addresses; secondary storage means for storing data in communication with said primary storage means so that data may be transferred between said primary storage means and said secondary storage means, secondary addressing means for addressing said secondary storage means with secondary addresses; forward translation means for translating said secondary addresses to said unique primary addresses to uniquely address said data; and reverse translation means for translating said unique primary addresses to synonym secondary addresses which translate to said unique primary addresses including means for storing entries for associating secondary addresses to primary addresses, and pointer means for storing pointers for pointing to corresponding entries in said forward translation means.

Claim 12

In a data processing machine, an apparatus for storing data, comprising: a primary storage means for storing data; primary addressing means for uniquely addressing said data with unique primary addresses; secondary storage means for storing data in communication with said primary storage means so that data may be transferred between said primary storage means and said secondary storage means, secondary addressing means for addressing said secondary storage means with secondary addresses; forward translation means for translating said secondary addresses to said unique primary addresses to uniquely address said data; and reverse translation means for translating said unique primary addresses to synonym secondary addresses which translate to said unique primary addresses including means for storing entries for associating secondary addresses to primary addresses, and pointer means for storing pointers for pointing to corresponding entries in said forward translation means.

Claim 13

The apparatus of claim 10, wherein said pointer means includes: means for storing a list header table having entries for pointing to the beginning entry of a link list; means for storing a link list where each entry in a link list has a pointer for pointing to an entry in said forward translation; and means whereby real addresses corresponding to said entry are obtained by said reverse translation means.