US5423015A — Memory structure and method for shuffling a stack…

Claim 1

Independent Claim 152 words

A memory structure for storing records, said structure comprising a plurality of contiguous memory locations each for storing one of said records, said plurality of memory locations being divided into memory sub-structures, each of said memory sub-structures comprising a separate but contiguous sub-portion of said memory structure, each of said sub-structures including a buffer memory location attached thereto, each of said buffer memory locations being arranged to receive a record stored in a memory location within the corresponding sub-structure and to transfer a record stored in that buffer memory location to a memory location within the corresponding sub-structure, wherein each of said buffer memory locations is further arranged to; receive a record stored in one of said memory locations of an immediately adjacent one of said sub-structures; and to transfer a record stored in that buffer memory location to one of said memory locations of an immediately adjacent one of said sub-structures.

Claim 2

Dependent Claim 152 words

A memory structure for storing records, said structure comprising a plurality of contiguous memory locations each for storing one of said records, said plurality of memory locations being divided into memory sub-structures, each of said memory sub-structures comprising a separate but contiguous sub-portion of said memory structure, each of said sub-structures including a buffer memory location attached thereto, each of said buffer memory locations being arranged to receive a record stored in a memory location within the corresponding sub-structure and to transfer a record stored in that buffer memory location to a memory location within the corresponding sub-structure, wherein each of said buffer memory locations is further arranged to; receive a record stored in one of said memory locations of an immediately adjacent one of said sub-structures; and to transfer a record stored in that buffer memory location to one of said memory locations of an immediately adjacent one of said sub-structures.

Claim 3

Dependent Claim 32 words

The memory structure of claim 1, wherein each of said records includes a search key comprising at least a part of each record and said records are stored in search key order.

Claim 4

Dependent Claim 18 words

The memory structure of claim 1, wherein each of said sub-structures includes an equal number of memory locations.

Claim 5

Dependent Claim 24 words

The memory structure of claim 1, wherein each of said buffer memory locations is the same size as each one of said memory locations.

Claim 6

Dependent Claim 25 words

The memory structure of claim 1, wherein each buffer memory location has the capacity to hold more than one record held in said memory locations.

Claim 7

Dependent Claim 53 words

The memory structure of claim 1, wherein said memory structure performs as a stack, and whereby a record is added to the stack at a chosen one of said memory locations within said memory structure by shuffling all records at and above said chosen memory location up one memory location (UP SHUFFLE OPERATION).

Claim 8

Dependent Claim 18 words

The memory structure of claim 1, wherein said records in said memory structure are maintained in sorted order.

Claim 9

Dependent Claim 86 words

The memory structure of claim 1 further comprising an overlap switching configuration for allowing data to be transferred between said sub-structures concurrently through a two-stage process, said overlap switching configuration comprising switches between each sub-structure, said switches being divided into two sets in which every second switch belongs to the same set, said data transfer being effected by turning said sets on and off so as to link and respectively isolate each sub-structure with neighboring ones of said sub-structures thereby allowing concurrent data transfer between sub-structures.

Claim 10

Dependent Claim 46 words

The memory structure of claim 1 further comprising control bits appended to the record in each occupied memory location, said control bits being maskable and allowing marking of specific ones of said records for use by different applications including identifying identical search keys of different records.

Claim 11

Dependent Claim 53 words

The memory structure of claim 1, wherein the memory structure performs as a stack, and whereby a record is added to the stack at a chosen memory location within said structure by shuffling all records at and below said chosen memory location down one memory location (DOWN SHUFFLE OPERATION) in the memory structure.

Claim 12

Dependent Claim 44 words

The memory structure of claim 1, wherein the memory structure performs as a stack, and whereby a record is added to the stack at a chosen memory location within said structure by shuffling all records sideways in raster format when said sub-structures are transposed.

Claim 13

Dependent Claim 29 words

The memory structure of claim 1, wherein the memory structure performs as a stack, and whereby a record is deleted from said stack by a logically opposite overwrite process.

Claim 14

Independent Claim 185 words

A method of storing records in a memory structure having a plurality of contiguous memory locations, each for storing one of said records, said plurality of memory locations being divided into memory sub-structures, each of said memory sub-structures comprising a separate but contiguous sub-portion of said memory structure, each of said sub-structures including a buffer memory location attached thereto, each of said buffer memory locations being arranged to receive a record stored in a memory location within the corresponding sub-structure and to transfer a record stored in that buffer memory location to a memory location within the corresponding sub-structure, wherein each of said buffer memory locations is further arranged to; receive a record stored in one of said memory locations of an immediately adjacent one of said sub-structures; and to transfer a record stored in that buffer memory location to one of said memory locations of an immediately adjacent one of said sub-structures; said method comprising the steps of storing said records in said memory structure in search key order, and placing said records into contiguous memory locations in said structure ordered by search key.

Claim 15

Independent Claim 185 words

