Patent GB-1000962-A (GB)
Title: Data storage system
IPC: G06F17/30
Filed: 1964-05-26
Abstract: 1,000,962. Electric digital data-storage. INTERNATIONAL BUSINESS MACHINES CORPORATION. May 26, 1964 [June 12, 1963], No. 21797/64. Heading G4C. A data storage system includes means to search through a linked group of data strings stored in a main memory and each including a name portion and a complete memory address, and utilizes an auxiliary memory storing the address of one member of each group. Each data string (or word) in main memory comprises name, link address and data portions, the data strings being " arranged " in mutually-exclusive closed loops by storing the address of each string in the link address portion of the previous string in the same loop (the address of the "first" string of a loop is stored in the link address portion of the " last " string of the loop). All strings have different names but the first two characters of the names within a given loop are all the same. The address of the last string (or string location) in each loop to be accessed (or in the case of an erase operation-see belowthat of the string before it in the loop) is stored in an auxiliary (Map) memory 17 at an address obtained by decoding the first two characters referred to. An instruction register stores the name of a data string in main memory to be erased, read out or have its data portion replaced with new data (write operation). In the case of a write operation, the new data is also stored in the instruction register. The middle six bits of each of the first two characters of the name in the instruction register (each character has eight bits) are decoded and used to address the Map memory 17 to read out 14 bits into the name loop address register shown. If all these bits are blank, indicating absence of a loop with those two characters starting the names of its data strings, then (a) in the case of an erase or read operation, an error indication is given, and (b) in the case of a write operation, a new onestring loop is created in main memory at an address specified by an availability list, which may involve counters if main memory addresses are filled up in sequence. (The link address portion of the data string is filled with the address of the string itself ). On the other hand, if the loop already exists, the strings in it are read out in turn and their names compared with that in the instruction register until equality is found or until the loop has been traversed once. The latter event is detected by comparing the link address portion of each string, as it is read out, with the address in the name loop address register, equality indicating that the loop has been traversed. If a string with the required name already exists in the main memory, then the required operation is performed when it is located. If this is an erase operation, then the link address in the erased string replaces the link address in the previous string in the loop. To enable this to be done, a register is provided (previous MAR address register) which stores the last-accessed main memory address. On the other hand, if a string with the required name does not exist in the loop an error indication is given in the case of an erase or read operation, and in the case of a write operation, the new string is inserted into the loop at an address specified by the availability list, the value of the linking address portion of the preceding string of the loop being changed to the address of the new string and the old value of this portion being adopted as the linking address portion of the new string. If a loop is completely erased, blanks are inserted into the appropriate address of Map memory 17. Modifications mentioned.-Each data string may consist of a variable number of machine words. Insertion of a new data string into a loop (as distinct from altering the data portion of an existing one) may be done in such a way that alphabetical order of the names in the loop is produced and preserved. Searching through a loop may be done in the order: name last accessed, name preceding that, followed by name succeeding it &c.