Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 588

RESPONSE in Opposition re #558 SEALED MOTION -- Defendants' Combined Daubert and Rule 26(A) Motion to Exclude the Expert Testimony of Dr. Mark Jones SEALED MOTION -- Defendants' Combined Daubert and Rule 26(A) Motion to Exclude the Expert Testimony of Dr. Mark Jones SEALED MOTION -- Defendants' Combined Daubert and Rule 26(A) Motion to Exclude the Expert Testimony of Dr. Mark Jones filed by Bedrock Computer Technologies, LLC. (Attachments: #1 Declaration of Austin Curry, #2 Exhibit A.1, #3 Exhibit A.2, #4 Exhibit A.3, #5 Text of Proposed Order)(Cawley, Douglas)

Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Doc. 588 Att. 2

Exhibit A.1

Dockets.Justia.com

Case 6:09-cv-00269-LED

Document 1-2 111111
[19]

Filed 06/16/2009 Page 2 of 15 1111111111111111111111111111111111111111111111111111111111111
US005893120A
[11] [45]

United States Patent
Nemes
[54]

Patent Number: Date of Patent:

5,893,120
Apr. 6, 1999

METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL USING A HASHING TECHNIQUE WITH EXTERNAL CHAINING AND ON-THE-FLY REMOVAL OF EXPIRED DATA Inventor: Richard Michael Nemes, 1432 E. 35th St., Brooklyn, N.Y. 11234-2604

[76]

R.L. Kruse, Data Structures and Program Design, Second Edition, Prentice-Hall, Englewood Cliffs, New Jersey, 1987, Section 6.5, "Hashing," and Section 6.6, Analysis of Hashing, pp. 198-215. D. F. Stubbs and N.W. Webre, Data Structure with Abstract Data Types and Pascal, Brooks/Cole Publishing Company, Monterey, California, 1985, Section 7.4, "Hased Implementations," pp. 310-336.

[21] [22] [51] [52] [58]

Appl. No.: 775,864 Filed:
6

Primary Examiner-Thomas G. Black Assistant Examiner-Hosain T. Alam
[57] ABSTRACT

Jan. 2, 1997

Int. CI. ...................................................... G06F 17/30 U.S. CI. .............................. 707/206; 707/1; 707/100; 707/101; 707/202 Field of Search ................................ 707/1, 200-206, 707/2,100-103 References Cited U.S. PATENT DOCUMENTS
5,121,495 5,202,981 5,287,499 6/1992 Nemes ........................................ 707/3 4/1993 Shackelford ................................ 707/1 2/1994 Nemes .................................... 707/206

[56]

OlliER PUBLICATIONS D.E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1973, pp. 506-549.

A method and apparatus for performing storage and retrieval in an information storage system is disclosed that uses the hashing technique with the external chaining method for collision resolution. In order to prevent performance deterioration due to the presence of automatically expiring data items, a garbage collection technique is used that removes all expired records stored in the system in the external chain targeted by a probe into the data storage system. More particularly, each insertion, retrieval, or deletion of a record is an occasion to search an entire linked-list chain of records for expired items and then remove them. Because an expired data item will not remain in the system long term if the system is frequently probed, it is useful for large information storage systems that are heavily used, require the fast access provided by hashing, and cannot be taken off-line for removal of expired data. 8 Claims, 6 Drawing Sheets

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 3 of 15

u.s.

Patent

Apr. 6, 1999

Sheet 1 of 6

5,893,120

15

D
PRINTER
16

RANDOM ACCESS MEMORY

1

CENTRAL
~~t'HIUL.lt:::>;:'ING~~

UNIT

DISK CONTROL UNIT

~~

10

FIG. 1

USER ACCESS SOFTWARE

20

OPERATING GENERAL SYSTEM ~~ UTILITY SOFTWARE SOFTWARE 21 APPLICATION SOFTWARE 1
23

22

25

APPLICATION SOFTWARE 2

............
24

APPLICATION SOFTWARE N

FIG. 2

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 4 of 15

u.s. Patent

Apr. 6, 1999

Sheet 2 of 6

5,893,120

---30
HASH SEARCH KEY GET HEAD OF TARGET LIST 31

32

3
YES

34
NO

36
RETURN SUCCESS SAVE POINTER TO LIST ELEMENT NO REMOVE REMOVE RECORD (FIG. 4)

""---35

RETURN FAILURE

~-37

ADVANCE TO NEXT ELEMENT

41

FIG.3

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 5 of 15

u.s. Patent

Apr. 6, 1999

Sheet 3 of 6

5,893,120

~50

ADVANCE PTR TO ELEMENT FOLLOWING ONE TO REMOVE

2
YES
54
ADJUST HEAD PTRTO BYPASS ELEMENT

NO
3
ADJUST PREDECESSOR'S PTRTO BYPASS ELEMENT

DE-ALLOCATE LIST ELEMENT TO BE REMOVED

STOP

56

FIG.4

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 6 of 15

u.s. Patent

Apr. 6, 1999

Sheet 4 of 6

5,893,120

\----70
SEARCH-TABLE SEARCH FOR RECORD AND CLEAN TARGET LIST

YES
PUT RECORD IN LIST ELEMENT RETURNED BY SEARCH·TABLE 73

YES

78
RETURN FULL ALLOCATE NEW LIST ELEMENT

RETURN REPLACED

79
COpy RECORD INTO NEW LIST ELEMENT

o
INSERT NEW LIST ELEMENT INTO TARGET LIST 1 RETURN INSERTED

( STOP

)-75
FIG.5

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 7 of 15

u.s. Patent

Apr. 6, 1999

Sheet 5 of 6

5,893,120

~90

2 YES NO

COpy RECORD

RETURN SUCCESS

RETURN FAILURE

STOP

FIG. 6

Case 6:09-cv-00269-LED

Document 1-2

Filed 06/16/2009

Page 8 of 15

u.s. Patent

Apr. 6, 1999

Sheet 6 of 6

5,893,120

,-,--100

YES

REMOVE DELETE ELEMENT (FIG. 4) RETURN SUCCESS STOP

103

RETURN FAILURE

106

FIG. 7

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 9 of 15

1
METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL USING A HASHING TECHNIQUE WITH EXTERNAL CHAINING AND ON-THE-FLY REMOVAL OF EXPIRED DATA CROSS-REFERENCE TO RELATED APPLICATIONS Not Applicable
10

2
Hall, Incorporated, Englewood Cliffs, N.J., 1987, Section 6.5, "Hashing," and Section 6.6, "Analysis of Hashing," pp. 198-215, and in Data Structures with Abstract Data Types and Pascal, by D. F. Stubbs and N. W. Webre, Brooks/Cole Publishing Company, Monterey, Calif., 1985, Section 7.4, "Hashed Implementations," pp. 310-336. Some forms of information are such that individual data items, after a limited period of time, become obsolete, and their presence in the storage system is no longer needed or desired. Scheduling activities, for example, involve data that become obsolete once the scheduled event has occurred. An automatically-expiring data item, once it expires, needlessly occupies computer memory storage that could otherwise be put to use storing an unexpired item. Thus, expired items must eventually be removed to reclaim the storage for subsequent data insertions. In addition, the presence of many expired items results in needlessly long search times since the linked lists associated with external chaining will be longer than they otherwise would be. The goal is to remove these expired items to reclaim the storage and maintain fast access to the data. The problem, then, is to provide the speed of access of hashing techniques for large, heavily used information storage systems having expiring data and, at the same time, prevent the performance degradation resulting from the accumulation of many expired records. Although a hashing technique for dealing with expiring data is known and disclosed in U.S. Pat. No. 5,121,495, issued Jun. 9, 1992, that technique is confined to linear probing and is entirely inapplicable to external chaining. The procedure shown there traverses, in reverse order, a consecutive sequence of records residing in the hash table array, continually relocating unexpired records to fill gaps left by the removal of expired ones. Unlike arrays, linked lists leave no gaps when items from it are removed, and furthermore it is not possible to efficiently traverse a singly linked list in reverse order. There are significant advantages to external chaining over linear probing that sometimes make it the method of choice, as discussed in considerable detail in the aforementioned texts, and so hashing techniques for dealing with expiring data that do not use external chaining prove wholly inadequate for certain applications. For example, if the data records are large, considerable memory can be saved using external chaining instead of linear probing. Accordingly, there is a need to develop hashing techniques for external chaining with expiring data. The methods of the above-mentioned patent are limited to arrays and cannot be used with linked lists due to the significant difference in the organization of the computer's memory. BRIEF SUMMARY OF THE INVENTION
55

5

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT Not Applicable REFERENCE TO A MICROFICHE APPENDIX Not Applicable BACKGROUND OF THE INVENTION This invention relates to information storage and retrieval systems, and, more particularly, to the use of hashing techniques in such systems. Information or data stored in a computer-controlled storage mechanism can be retrieved by searching for a particular key value in the stored records. The stored record with a key matching the search key value is then retrieved. Such searching techniques require repeated access to records into the storage mechanism to perform key comparisons. In large storage and retrieval systems, such searching, even if augmented by efficient search procedures such as the binary search, often requires an excessive amount of time due to the large number of key comparisons required. Another well-known and much faster way of storing and retrieving information from computer storage, albeit at the expense of additional storage, is the so-called "hashing" technique, also called scatter-storage or key-transformation method. In such a system, the key is operated on by a hashing function to produce a storage address in the storage space, called the hash table, which is a large onedimensional array of record locations. This storage address is then accessed directly for the desired record. Hashing techniques are described in the classic text by D. E. Knuth entitled The Art of Computer Programming, Volume 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973, pp. 506-549. Hashing functions are designed to translate the universe of keys into addresses uniformly distributed throughout the hash table. Typical hashing functions include truncation, folding, transposition, and modulo arithmetic. A disadvantage of hashing is that more than one key will inevitably translate in the same storage address, causing "collisions" in storage. Some form of collision resolution must therefore be provided. For example, the simple strategy called "linear probing," which consists of searching forward from the initial storage address to the first empty storage location, is often used. Another method for resolving collisions is called "external chaining." In this technique, each hash table location is a pointer to the head of a linked list of records, all of whose keys translate under the hashing function to that very hash table address. The linked list is itself searched sequentially when retrieving, inserting, or deleting a record. Insertion and deletion are done by adjusting pointers in the linked list. External chaining is discussed in considerable detail in the aforementioned text by D. E. Knuth, in Data Structures and Program Design, Second Edition, by R. L. Kruse, Prentice20

15

25

30

35

40

45

50

60

65

In accordance with the illustrative embodiment of the invention, these and other problems are overcome by using a garbage collection procedure "on-the-fiy" while other types of access to the storage space are taking place. In particular, during normal data insertion or retrieval probes into the data store, the expired, obsolete records are identified and removed from the external chain linked list. Specifically, expired or obsolete records in the linked list including the record to be accessed are removed as part of the normal search procedure. This incremental garbage collection technique has the decided advantage of automatically eliminating unneeded records without requiring that the information storage system be taken off-line for such garbage collection. This is

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 10 of 15

3
particularly important for information storage systems requiring rapid access and continuous availability to the user population. More specifically, a method for storing and retrieving information records using a linked list to store and provide access to the records, at least some of the records automatically expiring, is disclosed. The method accesses the linked list of records and identifies at least some automatically expired ones of the records. It also removes at least some automatically expired ones of the records from the linked list when the linked list is accessed. Furthermore, the method provides for dynamically determining maximum number of expired ones of the records to be removed when the linked list is accessed.

4

Central Processing Unit (CPU) 10 also controls an Input! Output (110) controller 14 that, in turn, provides access to a plurality of input devices such as CRT (cathode ray tube) terminal 15, as well as a plurality of output devices such as 5 printer 16. Terminal 15 provides a mechanism for a computer user to introduce instructions and commands into the computer system of FIG. 1, and may be supplemented with other input devices such as magnetic tape readers, remotely located terminals, optical readers, and other types of input 10 devices. Similarly, printer 16 provides a mechanism for displaying the results of the operation of the computer system of FIG. 1 for the computer user. Printer 16 may similarly be supplemented by line printers, cathode ray tube displays, phototypesetters, laser printers, graphical plotters, 15 and other types of output devices. BRIEF DESCRIPTION OF THE SEVERAL The constituents of the computer system of FIG. 1 and VIEWS OF THE DRAWING their cooperative operation are well-known in the art and are typical of all computer systems, from small personal comA complete understanding of the present invention may be puters to large mainframe systems. The architecture and gained by considering the following detailed description in 20 operation of such systems are well-known and will not be conjunction with the accompanying drawing, in which: further described here. FIG. 1 shows a general block diagram of a computer FIG. 2 shows a graphical representation of a typical system hardware arrangement in which the information software architecture for a computer system such as that storage and retrieval system of the present invention might shown in FIG. 1. The software of FIG. 2 comprises a user be implemented; 25 access mechanism that, for simple personal computers, may FIG. 2 shows a general block diagram of a computer consist of nothing more than turning the system on. In larger system software arrangement in which the information storsystems, providing service to many users, login and passage and retrieval system of the present invention might find word procedures would typically be implemented in user use; access mechanism 20. Once user access mechanism 20 has FIG. 3 shows a general flow chart for a table searching 30 completed the login procedure, the user is placed in the operation that might be used in a hashed storage system in operating system environment 21. Operating system 21 accordance with the present invention; coordinates the activities of all of the hardware components of the computer system (shown in FIG. 1) and provides a FIG. 4 shows a general flow chart for a linked-list element number of utility programs 22 of general use to the computer remove procedure that forms part of the table searching 35 user. Utilities 22 might, for example, comprise basic file operation of FIG. 3; access and manipulation programs, system maintenance FIG. 5 shows a general flow chart for a record insertion facilities, and programming language compilers. operation that might be used in a hashed storage system in The computer software system of FIG. 2 typically also accordance with the present invention; FIG. 6 shows a general flow chart for a record retrieval 40 includes application programs such as application software 23, 24, ... , 25. Application software 23 through 25 might, operation for use in a hashed storage system in accordance for example, comprise a text editor, document formatting with the present invention; and software, a spreadsheet program, a database management FIG. 7 shows a general flow chart for a record deletion system, a game program, and so forth. operation that might be used in a hashed storage system in 45 The present invention is concerned with information accordance with the present invention. storage and retrieval. It can be application software packages To facilitate reader understanding, identical reference 23-25, or used by other parts of the system, such as user numerals are used to designate elements common to the access software 20 or operating system 21 software. The figures. information storage and retrieval technique provided by the 50 present invention are herein disclosed as flowcharts in FIGS. DETAILED DESCRIPTION OF THE 3 through 7, and shown as PASCAL-like pseudocode in the INVENTION APPENDIX to this specification. FIG. 1 of the drawings shows a general block diagram of Before proceeding to a description of one embodiment of a computer hardware system comprising a Central Processthe present invention, it is first useful to discuss hashing ing Unit (CPU) 10 and a Random Access Memory (RAM) 55 techniques in general. Many fast techniques for storing and unit 11. Computer programs stored in the RAM 11 are retrieving data are known in the prior art. In situations where accessed by CPU 10 and executed, one instruction at a time, storage space is considered cheap compared with retrieval by CPU 10. Data, stored in other portions of RAM 11, are time, a technique called hashing is often used. In classic operated on by the program instructions accessed by CPU 10 hashing, each record in the information storage system from RAM 11, all in accordance with well-known data 60 includes a distinguished field unique in value to each record, processing techniques. called the key, which is used as the basis for storing and retrieving the associated record. Taken as a whole, a hash Central Processing Unit (CPU) 10 also controls and table is a large, one-dimensional array of logically accesses a disk controller unit 12 that, in turn, accesses a contiguous, consecutively numbered, fixed-size storage digital data stored on one or more disk storage units such as disk storage unit 13 until required by CPU 10. At this time, 65 units. Such a table of records is typically stored in RAM 11 of FIG. 1, where each record is an identifiable and addressuch programs and data are retrieved from disk storage unit sable location in physical memory. A hashing function 13 in blocks and stored in RAM 11 for rapid access.

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 11 of 15

5

6

successful and returns success in box 35, followed by the translates the key into a hash table array subscript, which is used as an index into the array where searches for the data procedure's termination in terminal box 37. If not, box 36 is record begin. The hashing function can be any operation on entered where failure is returned and the procedure again the key that results in subscripts mostly uniformly distribterminates in box 37. uted across the table. Known hashing functions include 5 If the end of the list has not been reached as determined truncation, folding, transposition, modulo arithmetic, and by decision box 33, decision box 38 is entered to determine combinations of these operations. Unfortunately, hashing if the record pointed to has expired. This is determined by functions generally do not produce unique locations in the comparing some portion of the contents of the record to hash table, in that many distinct keys map to the same some external condition. A timestamp in the record, for location, producing what are called collisions. Some form of 10 example, could be compared with the current time-of-day collision resolution is required in all hashing systems. In value maintained by all computers. Alternatively, the occurevery occurrence of collision, finding an alternate location rence of an event can be compared with a field identifying for a collided record is necessary. Moreover, the alternate that event in the record. In any case, if the record has not location must be readily reachable during future searches for expired, decision box 39 is entered to determine if the key the displaced record. 15 in this record matches the search key. If it does, the address A common collision resolution strategy, with which the of the record is saved in box 40 and box 41 is entered. If the present invention is concerned, is called external chaining. record does not match the search key, the procedure Under external chaining, each hash table entry stores all of bypasses box 40 and proceeds directly to box 41. In box 41, the records that collided at that location by storing not the the procedure advances forward to the next record in the records themselves, but instead a pointer to the head of a 20 linked list and the procedure returns to box 33. linked list of those same records. Such linked lists are If decision box 38 determines that the record under formed by storing the records individually in dynamically question has expired, box 42 is entered to perform the allocated storage and maintaining with each record a pointer on-the-fly removal of the expired record from the linked list to the location of the next record in the chain of collided and the return of the storage it occupies to the system storage records. When a search key is hashed to a hash table entry, 25 pool, as will be described in connection with FIG. 4. In the pointer found there is used to locate the first record. If the general, the remove procedure of box 42 (FIG. 4) operates search key does not match the key found there, the pointer to remove an element from the linked list by adjusting its there is used to locate the second record. In this way, the predecessor's pointer to bypass that element. (However, if "chain" of records is traversed sequentially until the desired the element to be removed is the first element of the list, then record is found or until the end of the chain is reached. 30 there is no predecessor and the hash table array entry is Deletion of records involves merely adjusting the pointers to adjusted instead.) On completion of procedure remove bypass the deleted record and returning the storage it occuinvoked from box 42, the search table procedure returns to pied to the available storage pool maintained by the system. box 33. Hashing techniques have been used classically for very It can be seen that the search table procedure of FIG. 3 fast access to static, short term data such as a compiler 35 operates to examine the entire linked list of records of which symbol table. Typically, in such storage systems, deletions the searched-for record is a part, and to remove expired are infrequent and the need for the storage system disappears records, returning storage to the storage pool with each quickly. In some common types of data storage systems, removal. If the storage pool is depleted and many expired however, the storage system is long lived and records can become obsolete merely by the passage of time or by the 40 records remain despite such automatic garbage collection, then the insertion of new records is inhibited (boxes 76 and occurrence of some event. If such expired, lapsed, or obso77 of FIG. 5) until a deletion is made by the delete procedure lete records are not removed from the system, they will, in (FIG. 7) or until the search table procedure has had a chance time, seriously degrade the performance of the retrieval to replenish the storage pool through its on-the-fly garbage system. Degradation shows up in two ways. First, the presence of expired records lengthens search times since 45 collection. Though the search table procedure as shown in FIG. 3, they cause the external chains to be longer than they implemented in the APPENDIX as PASCAL-like otherwise would be. Second, expired records occupy pseudocode, and described above appears in connection dynamically allocated memory storage that could be with an information storage and retrieval system using the returned to the system memory pool for useful allocation. Thus, when the system memory pool is depleted, a new data 50 hashing technique with external chaining, its on-the-fly removal technique while traversing a linked list can be used item can be inserted into the storage system only if the anywhere a linked list of records with expiring data appears, memory occupied by an expired one is reclaimed. even in contexts unrelated to hashing. A person skilled in the Referring then to FIG. 3, there is shown a flowchart of a art will appreciate that this technique can be readily applied search table procedure for searching the hash table preparatory to inserting, retrieving, or deleting a record, in accor- 55 to manipulate linked lists not necessarily used with hashing. dance with the present invention, and involving the dynamic The search table procedure shown in FIG. 3, implemented removal of expired records in a targeted linked list. Starting as pseudocode in the APPENDIX, and described above in box 30 of the search table procedure of FIG. 3, the search traverses the entire linked list removing all expired records key of the record being searched for is hashed in box 31 to as it searches for a key match. The procedure can be readily provide the subscript of an array element. In box 32, the hash 60 adapted to remove some but not all of the expired records, table array location indicated by the subscript generated in thereby shortening the linked list traversal time and speeding box 31 is accessed to provide the pointer to the target linked up the search at the expense of perhaps leaving some expired list. Decision box 33 examines the pointer value to deterrecords in the list. For example, the procedure can be mine whether the end of the linked list has been reached. If modified to terminate when a key match occurs. (PASCALthe end has been reached, decision box 34 is entered to 65 like pseudocode for this alternate version of search table determine if a key match was previously found in decision appears in the APPENDIX.) The implementor even has the box 39 (as will be described below). If so, the search is prerogative of choosing among these strategies dynamically

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 12 of 15

7

8

