Application of Knowlton

• Decision Date: 26 July 1973
• Docket Number: Patent Appeal No. 8896.
• Citation: 178 USPQ 486,481 F.2d 1357
• Parties: Application of Kenneth C. KNOWLTON.
• Court: U.S. Court of Customs and Patent Appeals (CCPA)

178 USPQ 486, 481 F.2d 1357 (1973)

Application of Kenneth C. KNOWLTON.

Patent Appeal No. 8896.

United States Court of Customs and Patent Appeals.

July 26, 1973.

Robert O. Nimtz, Murray Hill, N. J., attorney of record, for appellant.

S. Wm. Cochran, Washington, D. C., for the Commissioner of Patents. Jere W. Sears, Washington, D. C., of counsel.

Before MARKEY, Chief Judge, and RICH, ALMOND, BALDWIN, and LANE, Judges.

BALDWIN, Judge.

This appeal is from the decision of the Patent Office Board of Appeals affirming the examiner's rejection of claims 1-22, all the claims in appellant's application.¹

The Invention

Appellant's invention relates to a system for computer processing of list information, i. e., items of information which are related or have characteristics in common, such as business inventories, personnel files, business accounts, etc. The application states:

For many applications, data items can be easily linked by their mere contiguity, such as a list on a single sheet of paper. In other cases, however, items are added and deleted at various times, and the interrelationship between items is not a simple linear one. In an inventory list, for example, a hierarchy must be maintained with each item linked in one way to the items out of which it is made, and linked in another way to that item of which it forms a part. In addition, cross referencing, for example, to other items which are similar in structure or origin may also be required. While separate lists could be maintained to express all of these relationships by duplicating appropriate items on the different lists, such an organization is wasteful of space and unmanageable with even moderately-sized item sets.

A more useful listing includes each item only once, but includes with the data item "links" to all other relevant items. Since these "linkages" have many different significances, the links likewise have distinguishable characteristics.

In the present invention, a data item is entered into a unitary block of storage space along with all of the necessary links. Since the number of linkages is variable as well as the number and size of data items, the size of the storage blocks is likewise made variable. In order to distinguish the various linkages, they are entered into different fields in the storage blocks. A field, in this connection, is defined as any contiguous set of single bit storage positions within the block. Since the blocks are naturally divided into "words" (i. e., standard length contiguous bit positions), fields are also defined to include only portions (or the whole) of single words. The various links then constitute address pointers to the linked blocks.

In order to utilize the available storage capacity most efficiently, so-called "free storage" lists are likewise maintained. These are singly-linked lists of the storage blocks available in the system, but not yet called into use. Since different size blocks are available, a separate list is provided for each size of block. The entire available storage area may, for example, initially be assembled into a single free storage list of blocks of the maximum size. A block of this size can then be obtained merely by removing it from the free storage list. If a smaller sized block is required, larger blocks are split in two until a block of the appropriate size is avaialable. Finally, when blocks are no longer needed, they can be returned to the appropriate free storage list for future use.

The application sets out schematic block diagrams related to various aspects of the invention. Figure 1 is typical, and shows how the memory blocks of various sizes are obtained:

The application also contains descriptions of the drawings, in which the relationships between the depicted components of the invention are generally described. However, what appellant contends is a complete disclosure of the preferred embodiment of the invention is made up of a number of computer program listings for use of the invention with a general purpose digital computer, and descriptions of how the listed programs work. The specification refers to the IBM 7094 Data Processing System as one type of apparatus which could process the listed computer programs.

The first listing which appears in the application is entitled "Storage Allocator," and the first part of that listing appears as follows:

                                      PROGRAM LISTING NO. 1
                  ||
                  ||*
                  ||*         * * * * * * STØRAGE ALLØCATØR * * * * * *
                  ||*
                  ||*                    1-BLØCK PRØCURER
                  ||*
                  ||
                 1|| GET.1 SXA   *+8,4     SAVE INDEX REGISTER 4
                 2||       NZT   1.S       TEST 1-BLØCK STØRAGE LIST FØR EMPTY
                 3||       TSX   SPLIT2,4  IF EMPTY, SPLIT A 2-BLØCK
                 4||       LDQ   1.S       ADDR. ØF 1ST FREE BLØCK INTØ MQ
                 5||       CAL*  1.S       ADDR. ØF 2ND FREE BLØCK INTØ AC
                 6||       STZ*  1.S       CLEAR PØINTER IN 1ST FREE BLØCK
                 7||       STA   1.S       ADDR. ØF 2ND BLØCK INTØ HEAD ØF LIST
                 8||       XCL             ADDR. ØF 1ST BLØCK INTØ AC
                 9||       AXT   **, 4     RESTØRE INDEX REGISTER 4
                10||       TRA   1, 4      RETURN
                  ||*
                

Following each program listing, there is an explanation of how the listed program works. While some of these explanations are more detailed than others, we find that the explanation of the above-quoted portion of the first listing is sufficiently representative for an understanding of the case:

The 1-block procurer * * * is implemented by the "GET.1" subroutine, entered by a transfer to the location labeled GET.1. The first instruction (SXA * + 8,4) is a direction to save the contents of the indicated index register, in this case, index register 4, in the location "* + 8," which is interpreted as the location eight instructions after the current instruction. This is instruction 9 in the GET.1 subroutine, and the index register contents are stored in the address field of instruction 9 reserved by the double asterisk. Since index register four will be used in the GET.1 subroutine to hold a reference address when transferring to another subroutine, the original contents must be saved. These contents represent an address in the main program from which the transfer to the GET.1 subroutine took place and to which control is to be returned after execution of the subroutine.

Instruction 2 in the GET.1 subroutine (NZT 1.S) is a direction to test the contents of location 1.S for a zero. If a zero is found there, the next instruction is executed. If anything but zero is found, the next instruction is skipped. The location 1.S is the head of the 1-block free storage list. If there are any 1-blocks on this list, location 1.S holds a pointer to the first block. If there are none, location 1.S holds zero. The test at instruction 2 ascertains which is the case, and, if a zero is found (no 1-block available), instruction 3 (TSX SPLIT2,4) is executed. This instruction is a transfer to the subroutine "SPLIT2" corresponding to the 2-block splitter 16 in Fig. 1. Before transferring, the current location (of instruction 3) is stored in index register 4 to provide a return address from the SPLIT2 subroutine. The SPLIT2 subroutine returns with the addresses of two 1-blocks, the address of the first in location 1.S, and the address of the second in the first.

Instruction 4 (LDQ 1.S) loads the 1-block address in location 1.S into the Multiplier-Quotient Register. Instruction 5 (CAL* 1.S) places the address in the 1-block whose address is in location 1.S into the Accumulator Register. This indirect addressing facility (indicated by the asterisk after CAL) is available in many general purpose computers. If not available, the same effect can be obtained by explicitly getting the address and using it for access.

Instruction 6 (STZ* 1.S) puts all zeros in the location whose address is in location 1.S. This, of course, is the first 1-block. This block is cleared so as to be ready for use when delivered back to the main program.

Instruction 7 (STA 1.S) stores the address which is in the Accumulator Register into location 1.S. As noted in instruction 5, this address is the address of the second 1-block in the list. In effect, the first 1-block has been removed from the free storage list by replacing the address of the first 1-block with the address of the second 1-block in location 1.S (the head of the free storage list).

Instruction 8 (XCL) exchanges the contents of the Accumulator Register and the Multiplier-Quotient Register. This leaves the address of the first 1-block, loaded into the Multiplier-Quotient Register in instruction 4, in the Accumulator Register. This is where it is expected to be found when returning from the GET.1 subroutine.

Instruction 9 (AXT **,4) was discussed above. This instruction loads the return address back into index register 4 to permit a return to the main program.

Instruction 10 (TRA 1,4) transfers control back to the calling program. It transfers control to the first location after the location stored in index register 4.

Appellant states that "the claims are all couched in the `means-plus-function' claim format sanctioned by the third paragraph of 35 U.S.C. § 112." He further states that most of them "call for means for organizing a memory into storage blocks, means for specifying fields in such storage blocks, base registers for holding pointer signals to the blocks, and processing means using the pointer signals for operating on the contents of specified fields." Claim 1 is exemplary (paragraphing ours):

1. A linked list processor comprising a memory,

means for establishing blocks of storage within said memory,

means for specifying fields within said blocks for storing data signals and linking signals,

said fields being of arbitrary size and location within said blocks,

a plurality of base registers for storing linking signals to prescribed ones of said blocks, and

means for accessing and processing the contents of any prescribed field in said memory.

The Rejections

The board sustained...