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

Filing 846

Additional Attachments to Main Document: #845 MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed) MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed) MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed) MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed) MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed).. (Attachments: #1 Exhibit 13 - U.S. Patent 5,893,120 - PX-1, #2 Exhibit 14 - 1996 NRL IPv6 code key.c - DX-36, #3 Exhibit 15 - NRL Source Code - key.h - DX-35, #4 Exhibit 16 - Information Disclosure Statement - 6/2010 - DX-147C, #5 Exhibit 17 - Information Disclosure Statement -12-2010 - DX-147E, #6 Exhibit 18 - Transaction History for Patent Application - DX-147G, #7 Exhibit 19 - USPTO Notice of Intent to Issue - DX-147F, #8 Exhibit 20 - Ex Parte Reexamination Certificate for the '120 Patent - DX-147H, #9 Exhibit 21 - US. Patent 5,287,499 - DX-66, #10 Exhibit 22 - Telcordia documents re: patent application - DX-56, #11 Exhibit 23 - Yahoo!'s 2004 10K Annual Statement - PX-248)(Doan, Jennifer)

Exhibit 13

PX-1
6 :09-cv-269-LE D

BTEX0000159

II11I1

United States Patent

fI9J

Nemes
MKfHODS AN)) APPARATUS FOR
INFORMATION STORAGE AND RETRIEVAl.
USING A HASHING TECHNIQUE WITH
EXTERNAL CHAINING AN)) ON-THE-FLY
REMOVAL OF EXPIRED DATA

f76]

Inventor:

[21]

App!. No.: 775;864

[22]

Filed:

RJchard Michael Nemes, 1432 E. 35th
S1., Brooklyn, N.Y. 11234-2604

Jan. 2, 1997
6