at the time search table is invoked by the caller, thus 5 begins at staring box 70 from which box 71 is entered. In box 71, the search table procedure of FIG. 3 is invoked with sometimes removing all expired records, at other times the search key of the record to be inserted. As noted in removing some but not all of them, and yet at other times connection with FIG. 3, the search table procedure finds the choosing to remove none of them. Such a dynamic runtime decision might be based on factors such as, for example, 5 linked list element whose key value of the record contained therein matches the search key and, at the same time, how much memory is available in the system storage pool, removes expired records on-the-fly from that linked list. general system load, time of day, the number of records Decision box 72 is then entered where it is determined currently residing in the information system, and other whether the search table procedure found a record with factors both internal and external to the information storage matching key value. If so, box 73 is entered where the record and retrieval system itself A person skilled in the art will 10 to be inserted is put into the linked list element in the appreciate that the technique of removing all expired records position of the old record with matching key value. In box while searching the linked list can be expanded to include 74, the insert procedure reports that the old record has been techniques whereby not necessarily all expired records are replaced by the new record and the procedure terminates in removed, and that the decision regarding if and how many terminal box 75. 15 records to delete can be a dynamic one. Returning to decision box 72, if a matching record is not In FIG. 4 there is shown a flowchart of a remove procefound, decision box 76 is entered to determine if there is dure that removes a record from the retrieval system, either sufficient storage in the system storage pool to accommodate an unexpired record through the delete procedure as will be a new linked list element. If not, box 77 is entered to report noted in connection with FIG. 7, or an expired record that the storage system is full and the record cannot be through the search table procedure as noted in connection 20 inserted. Following that, the procedure terminates in termiwith FIG. 3. In general, this is accomplished by the invoking nal box 75. procedure, being either the delete procedure (FIG. 7) or the If decision box 76 determines that sufficient storage can search table procedure (FIG. 3), passing to the remove be allocated from the system storage pool for a new linked procedure a pointer to a linked list element to remove, a list element, then box 78 is entered where the actual memory pointer to that element's predecessor element in the same 25 allocation is made. In box 79, the record to be inserted is linked list, and the subscript of the hash table array location copied into the storage allocated in box 78, and box 80 is containing the pointer to the head of the linked list from entered. In box 80, the linked list element containing the which the element is to be removed. In the case that the record copied into it in box 79 is inserted into the linked list element to be removed is the first element of the linked list, to which the contained record hashed. The procedure then the predecessor pointer passed to the remove procedure by 30 reports that the record was inserted into the information the invoking procedure has the NIL (sometimes called storage and retrieval system in box 81 and the procedure NULL, or EMPTY) value, indicating to the remove proceterminates in box 75. dure that the element to be removed has no predecessor in FIG. 6 shows a detailed flowchart of a retrieve procedure the list. The invoking procedure expects the remove used to retrieve a record from the information storage and procedure, on completion, to have advanced the passed retrieval system. Starting in box 90, the search table procepointer that originally pointed to the now-removed element 35 dure of FIG. 3 is invoked in box 91, using the key of the so that it points to the successor element in that linked list, record to be retrieved as the search key. In decision box 92 or NIL if the removed element was the final element. (The it is determined if a record with a matching key was found search table procedure of FIG. 3, in particular, makes use of by the search table procedure. If not, box 93 is entered to the remove procedure's advancing this passed pointer in the report failure of the retrieve procedure, and the procedure described way; it is made use of in that box 33 of FIG. 3 is 40 terminates in terminal box 96. If a matching record was entered directly following completion of box 42, as was found, box 94 is entered to copy the matching record into a described above in connection with FIG. 3.) record store for processing by the calling program, box 95 The remove procedure causes actual removal of the is entered to return an indication of successful retrieval, and designated element by adjusting the predecessor pointer so the procedure terminates in terminal box 96. that it bypasses the element to be removed. In the case that 45 FIG.7 shows a detailed flowchart of a delete procedure the predecessor pointer has the NIL value, the hash table useful for actively removing records from the information array entry indicated by the passed subscript plays the role storage and retrieval system. Starting at box 100, the proof the predecessor pointer and is adjusted the same way in cedure of FIG. 7 invokes the search table procedure of FIG. its stead. Following pointer adjustments, the storage occu3 in box 101, using the key of the record to be deleted as the pied by the removed element is returned to the system 50 search key. In decision box 102, it is determined if the search storage pool for future allocation. table procedure was able to find a record with matching key. Beginning, then, at starting box 50 of FIG. 4, the pointer If not, box 103 is entered to report failure of the deletion to the list element to remove is advanced in box 51 so that procedure, and the procedure terminates in terminal box it points to its successor in the linked list. Next, decision box 106. If a matching record was found, as determined by 52 determines if the element to remove is the first element 55 decision box 102, the remove procedure of FIG. 4 is invoked in the containing linked list by testing the predecessor in box 104. As noted in connection with FIG. 4, the remove pointer for the NIL value, as described above. If so, box 54 procedure causes removal of a designated linked list element is entered to adjust the linked list head pointer in the hash from its containing linked list. Box 105 is then entered to table array to bypass the first element, after which the report successful deletion to the calling program, and the procedure continues on to box 55. If not, box 53 is entered procedure terminates in terminal box 106. where the predecessor pointer is adjusted to bypass the 60 The attached APPENDIX contains PASCAL-like element to remove, after which the procedure proceeds, once pseudocode listings for all of the programmed components again, to box 55. Finally, in box 55 the storage occupied by necessary to implement an information storage and retrieval the bypassed element is returned to the system storage pool system operating in accordance with the present invention. and the procedure terminates in terminal box 56. Any person of ordinary skill in the art will have no difficulty FIG. 5 shows a detailed flowchart of an insert procedure 65 implementing the disclosed system and procedures shown in the APPENDIX, including programs for all common hardsuitable for use in the information storage and retrieval ware and system software arrangements, on the basis of this system of the present invention. The insert procedure of FIG.

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 13 of 15