A method of storing records in a memory structure having a plurality of contiguous memory locations, each for storing one of said records, said plurality of memory locations being divided into memory sub-structures, each of said memory sub-structures comprising a separate but contiguous sub-portion of said memory structure, each of said sub-structures including a buffer memory location attached thereto, each of said buffer memory locations being arranged to receive a record stored in a memory location within the corresponding sub-structure and to transfer a record stored in that buffer memory location to a memory location within the corresponding sub-structure, wherein each of said buffer memory locations is further arranged to; receive a record stored in one of said memory locations of an immediately adjacent one of said sub-structures; and to transfer a record stored in that buffer memory location to one of said memory locations of an immediately adjacent one of said sub-structures; said method comprising the steps of storing said records in said memory structure in search key order, and placing said records into contiguous memory locations in said structure ordered by search key.

Claim 16

Dependent Claim 28 words

The method of claim 13, wherein the memory structure performs as a stack, and whereby a record is deleted from said stack by a logically opposite overwrite process.

Claim 17

Dependent Claim 60 words

The method of claim 13, wherein said memory structure performs as a stack, and said method further comprises the step of adding a record to the stack at a chosen one of said memory location within said memory structure by shuffling all records at and above said chosen one of said memory locations up one memory location (UP SHUFFLE OPERATION).

Claim 18

Dependent Claim 190 words

The method of claim 15 wherein an UP SHUFFLE OPERATION is performed by dividing said stack into smaller sub-stacks as follows: A. all memory locations in the sub-structure containing said chosen one of said memory locations above said chosen one of said memory locations are treated as a sub-stack, B. all sub-structures above the sub-structure containing said chosen one of said memory locations are treated as sub-stacks, C. a record is popped off the top of each of the stacks and is respectively stored in the buffer memory location attached to the sub-structure immediately above the sub-structure from which that record has been popped, D. all of the sub-stacks are pushed up by one memory location, E. to complete the UP SHUFFLE OPERATION, each record now stored in each buffer memory location as a result of the UP SHUFFLE OPERATION so far is transferred to the bottom memory location in the sub-structure to which that buffer memory location is attached, and F. at the same time as or subsequent to step E, the record to be added to said stack is transferred into said chosen one of said memory locations.

Claim 19

Dependent Claim 33 words

The method of claim 15 wherein said method further comprises the step of overwriting a chosen location by shifting the records of all memory locations below that chosen memory location up one location.

Claim 20

Dependent Claim 64 words

The method of claim 13, wherein the memory structure performs as a stack, and said method further comprises the step of adding a record to the stack at a chosen one of said memory locations within said memory structure by shuffling all records at and below said chosen one of said memory locations down one memory location (DOWN SHUFFLE OPERATION) in the memory structure.

Claim 21

Dependent Claim 189 words

The method of claim 18 wherein a DOWN SHUFFLE OPERATION is performed by dividing said stack into smaller sub-stacks as follows: A. all memory locations in the sub-structure containing said chosen one of said memory locations below said chosen one of said memory locations are treated as a sub-stack, B. all sub-structures below the sub-structure containing said chosen one of said memory locations are treated as sub-stacks, C. a record is pushed off the bottom of each of the sub-stacks and is respectively stored in the buffer memory location attached to the sub-structure immediately below the sub-structure from which that record has fallen, D. all of the sub-stacks are pushed down by one memory location, E. to complete the DOWN SHUFFLE OPERATION, each record now stored in each buffer memory location as a result of the DOWN SHUFFLE OPERATION so far is transferred to the top memory location in the sub-structure to which that buffer memory location is attached, and F. at the same time as or subsequent to step E, the record to be added to said stack is transferred into said chosen one of said memory locations.

Claim 22

Dependent Claim 34 words

The method of claim 18 wherein said method further comprises the step of overwriting a chosen memory location by shifting the records of all memory locations above that chosen memory location down one location.

Claim 23

Dependent Claim 48 words

The method of claim 13, wherein the memory structure performs as a stack, and said method further comprises the step of adding a record to the stack at a chosen memory location within said structure by shuffling all records sideways in raster format when said sub-structures are transposed.

Claim 24

Dependent Claim 146 words

The method of claim 21, wherein a raster type shuffle is performed as follows: A. all sub-structures are in a side by side format, B. for all memory locations below said chosen one of said memory locations at which an insertion is desired, C. each record in the lowermost row of memory locations in all sub-structures is shifted into the corresponding buffer memory location, D. each record in each buffer memory location is shifted into the memory location of the adjacent sub-structure corresponding to the memory location from which that record has just been removed, E. steps C and D are repeated for the next row up of memory locations in all sub-structures until the record in said chosen one of said memory locations is moved, and F. the record to be added to the stack is inserted in said chosen one of said memory locations.

Claim 25

Dependent Claim 146 words

The method of claim 21, wherein a raster type shuffle is performed as follows: A. all sub-structures are in a side by side format, B. for all memory locations above said chosen one of said memory locations at which an insertion is desired, C. each record in the uppermost row of memory locations in all sub-structures is shifted into the corresponding buffer memory location, D. each record in each buffer memory location is shifted into the memory location of the adjacent sub-structure corresponding to the memory location from which that record has just been removed, E. steps C and D are repeated for the next row down of memory locations in all sub-structures until the record in said chosen one of said memory locations is moved, and F. the record to be added to the stack is inserted in said chosen one of said memory locations.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-06-05	1998-12-05	1999-06-06	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-06-05	2002-12-05	2003-06-06	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-06-05	2006-12-05	2007-06-06	$7700.00	Window Closed / Lapsed

Memory structure and method for shuffling a stack of data utilizing buffer memory locations

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag