Patent GB-1207318-A (GB)
Title: System for processing list information
Inventor: KNOWLTON KENNETH CHARLES
IPC: G06F9/40
Filed: 1967-11-21
Abstract: 1,207,318. Digital electric data processor. WESTERN ELECTRIC CO. Inc. 21 Nov., 1967 [1 Dec., 1966], No. 52823/67. Heading G4A.  A linked list processor comprises a memory storing in blocks of storage locations therein information items and pointers, each pointer identifying a block containing related information items, means for defining fields of variable sizes and locations within the blocks, a plurality of base registers storing pointers identifying prescribed ones of the blocks, and means for accessing the contents of any prescribed said field. Storage allocator (Fig. 1). Data to be stored may be of variable length and may be related to various other items of data. Linking information is defined by fields of various sizes and locations within each item of data, the data in the fields constituting address pointers to linked blocks. Since the data is of variable length it is arranged to be stored in blocks of 1, 2 or 4 word length, for instance. A request for data storage occurs on lines 13, 22, 30 for 1, 2, 4 blocks respectively. The request is applied to the appropriate procurer 10, 11, 12 which examines a list of available blocks of the required size 14, 23, 31. If a block is available it is delivered on corresponding lines 15, 24, 32. If a block is not available a request is sent to the next largest block procurer which repeats the search. If a larger block is available it is delivered to a splitter 16, 25 which divides the block in two and adds two addresses to the appropriate free storage list for access by the originally requested procurer. For the first request a storage initializer is called in which divides the entire available list memory into 4-blocks. When a block is no longer needed its address is returned to the free storage list and when two mated blocks are returned they are recombined and returned to the storage list of the next larger block. The storage allocator described can be implemented by means of circuit arrangements or preferably by appropriately programming a general purpose computer using a plurality of subroutines corresponding, one for one, to the blocks of Fig. 1. The programmes are given. Field access control (Fig. 2). Three field accessors 50, 51, 52 are able to retrieve the contents of a different field of the storage blocks in the list memory 53 and return data to the said field. Each accessor has direct access to a particular field but the field must be further referenced to a particular data storage block so a pointer to the storage block accompanies the request for fetching or storing. A fetch-store initializer specifies all the parameters of the various fields and can be used to vary the parameters at any time after processing has been done. Again, preferably, the control is implemented by programming a general purpose computer and programs corresponding to the bracketed headings in Fig. 2 are given.  Subroutine push-down control.-When a subroutine calls other subroutines during its execution a system automatically keeps a record of the nested calls. A plurality of storage locations are used each including at least two portions, one of which stores the return address, the other of which carries a pointer which is the address of the next succeeding word on the list. The head of the list is identified by a mnemonic SUBPDL and contains only the address of the latest entry on the list. A programme is given corresponding to the push-down control.