9
description, including flowcharts and information shown in the APPENDIX. It should also be clear to those skilled in the art that other embodiments of the present invention may be made by those skilled in the art without departing from the teachings of the

10
present invention. It is also clear to those skilled in the art that the invention can be used in diverse computer applications, and that it is not limited to the use of hash tables, but is applicable to other techniques requiring linked lists with expiring records.

Appendix Functions Provided The following functions are made available to the application program: 1. insert (record: record_type) Returns replaced if a record associated with record.key was found and subsequently replaced. Returns inserted if a record associated with record.key was not found and the passed record was subsequently inserted. Returns full if a record associated with record.key was not found and the passed record could not be inserted because no memory is available. 2. retrieve (record: record_type) Returns success if record associated with record. key was found and assigned to record. Returns failure if search was unsuccessful. 3. delete (record_key: record_key_type) Returns success if record associated with record_key was found and subsequently deleted. Returns failure if not found. Definitions The following formal definitions are required for specifying the insertion, retrieval, and deletion procedures. They are global to all procedures and functions shown below. 1. const table_size /* Size of hash table. 2. type list_element_pointer ~ t list_element /* Pointer to elements of linked list. 3. type list_element ~ /* Each element of linked list. record record_contents: record_type; next: list_element_pointer /* Singly-linked list. end 4. var table: array [0 ... table_size - 1] of list_element_pointer /* Hash table. /* Each array entry is pointer to head of list. Initial state of table: table[i] ~ nil 'if i 0 ~ i < table_size /* Initially empty. Insert Procedure function insert (record: record_type): (replaced, inserted, full); var position: list_element_pointer;

*/ */ */

*/ */ */ */

dummy_pointer: list_element_pointer; index: 0 ... table_size - 1; begin if search_table (record.key, position, dummy_pointer, index) /* Record already exist? then begin /* Yes, update it with passed record. position i .record_contents := record; return (replaced) end else /* No, insert new record at head of list, if no memory available then return (full) /* if memory available to do so. /* Memory is available for a node. else begin /* Dynamically allocate new node. new(position); /* Hook it in. position i .record_contents := record; position t .next :~ table[ index]; table[ index] :~ position; return (inserted) end /* else begin end /* insert * / Retrieve Procedure function retrieve (var record: record_type): (success, failure); var position: list_element_pointer; /* Pointer into list of found record. dummy_pointer: list_element_pointer; /* Don't need position's predecessor. dummy_index: 0 ... table_size - 1; /* Don't need table index mapped to by hash function. begin if search_table (record.key, position, dummy_pointer, dummy_index) /* Record exist? then begin /* Yes, return it to caller. record := position i .record_contents; return (success) end else return (failure) /* No, report failure. end /* retrieve */

/* Pointer into list of found record, * / /* or new element if not found. * / /* Don't need position's predecessor. */ /* Table index mapped to by hash function. * / */ */

*/ */ */ */ */

*/

*/ */ */ */ */

*/

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 14 of 15

11
-continued
Appendix Delete Procedure function delete (record_key: record_key_type): (success,failure); var position: list_element_pointer; /* Pointer into list of found record. previous_position: list_element_pointer; /* Points to position's predecessor. index: 0 ... table_size - 1; /* Table index mapped to by hash function. begin if search_table (record_key, position, previous_position, index) /* Record exist? /* Yes, remove it. then begin remove (position, previous_position, index); return (success) end else return (failure) /* No, report failure. end /* delete * / Search Table Procedure

12

*/ */ */

*/ */

*/