Int. CI. ...................................................... G06F 17/30
U.S. CI. .............................. 707/206; 7(J7/1; 707/100;
707/10l; 707/202
Field of Search ................................ 70711,200--206,
707/2, 100--103

f58]
[56J

Referencl."S Cited
U.S. PATENT DOCUMENTS

5,121,495
5,202,981
5,287,499

USOO5893120A

[11)

[45]

[54]

[51]
[52J

1111111111111111111111111111111111111111111111111111111111111

6/1992 Nemes ........................................ 707/3
4/1993 Shackelford ................................ 707/1
2/1994 Nemes .................................... 7071206

OUIER PUBLICATIONS
DE Knuth, The Art of Computer Programmin& vol. 3,
Sorting and Searching, Addison-Wesley, Reading, MassachusetL.. , 1973, pp. 506--549.

Patent Number:
Date of Patent:

5,893,120
Apr. 6, 1999

R.L. Kruse, Data Structures and Program Design, Second
Edition, Prentice-llall, 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.
Primary Examiner-:lllOmas G. Black
Assi'i[ant Examiner-Hosain T. Alam

[57)

ABSTRACT

A method and apparatus for performing storage and retrieval
in an information storage system is discloscd 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 in-.ertion, 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 u.-.eful for large information
storage systems that arc heavily used, require the fast access
provided by ha.·.,hing, and cannot be taken off-line for
removal of expired data.
8 Claims, 6 Dr.twing Shccts

BTEX0000160

u.s. Patent

Apr. 6, 1999

5,893,120

Sheet 1 of 6

15

RANDOM
ACCESS
MEMORY

1

INPUTCENTRAL
DISK
OUTPUT t+-+-Jl-'t1ul.Il:::;SINGI-+--+-I CONTROL ........+-1
UNIT
UNIT
14

10

PRINTER

FIG. 1

6

USER
ACCESS
SOFTWARE

20

OPERATING
SYSTEM
SOFTWARE

GENERAL
UTILITY
SOFTWARE

22

21

APPLICATION
SOFTWARE
1

APPLICATION
SOFTWARE

...... ... __ .

...... -

2

"'

25

APPLICATION
SOFTWARE
N

24

23

FIG. 2

BTEX0000161

u.s. Patent

Apr. 6, 1999

5,893,120

Sheet 2 of 6

J---30

HASH
SEARCH

31

GET HEAD
OF TARGET

32

KEY

LIST

YES

34

NO
36

RETURN "---35
SUCCESS
SAVE
POINTER TO
LIST ELEMENT

NO

REMOVE
REMOVE
RECORD

RETURN

FAILURE

---37

(FIG. 4)

ADVANCE TO
NEXT
ELEMENT

41

FIG.3

BTEX0000162

u.s. Patent

Apr. 6, 1999

START

Sheet 3 of 6

5,893,120

~50

51
ADVANCE PTR
TO ELEMENT
FOLLOWING
ONE TO REMOVE

NO

YES

53
ADJUST
PREDECESSOR'S
PTRTO
BYPASS ELEMENT

ADJUST
HEAD PTRTO
BYPASS
ELEMENT

DE-ALLOCATE
LIST ELEMENT
TO BE REMOVED

STOP

56

FIG. 4

BTEX0000163

u.s. Patent

Apr. 6, 1999

5,893,120

Sheet 4 of 6

YES
PUT RECORD
IN LIST ELEMENT
RETURNED BY
SEARCH·TABLE

YES

73

78

RETURN
FULL

RETURN

REPLACED

ALLOCATE
NEW LIST
ELEMENT

79
COpy RECORD
INTO NEW
LIST ELEMENT

o
INSERT NEW
LIST ELEMENT
INTO TARGET
LIST

1

RETURN

INSERTED

STOP

-75

FIG. 5
BTEX0000164

u.s. Patent

Apr. 6, 1999

5,893,120

Sheet 5 of 6

START ~90
SEARCH-TABLE
SEARCH FOR
RECORD AND
CLEAN TARGET
LIST

YES

COpy
RECORD

RETURN
SUCCESS

RETURN
FAILURE

STOP

FIG. 6

BTEX0000165

u.s. Patent

Apr. 6, 1999

5,893,120

Sheet 6 of 6

~100

SEARCH-TABLE
SEARCH FOR
RECORD AND
CLEAN TARGET
LIST

102
YES

NO

103

REMOVE
DELETE
ELEMENT
(FIG. 4)

RETURN
FAILURE

RETURN
SUCCESS

STOP

106

FIG. 7

BTEX0000166

5,893,120

1

2

METHODS AND APPARATUS FOR
INFORMATION STORAGE AND RETRIEVAl.
USING A HASHING TECHNIQUE WITH
EXTERNAL CHAINING AND ON·THE-FLY
REMOVAL OF EXPIRED DATA

Hall, Incorporated, Englewood ClifTs, N.J., 1987, Section
6.5, "IIashing," and Section 6.6, "Analysis of Hashing," pp.
198~215, and in Data "·;tructures 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
de.<;ired. Scheduling activities, for example, involve data that
become obsolete once the seheduled event has occurred. An
automatically-expiring data item, oncc 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. 'lbe goal i<; 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 infonnation storage systems having expiring data and, at the same time,
prevent the performance degradation resulting from the
aecumulation of many expired records. Although a hashing
technique for dealing with expiring data is known and
di<;closed 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 furthennore it is not possible to efficiently traverse a singly linked list in reverse order. 'Ibere 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 texl<;,
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. 'lbe 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.

5

CROSS-REFERENCE TO RELATED
APPLICATIONS
Not Applicable
10

STATEMENT REGARDING FEDERALLY
SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable
BACKGROUND OF THE INVENTION

15

This invention relate.<; to information storage and retrieval 20
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 !;tored records. The stored record with a key 25
matching the search key value is then retrieved. Such
searching techniques require repeated access to records into
the storage mechani<;m to pcrfonn key comparisons. In large
storage and retrieval systems, such searching, even if augmented by efficient search procedures such as the binary 3()
search, often requires an excessive amount of time due to the
large number of key compari<;ons required.
Another well-known and much faster way of storing and
retrieving information from computer storage, albeit at the ]5
expense of additional storage, is the so-called "hashing"
technique, also called seatter-storage or key-transfonnation
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 one- 40
dimensional array of record locations. 'Ibis storage address
is then acccssed directly for the desired record. Hashing
techniques are described in the classic text by D. E. Knuth
entitled The Art of Computer Programmin& Volume 3,
Sorting and Searching, Addison-Wesley, Reading, Mass., 45
1973, pp. 506-549.
Hashing functions are designed to translate the universe
of keys into addresses unifonnly distributed throughout the
hash table. 'lypical hashing functions include truncation,
folding, transposition, and modulo arithmetic. A di<;advan- 50
tage of hashing is that more than one key will inevitably
translate in the same storage address, causing "colli<;ions" in
BRIEF SUMMARY OF 111E INVEN'llON
storage. Some form of collision resolution must therefore be
provided. For example, the simple strategy called "linear
In accordance with the illustrative embodiment of the
probing," which eonsisl<; of searching forward from the 55 invention, these and other problems are overcome by using
a garbage collection procedure "on-the-lly" while other
initial storage address to the first empty storage location, is
types of access to the storage space arc taking place. In
often used.
particular, during normal data insertion or retrieval probes
Another method for resolving collisions is called "exterinto the data store, the expired, obsolete records are identinal chaining," In this technique, each hash table location is
a pointer to the head of a linked li<;t of records, all of whose 60 lied and removed from the external chain linked list.
Specifically, expired or obsolete records in the linked list
keys translate under the hashing function to that very hash
including the record to be accessed are removed as part of
table address. The linked list is itself searched sequentially
the nonnal search procedure.
when retrieving, inserting, or deleting a record. Insertion and
'Ibis incremental garbage collection technique has the
deletion are done by adjusting pointers in the linked list.
External chaining is discussed in considerable detail in tbe 65 decided advantage of automatically eliminating unneeded
records without requiring that the information storage sys-"
aforementioned text by D. E. Knuth, in Data Structures and
tem be taken off-line for such garbage collection. Tbi<; is
Program Design, Second Edition, by R. L Kruse, Prenticc-

BTEX0000167

5,893;120

3

4

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 reeords using a linked list to store and provide
access to the records, at le<L-<;t 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 record<; from the linked Ii<;t
when the linked list is accessed. Furthermore, the method
provides for dynamically determining maximum numher of
expired ones of the records to be removed when the linked
list is accessed.

Central Processing Unit (CPU) 10 also controls an Input!
Output (I/O) controller 14 that, in tum, provides access to a
plurality of input devices such as CRT (cathode ray tube)
terminal 15, as well <L-<; a plurality of output devices such as
5 printer 16. 'Ierminal 15 provides a meehanism for a compuler user to introduce instructions and commands into the
computer system of FIG. 1, and may be supplemented with
other input devices such ao; magnetic tape readers, remotely
located terminals, optical readers, and other types of input
!O devices. Similarly, printer 16 provides a mechanism for
displaying the results of the operation of the computer
system of HG. 1 for the computer user. Printer 16 may
similarly be supplemented by line printers, cathode ray tube
displays, phototypesetters, laser printers, graphical plotten;,
15 and other types of output devices.
BRIEF DESCRIPTION OF TIlE SEVERAL
The constituents of the computer system of FIG. 1 and
VIEWS OF TIlE DRAWING
their cooperative operation are well-known in the art and are
typical of all computer systems, from small personal comAcomplete understauding of the present invention may be
puters to large mainframe systems. 1be 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 a(Chitecture 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 acce..<;s mechanism that, for simple personal computers, may
PIG. 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 scrvice 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
BG. 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 compuler 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 JiIG. 2 typically also
accordance with the present invention;
40 includes application programs such as application software
FIG. 6 shows a general flow chart for a record retrieval
23, 24, ... , 25. Application software 23 thwugh 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 understauding, 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 DESCRIPIlON OF mE
3 through 7, and shown as PA'iCAL-like pseudocode in the
INVENTION
APPENDIX to this specification.
1<1G. 1 of the drawings shows a general block diagram of
Before proceeding to a description of one emhodiment 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 h<L-'>hing 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
Central Processing Unit (CPU) 10 also controls and
retrieving the associated record. Taken as a whole, a hash
accesses a disk controller unit 12 that, in tum, accesses a
table is a large, one-dimensional array of logically
digital data stored on one or more disk storage units such as
contiguous, consecutively numbered, fixed-size storage
disk storage unit 13 until required by CPU 10. At thi<; time, 65 units. Such a table of records is typically stored in RAM 11
such programs and data are retrieved from disk storage unit
of FIG. 1, where each record is an identifiable and addres13 in block" and stored in RAM 11 for rapid access.
sable location in physical memory. A hashing function

BTEX0000168

5,893,120

5

6

translates the key into a hash table array subscript, which is
successful and returns success in box 35, followed by the
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 hegin. The ha<;hing function can be any operation on
entered where failure is returned and the procedure again
the key that rcsulL-; in subscripts mostly unifmmly distrihterminates 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. Ihis i" determined by
Cunctions generally do nol produce unique locations in the
comparing some portion of the contents of the record to
hash tahle, 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 i" necessary. Moreover, the alternate
that event in the record. In any case, if the record has not
location mllst 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 scarch key. If ii docs, the address
A common collision resolution strategy, with which the
of the record is saved in box 40 and box 4l is entered. If the
present invention i" concerned, i" called external chaining.
record docs 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 arc
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 tbe next record in the chain of collided
records. When a search key is hashed to a hash table entry, 25 and the return of the storage it oC('"Ilpies to the system storage
pool, as will be described in connection with FIG. 4. In
the pointer fonnd there is used to locale 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 clement. (However, if
"chain" of records is traversed scquentially until the desired
record is found or until the end of the chain is reached. 30 the element to be removed is the first clement of the li"t, then
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
Ii can be seen that the search table procedure of HG. 3
fast access to static, short term data such as a compiler 35
operates to examine the entire linked list of records of which
symhol 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 arc 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-fiy 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 i., 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 PIG. 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.
The search table procedure shown in FIG. 3, implemented
dance with the present invention, and involving the dynamic
removal of expired records in a targeted linked list. Starting
as pseudocode in the APPENDIX, and described above
traverses the entire linked list removing all expired records
in box 30 of the search table procedure of FIG. 3, the search
as it searches for a key matcb. The procedure can be readily
key of the record being searched for is ha<;hed in box 31 to
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. (PA.<iCALthe end has been reached, decision box 34 t<; entered to 65 like pseudocode for this alternate version of search table
appears in the APPENDIX.) Ihc implementor even has the
determine if a key match was previously found in decision
prerogative of choosing among these strategies dynamically
box 39 (as will be described below). If so, the search is

BTEX0000169

5,893,120

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 pfOcedure of FIG. 3 i., 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
ehoosing 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 (ecord 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 extemalto 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 clement 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 heen
techniques whereby not necessarily all expired records arc
replaced by the new record and the procedure terminates in
removed, and that the decision regarding if and how many
terminal box 75.
records to delete can be a dynamic one.
15
Returning to deci.,ion 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 kl he 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 clement containing the
which the element is to be removed. In the case that tbe
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 report<; 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 he 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 clement 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
de..<;eribed 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
de..<;eribed 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 o[ 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 subseript plays the role
storage and retrieval system. Starting at box 100, the proo[ the predecessor pointer and is adjm;ted 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 ofthc record to be deleted as the
pied by the removed element is returned to the system 50 seareh key. In decision box 102, it is determined if the search
storage pool [or 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 terminate..<; 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 PI G. 4 is invoked
in the containing linked list by testing the predecessor
in box 104. A<; noted in connection with HG. 4, the remove
pointer [or 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 it., 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 i<; returned to tbe system storage pool
system operating in accordance with the present invention.
and the procedure terminates in terminal box 56.
Any person o[ 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
suitable for use in the information storage and retrieval
the APPENDIX, including programs for all common hardsystem of the present invention. 'Ine in.,<;ert procedure of FIG.
ware and system software arrangements, on the basis of this

BTEX0000170

5,893,120
9

10

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

present invention. It is al'>O 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 availahle to the applimtion progrnm:
1. insert (record: record_type)
Returns replaced if a record a.soci.ted with r"",rd.key was found and
subsequently replaced.
Returns inserted if a record associated with record.key was not round and the
passed record wa.< subsequelltly inserted.
Returns full if" record associated with record.key was not found and the passed
record could not be inserted because DO memory is available.
2. retrieve (record: record .. type)
Returns SUCCess if record •••oc;.ted with record.key W3.< rOllnd .nd assigned to
record.
Returns failure if search was unsuccessful.
3. delete (record. key: rccordJey._typc)
Returns success if record ass<x:iated with record . ..key was found and subsequently deleted.
Returns failure if not found.
Definitions
'lbe following formal definitions are required for specifying the insertion, retrieval, and deletion
procedures. They are global to all procedures and functions shown below.
f* Size of bash table.
1. const tabl" . ..siz.c
Pointer to elements of linked list.
2" type list_element_pointer ~ 1 list_element
3. type list ...clement ~
/" Each element of linked list.
record
record .conten!s: record _type;
neJ[t: Jist_dcment-pointcr
1* Singly-linked list.
end
4. var table: array [0 ... table.. _size - 1J of list_elemenLpointer
Hash table.
Eaeh array entry i. pointer to head of list.
Initial stale of table: tablefi] m nil Vi 0 ,; i < tableJi7.e
/. Initially empty.
Insert Procedure

r

r

'*

function insert (record: record ,type): (replaced, inserted, full);
var position: lisL ..elcmc:nt_pointer,

*/
*/

0'

*f
Of

*'

"'

'*

" Poinler into list of found record, "'
Or new element if not fOWld. */
/* Don't need position'. predecessor. *f
f* ·Thble index mapped to by hash function.•f

dummy-pointer: list_element pointer;
index: 0 ... table ..size - 1;
begin
if seareh."_table (record.key, position, dummy_pointer, index)
then begin
positiont .recOld_contents :~ "'-COrd;
return (replaced)
end
else
if no memory available then return (full)
else begin
new(position);
po.ition t .record contents:= record;
po.ition t .next :~ table[ index];
tablc[indcxJ :- position;
return (inserted)
end
end
f* insert
Retrieve Procedure

*'

fO Record already exist?
'" Yes, update it with passed record. *f

1* No, insert new record at head of lis!, .,
1* if memory .vailahle to do so.
f* Memory is available for a node.
Dynamically allocate new node. f
Hook it in.•,

'*

'*

'*

*'

*'
*'
*

else begin .,

function retrieve (var record: record. .,lype): (success, failure);
,. P"int.er into list of found record.•,
vaf position: lisl_elemenLpointer;
durnmy-pointer: list_clement_pointer,
Don'l need position's predecessor.
durnmy.-'ndex: 0 ... table size - 1;
f" IJon'l need ~~ble index mapped to by hash function.

'*

begin
if """reLlable (record key, position, dummy_pointer, dummy index)
then begin
record ~= position f .record l."tmlcnts;
return (success)
end
else return (failure)
f* retnL"Vc */
end

r

'*

*'
*'
*'

Record <",~,t?
Yes, return it to caller. */

'*

No, R1"'rt failure. '.j

BTEX0000171

5,893,120

11

12
-continued
Appendix
Delete Procedure

funclion delete (reconL_ key: record_key_type): (success,wilure);
vat position: list_eleiIlcnl._pointer;
previous ___ position: lisL clcment-pointer;
index: 0 . __ lahle_size - 1;

" Pointer into list of found record. "'
" Points to pooition's predecessor. ./
/* Tahlc index mapped to by hash function_ '/

hcgin
ir ""arcLtable (r=rd_key, position, previous_position, index)
then hegin
remove (positi.on, previous_po..o;;itiofi, index);
return (success)
end
else return (failure)
/* delete */
cud
Search Thble Procedure

1* Record exist? ./
/* Yes, remove it. */

r

No, report failure. '/

function search lahle (record _ key: recordJey__ typc;
Vat position: list_dcmenL pointer;
vat previous_posilion: lisl_elerncnl __pointer;
vat index: 0 ... table--"izc - 1): boolean;
/' Search tahle for recordJey and delete expired records in target list; if found, position is made to
point 10 located record and previous_position to its predecessor, and TRUE is returned; otherwise
EAI SE is returned_ index is set to lahle subscript thaI is mapped to by hash function in either
case. */
var 1': lisLelement _
pointer;
Used for traversing chain.
previous_po list elemcnl-pointer;
1* Points to 1". predecessor.
begin
1* hash return. value in the range 0 __ . table--"ize - 1.
index := hash (recordJcy);
p :~ tablc[indexJ;
1* InitialiZation before loop.
previous_p :c:: nil;
'" Ditto
I" Ditto
position := nil;

r

previous_position ~"="\ nil;

while p .. nil

"/
*/
'/
"
.,

./

1* Ditto "'
/" HEART OF Tim TECHNIQUE: Trnverse entire list, deleting */
/. expired records as we search. '/

begin
if pt .recorLcontents is expired
then remove (p, previous-p, index)
/* ON-TIiE-FLY REMOVAL OF EXPIRED RECORD! "'
else begin
if position ~ nil then if pt .record ___ contents.key ~ re~"rdJey
I" If this is record wanted,'/
then begin position :~ p; previous_position :~ previous-p end;
save ita posilion. "/
,. Advance to .,
previuus-p :M P;
p :~ p1 .next
1* ne"t record. "'
end
'* else begin */
end;
1* Return TRUE if record located, olherwise FAL<;K '/
return (posilion .. nil)
search_ .lable */
end
Alternate Version of Search 'lable Procedure

r

r

function scarcLtable (recordJey: recot<L.k.cy_typc;
var position~ 1ist_element_pointer;

var previous __ position'list_element-P"inter;
var index: 0 ... table_size - 1): boolean;
1* SAME AS VERSION SHOWN ABOVllllXCEPT 11IAT Hili SEARCH 'nlRMINATES IF
RECORD IS FOUND, INSTEAD OF ALWAYS TRAVERSING TIlE ENTIRE CHAIN.•,
var p: list_element pointer;
1* Used for traversing chain.
previollS-P: lisLelement_pointer;
Points to p'. predecessor_
begin
1* hash returns value in the range 0 ... table_si7.e - 1.
index :~ hash (record_key);
1* luiliaJization before loop.
p :~ mblc[index];
1* Ditto
previ()us-p :~ nil;

r

position ;:;:;: nil;

previous---position
while p .. nil

:~

nil;

,. Ditto
/" Diuo
/* HEARl' OF WE TECHNIQUE: 'I'rsv,,,,,. list, deleting
1* expired recoId.~ as we search.

'/
*/

"
'/
./

"'

'/
'/
*1

hegin
if pf .record_contents is expired
/. ON-TIlE"FLY REMOVAt.. OF EXPIRED RECORDI '/
then remOve (p, previouL_p, index)
else begin
,. If tbis is record wanted:,
if p f .rccord_coutents.key ~ rccordJeY
1* save ita posilion. "/
then begin
position :~ 1';
previous position: N previouB, ~p;

r.turn (true)
end;
previous_p :- 1';
p :- p1 .next

1* We found the record, so terminate search. '/
,. Advance to "

'" next record. */

BTEX0000172

5,893,120

13

14
-continued
Appendix

end
cnd;
rdum (false)
cnd

1* seareLlable
Remove Procedure

'*

*'

'*

else begin

*'

Reeon\ not found.•,

procedure remove (vaT clem lo del: li$t __clement-pointer;
previous___elem, Iist._element_pointer;
index, 0 ... table_size - 1);
Ddctc c1em_w_dd f from list, advancing elem. __ w_del to next element. previous__eIem points La
cJcJIL.tn_del's predecessor, or nil if eJenLLo_del f is 1"' denlent in list.
var P' JisLelemcnL.pointer;
Save pointer to clcm_to_del for disposal.
hegin
p , ~ dem_tn_del;
1* Save so we can dispose when finished adjusting pointers.
c1effi_tn_del , ~ eIent to. del f .next;
if previous_elem ~ nil
1* Deleting 1" elemenl requires changing
hcad pointer, as opposed tn .,
then table[ index] :- elenl..... to del
else prcvious__eJem f .next :- dem_to_del;
/* predecessor's neAL pointer. */
dispose (P)
Dynamically de-allocate node .• ,
1* remove*!
end

'*

*'

r

,0

*'
*'
*'

'*

I claim:
1. An information storage and retrieval system, the system
comprising:
a linked list to store and provide access to record,; 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
record<; from the linked list when the linked list is
aecessed, 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. 1be 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 acces.<;ed linked list of records.
3. A method for storing and retrieving information records
using a linked Ii';t to store and provide acce.o;s to the record,;,
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. 1be method aecording 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.
S.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

25

30

35

40

45

50

55

technique to store the records with same hash address,
at least some of the records automatically expiring,
a record search meanS utilizing a search key to access a
linked list of reo)rds having the same hash address,
the record search means including means for identifying
and removing at least some expired ones of the record,;
from the linked list of records when the linked list is
accessed, and
meal<;, utilizing the record search means, for inserting,
retrieving, and deleting record,; from the system and, at
the same time, removing at least some expired ones of
the records in the accessed linked list of rccords.
6. The information storage and retrieval system according
to claim S further including means for dynamically determining maximum number for the record search means to
remove in the accessed linked list of records.
7. A method for storing and retrieving information record,;
using a hashing technique to provide access to the records
and using an external chaining technique to store the record,;
with same hash address, at least some of the records automatically expiring, the method comprising the steps of:
accessing a linked list of record,; having same hash
address,
identifying at least some of the automatically expired ones
of the records,
removing at least some of the automatically expired
records from tbe 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.
8. The method according to claim 7 further including tbe
step of dynamically determining maximum number of
expired ones of the records to remove when the linked list
is accessed.

60

* * * * *

BTEX0000173