Self-managing variable field storage system for handling nested data structures

• US 4,027,288 A
• Filed: 02/09/1976
• Issued: 05/31/1977
• Est. Priority Date: 02/09/1976
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Burroughs Corp (Unisys Corporation)
• Inventors: Hodgman, Gary Wesley, Barton, Robert Stanley
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Heckler, Thomas M.
• Application Number:
  US05/656,280
• Time in Patent Office: 477 Days
• Field of Search: 340/172.5, 360/50, 360/71, 360/72
• US Class Current: 711/113
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G11C 19/287 Organisation of a multiplicity of shift registers

Abstract

This disclosure relates to a storage system employing a serial periodic memory as the storage mechanism. The storage mechanism has one or more control and access ports which control data transmission to and from the storage mechanism, each port including input and output devices associated with a data track of the storage mechanism. A queue shift register is coupled between the input and output devices to receive previously stored information characters which are to be temporarily held when newly received information characters are to be written into the storage media. Control of the system resides in the control ports and is activated by commands from the external sources. A character set is employed which includes a beginning delimiter character and an ending delimiter character such that information segments may be of any length up to the capacity of the storage mechanism. The system control ports manage, among other things, the explicit representation of the beginning and end of strings of data and the decomposition of strings into substrings, the automatic allocation and reclamation of unused storage space as strings of data increase or decrease in size, and the permission or prohibition of access to data strings depending on the requestor'"'"'s identity. Data strings may be accessed according to their order or by symbolic addressing.

Claims

1. A variable field storage system for storing variable length data field segments, each of which starts with a beginning delimiter character and ends with an ending delimiter character, said system being capable of containing free space between said segments, said system comprising:

a serial periodic storage media;

an input device coupled to said storage media;

an output device coupled to said storage media;

an input/output data bus;

an access shift register means coupled to said input device and said output device and to said input/output data bus to receive data segments from said data bus for transmission to said input device and to receive data segments from said output device for transmission to said data bus; and

a queue shift register means coupled to said input device and said output device to receive from said output device data segments that are to be temporarily retained to provide storage space for new data segments that are supplied to said input device from said access shift register when free storage space is available between stored segments.

2. A storage system according to claim 1 which further includes:

a command bus to supply commands;

a command register coupled to said command bus to receive various commands to be carried out by said system; and

decoder means coupled to said command register and to said other registers and devices to decode commands received by said command register and to supply control signals to said other registers and devices.

3. A storage system according to claim 1 including:

a name tag bus to supply name tags;

a name tag register coupled to said name tag bus to receive one or more name tags; and

comparator means coupled to said access shift register means and to said name tag register to compare various data field segments with name tags received by said name tag register.

4. A variable field storage system for storing variable length data field segments, each of which starts with a beginning delimiter character and ends with an ending delimiter character, said segments being capable of being nested to any level as determined by the number of beginning delimiter characters previously not matched by ending delimiter characters during the scanning of each segment from the beginning of an initial segment, said system comprising:

a storage media;

a serial input means coupled to said storage media;

a serial output means coupled to said storage media; and

a delimiter balance counter means coupled to said serial output means to maintain a count of the number of beginning delimiter characters for a given field segment which have not been matched by an ending delimiter character.

5. A storage system according to claim 4 including:

an access shift register coupled to said input and said output means, said delimiter balance counter being coupled to said access shift register to maintain a count of said beginning and ending delimiter characters as field segments are transferred from said output means to said access shift register.

6. A system according to claim 5 which further includes:

a name tag bus to supply name tags and ordinal values;

a name tag register coupled to said name tag bus to receive either name tags indicating a field stored in said storage media or an ordinal value representing the position of said field in said storage media; and

a comparator means coupling said name tag register to said balance counter to determine when a field exists in said access shift register which field has the ordinal position corresponding to the ordinal positions received by said name tag register.

7. A variable field storage system for storing variable length data field segments each of which starts with a beginning delimiter character and ends with an ending delimiter character, said system being capable of containing free space between said segments, said system comprising:

a storage media;

serial input means coupled to said storage media;

serial output means coupled to said storage media;

means coupled to said storage media to detect said beginning delimiter characters and said ending delimiter characters; and

free space detection means coupled to said storage media to detect the existence of a data character immediately following an ending delimiter character.

8. A storage system according to claim 7 further including:

an access shift register coupled to said input and output means and to which said free space detection means is coupled.

9. A system according to claim 8 further including:

a character generator coupled to said access shift register to supply additional characters thereto.

10. In a variable field storage system for storing variable length data field segments, each of which starts with a beginning delimiter character and ends with an ending delimiter character, said system being capable of containing free space between said segments, said system including a serial periodic storage media, a character generator coupled to said storage media and means to write over characters previously stored in said media, the method comprising;

detecting a beginning delimiter character of a field segment in said storage media;

counting a prescribed number of character positions following said detected beginning delimiter character;

generating an ending delimiter character and also data characters which are all of one kind after said generated ending delimiter character; and

writing said generated characters over previously stored characters in said storage media at a position starting after said counted positions, said characters all of one kind indicating free space.

11. A method according to claim 10 which further comprises:

writing over characters which are all of one kind after an ending delimiter character; and

generating an equal number of said characters all of one kind after a succeeding ending delimiter character, said characters all of one kind indicating free space.

12. In a variable field storage system for storing variable length data field segments, each of which starts with a beginning delimiter character and ends with an ending delimiter character, said segments being capable of being nested to any level as determined by the number of beginning delimiter characters previously not matched by an ending delimiter character during the scanning of each segment from the beginning of an initial segment, said system including a delimiter balance count register, the method comprising:

incrementing said balance count register each time a beginning delimiter character is detected in a field segment; and

decrementing said balance count register each time an ending delimiter character is detected in said field segment such that the contents of said balance count register indicates the level of nesting of a current segment.

13. A method according to claim 12 which further includes:

maintaining a count of all beginning delimiter characters at a given level which are unmatched by an ending delimiter character so as to specify the ordinal position of the respective fields within said beginning and ending delimiter characters at said given level.