function search_table (record_key: record_key_type; var position: list_element_pointer; var previous_position: list_element_pointer; var index: 0 ... table_size - 1): boolean; /* Search table for record_key and delete expired records in target list; if found, position is made to point to located record and previous_position to its predecessor, and TRUE is returned; otherwise FALSE is returned. index is set to table subscript that is mapped to by hash function in either case. */ var p: list_element_pointer; /* Used for traversing chain. * / previous_p: list_element_pointer; /* Points to p's predecessor. */ begin index :~ hash (record_key); /* hash returns value in the range 0 ... table_size - 1. * / /* Initialization before loop. * / p :~ table[index]; previous_p := nil; /* Ditto */ position := nil; /* Ditto */ previous_position := nil; /* Ditto */ /* HEART OF THE TECHNIQUE: Traverse entire list, deleting */ while p" nil /* expired records as we search. * / begin if P t .record_contents is expired then remove (p, previous_p, index) /* ON-THE-FLY REMOVAL OF EXPIRED RECORD! */ else begin if position ~ nil then if p t .record_contents.key ~ record_key /* If this is record wanted, * / then begin position := p; previous_position := previous_p end; /* save its position. * / /* Advance to * / previous_p := p; p :~ pt .next /* next record. * / end /* else begin * / end; return (position" nil) /* Return TRUE if record located, otherwise FALSE. * / end /* search_table * / Alternate Version of Search Table Procedure function search_table (record_key: record_key_type; var position: list_element_pointer; var previous_position: list_element_pointer; var index: 0 ... table_size - 1): boolean; /* SAME AS VERSION SHOWN ABOVE EXCEPT THAT THE SEARCH TERMINATES IF RECORD IS FOUND, INSTEAD OF ALWAYS TRAVERSING THE ENTIRE CHAIN. */ var p: list_element_pointer; /* Used for traversing chain. * / previous_p: list_element_pointer; /* Points to p's predecessor. */ begin index :~ hash (record_key); /* hash returns value in the range 0 ... table_size - 1. * / /* Initialization before loop. * / p :~ table[index]; previous_p := nil; /* Ditto */ position := nil; /* Ditto */ previous_position := nil; /* Ditto */ /* HEART OF THE TECHNIQUE: Traverse list, deleting */ while P" nil /* expired records as we search. * / begin if pt .record_contents is expired /* ON-THE-FLY REMOVAL OF EXPIRED RECORD! */ then remove (p, previous_p, index) else begin if p t .record_contents.key ~ record_key /* If this is record wanted, * / then begin /* save its position. * / position := p; previous_position := previous_p; return (true) /* We found the record, so terminate search. * / end; previous_p := p; /* Advance to * / p :~ pt .next /* next record. * /

Case 6:09-cv-00269-LED

Document 1-2
5,893,120

Filed 06/16/2009

Page 15 of 15

13
-continued
Appendix end end; return (false) end

14

/* else begin * / /* Record not found. * / /* search_table * /
Remove Procedure

procedure remove (var elem_to_del: list_element_pointer; previous_elem: list_element_pointer; index: 0 ... table_size - 1); /* Delete elem_to_del t from list, advancing elem_to_del to next element. previous_elem points to elem_to_del's predecessor, or nil if elem_to_del i is 1 st element in list. */ var p: list_element_pointer; /* Save pointer to elem_to_del for disposal. begin p : ~ elem_to_del; /* Save so we can dispose when finished adjusting pointers. elem_to_del : ~ elem_to_delt .next; if previous_elem = nil /* Deleting 1 st element requires changing then table[index1 :~ elem_to_del /* head pointer, as opposed to else previous_elem i .next := elem_to_del; /* predecessor's next pointer. /* Dynamically de-allocate node. dispose (p) end /* remove*j

*/

*/ */
*/ */ */

I claim: 1. An information storage and retrieval system, the system comprising: a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring, a record search means utilizing a search key to access the linked list, the record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed, and means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list. 2. The information storage and retrieval system according to claim 1 further including means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records. 3. A method for storing and retrieving information records using a linked list to store and provide access to the records, at least some of the records automatically expiring, the method comprising the steps of: accessing the linked list of records, identifying at least some of the automatically expired ones of the records, and removing at least some of the automatically expired records from the linked list when the linked list is accessed. 4. The method according to claim 3 further including the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed. 5. An information storage and retrieval system, the system comprising: a hashing means to provide access to records stored in a memory of the system and using an external chaining

technique to store the records with same hash address, at least some of the records automatically expiring,
25

a record search means utilizing a search key to access a linked list of records having the same hash address, the record search means including means for identifying and removing at least some expired ones of the records from the linked list of records when the linked list is accessed, and

30

meals, utilizing the record search means, for inserting, retrieving, and deleting records from the system and, at the same time, removing at least some expired ones of 35 the records in the accessed linked list of records. 6. The information storage and retrieval system according to claim 5 further including means for dynamically determining maximum number for the record search means to 40 remove in the accessed linked list of records. 7. A method for storing and retrieving information records using a hashing technique to provide access to the records and using an external chaining technique to store the records with same hash address, at least some of the records auto45 matically expiring, the method comprising the steps of: accessing a linked list of records having same hash address, identifying at least some of the automatically expired ones of the records, 50 removing at least some of the automatically expired records from the linked list when the linked list is accessed, and inserting, retrieving or deleting one of the records from the system following the step of removing. 55 8. The method according to claim 7 further including the step of dynamically determining maximum number of expired ones of the records to remove when the linked list is accessed.
60

* * * * *