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

Filing 284

Response to CLAIM CONSTRUCTION BRIEF filed by AOL Inc, Amazon.com Inc., Google Inc., Match.Com LLC, MySpace Inc., Softlayer Technologies, Inc., Yahoo! Inc.. (Attachments: #1 Affidavit, #2 Exhibit 1, #3 Exhibit 2, #4 Exhibit 3, #5 Exhibit 4, #6 Exhibit 5-1, #7 Exhibit 5-2, #8 Exhibit 5-3, #9 Exhibit 5-4, #10 Exhibit 5-5, #11 Exhibit 5-6, #12 Exhibit 6)(Chaikovsky, Yar)

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

Doc. 284 Att. 2

EXHIBIT 1

Dockets.Justia.com

BTEX0000I 59

11111

11111111

III

11111

11111

11111

11111

11111

11111

11111

11111

111111

III

11111

liii

USOOS 893 120A

United States Patent
Nemes

Patent

Number
Patent

5893120
Apt
Program Design
Cliffs

Date

of

1999

METHODS AN1 APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL HASHING TECHNIQUE WiTH USING EXTERNAL CHAINING ANI ON-THE-FLY REMOVAL OF EXPIRED DATA
Inventor Richard Michael

R.L

Krusc

Data

Structures Jail

and

Second

Edition
Section

Prentice-WI

Englewood and

New

Jersey 1987 of Uash

ing
UI

6.5 Hashing pp 198215 Stubbs Typcs and

Section

6.6 Analysis

NW

Webre

Data

Structure

with

Abstract

Data

and Pascal

Brooks/Cole
Section

Nemes

1432

F.

35th

Monterey tations Primary

California 1985

Company 7.4 Hased Implemen

Publishing

St

Brooklyn

N.Y

11234-2604

pp 310336
ExaminerThomas ExaminerIlosain
Black

App
Filed

No

775864

Asvistant

Alam

Jan

1997

ABSTRACT
CO6F
707/206 707/1 17/30
in

mt Cl
U.S

method
an

and

apparatus storage

for

performing
is

storage

and
that

retrieval

Cl
of Search

707/100 707/202

information technique
resolution

system
the

disclosed

uses the
for

707/JO
Field

hashing
collision noration

with
In

external to

chaining

method

707/1 707/2

200206
100103

order

prevent

performance
expiring that

dete
data

due

to

the

presence

of automatically technique
is

items References Cited
all

garbage
records

collection stored into

used

removes chain

expired

in the the

system
data

in the

external

targeted

by

probe each

storage

system of

More
record

U.S
5121495 5202981 5287499

PATENT
Nemea

DOCUMENTS
707/3 707/1 707I206

particularly
is

insertion an

retrieval entire

or deletion

an

occasion

to search

linked-list

chain

of records an expired
if

6/1992 4/1993 2/1994

Sliaekelford

for expired data

items and then not remain probed
are

remove
in
it

them Because
system

Nemes

item will
is

the
is

long term

the

system

frequently that

useful

for large require the

information
fast access for

Ot11ER D.E
Sorting

PUBLICATIONS Programming Reading
vol

storage

systems by

heavily

used

Knuth
and

The

An

provided of Computer removal

hashing

and

cannot

be

taken

off-line

of expired data

Searching

MdisonWesley

Massa Claims DrawIng
Sheets

ehusetLs

1973

pp 506549

BTEX0000I

60

U.S Patent

Apr

1999

Sheet

of

5893120

15

FIG

USER

ACCESS SOFTWARE
20

____
GENERAL
UTILITY

OPERATING SYSTEM

SOFTWARE
_________
Ir

SOFTWARE

22

21
r25
APPLICATION

APPLICATION

APPLICATION

SOFTWARE

SOFTWARE

SOFTWARE

FIG

BTEX0000I

61

U.S Patent

Apr

1999

Sheet

of

5893120

FIG

BTEX0000I

62

U.S

Patent

Apr

1999

Sheet

of

5893120

ADVANCE PTR TO ELEMENT
FOLLOWING

ONE TO REMOVE

DE-ALLOCATE
LIST

ELEMENT

TO BE REMOVED

FIG

BTEX0000I

63

US

Patent

Apr

1999

Sheet

of

5893120

FIG

BTEX0000I

64

U.S Patent

Apr

1999

Sheet

of

5893120

-Td

FOR AND RECORD CLEAN TARGET
LIST

SEARCH

FIG

BTEX0000I

65

U.S

Patent

Apr

1999

Sheet

of

5893120

START10
SEARCH-TABLE FOR RECORD AND CLEAN TARGET SEARCH
LIST

102 104

YES REMOVE
DELETE ELEMENT FIG.4

RECORD
FOUND

NO
103

RETURN
FAILURE

RETURN SUCCESS

STOP

--106

FIG

BTEX0000I

66

5893120
METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL hAShING TECHNIQUE WITH USING EXTERNAL CHAINING AND ON-THE-FIN REMOVAL OF EXPIRED DATA
CROSS-REFERENCE TO RELATED
Hall 6.5 Incorporated Englewood
Cliffs

N.J

1987

Section

hashing and Section 6.6 198215 and in Data Structures
by
FL

Analysis
with

of Hashing

pp
4pav

Abstract Data

and Pascal
Publishing

Stubbs

and

Webre
Calif

Brooks/Cole Section 7.4

Company

Monterey

1985

Hashed APPLICATIONS
Not Applicable
10

Implementations

pp 310336
are

Some forms of information
items
their after limited in the

such

that

individual

data

period of time
storage activities the

become
is

obsolete needed
data

and or
that

presence

system
for

no longer
involve

desired Scheduling

example

FEDERAlLY STATEMENT REGARDING OR DEVELOPMENT SPONSOREI RESEARCh
Not Applicable

become

obsolete

once

scheduled item

event has occurred
it

An

automatically-expiring

data

once

expires could

needlessly

occupies
pitt 15

computer

memory
an

storage

that

otherwise be expired items

to

use storing
eventually data

unexpired removed
In to

item

Thus
the

REVERENCE
Not Applicable

TO

MICROFICHE APPENDIX

must

be

reclaim

the

storage

for

subsequent
expired the

insertions in

addition

presence

of many

items results
lists

needlessly

long search
external

times since
will

linked than expired to

associated

BACKGROUND
This invention systems techniques
relates
to

OF THE
information

INVENTION
longer storage to the

with

chaining
is

be

they

otherwise would
the

be The goal
storage

to

remove

and of

retrieval

20

these access

items to reclaim data
is

and maintain fast

and
in

more such

particularly

use

hashing

the

systems
stored in

The problem then
computer-controlled stor
25

to

provide the
heavily data

speed

of access

of stor

Information

or data

hashing age

techniques

for

large

used

information
at

can be retrieved by searching for age mechanism record key value in the stored records The stored matching searching
the storage the search

particular

systems
the

having

expiring

and

the

same time
from
the

with

key Such
into large

prevent

performance of many
dealing

degradation

resulting

key
require to

value

is

then access

retrieved to records In
if

accumulation
technique disclosed that 30 inapplicable there traverses for in

expired records Although with
expiring data issued
is

hashing

techniques mechanism
retrieval efficient requires

repeated

known Jun

and

perform key comparisons such searching such even
as the

U.S
is

Pat

No 5121495
to linear

1992
entirely

storage

and by
often

systems
search

aug

technique
to

confined
external

probing The

and

is

mented search
large

procedures amount

binary

chaining order
table

procedure

shown
of

an excessive

of time due to the

in reverse in the records

consecutive

sequence

number of key comparisons
well-known information of
additional also In called

required
faster

records

residing

hash
to

array continually
left

relocat of

Another
retrieving

and

much

way of
so-called

storing albeit
at

and
the

ing

unexpired ones

fill

gaps

by

the

removal

from computer storage
is

storage

expired

expense technique

the or

hashing
it

Unlike arrays linked
are

lists

leave

no gaps
it

when items from
possible to effi are

scatter-storage

key-transformation operated on by

removed
traverse

and

furthermore
linked
list

is

not

method
hashing

such
to

system produce hash of record
directly

the

key

is

ciently

singly

in reverse

order lhere

function called

storage

address
is

in the large

storage

significant 40 ing that

advantages sometimes

to external
it

chaining over linear method
the

prob
as

space
is

the array

table

which

oneaddress

make

the in

of choice

dis

dimensional then

locations for the

This storage record by

cussed

in considerable techniques

detail

aforementioned with expiring wholly
if

texts data that for arc

accessed
are

desired text

Hashing Knuth

and so hashing do
not

for dealing

techniques
entitled

described

in the

classic

use external
applications considerable

chaining For

prove

inadequate
records

The and

Art

of

Computer

Prograintning

Volume

certain

example
can

the

data

Sorting

Searching

Addison-Wesley

Reading

Mass
universe
the

large

memory
of linear hashing

be

saved

using external
there
is

1973

pp 506549
functions addresses are

chaining instead designed
to translate the

probing
techniques

Accordingly
for external

Hashing of keys hash
into

need with
patent
lists

to

develop

chaining

uniformly hashing and

distributed

throughout

expiring are

data
to

The methods
arrays

of the cannot

above-mentioned with
linked

table

lpical

functions

include

truncation disadvan

limited to the

and

be used

folding
tage

transposition

modulo
than

arithmetic

due

significant

difference

in the

organization

of

of

hashing
in

is

that

more

one

key

will

the inevitably in

computers

memory

translate

the

same

storage

address

causing collisions must therefore
called

storage Some form of collision provided For example which
consists to the of the

BRIEF
In

resolution

be

SUMMARY
with the

OF THE INVENTION
illustrative

simple

strategy

linear from
the
is

accordance
these

embodiment overcome

of

the

probing
initial

searching
first

forward
storage

invention garbage
types

and other

problems

are

by using
other In

storage

address

empty

location

collection access
to

procedure
the storage data

on-the-fly space
are or

while

often

used
method
In for resolving
this

of

taking retrieval

place

Another
nal

eoffisions

is

called

exter
is

particular into 60 fled the

during normal
data

insertion obsolete external records are

probes identi
list
list

chaining
to the translate

technique of
the linked

each
list

hash

table
all

location

store

the

expired
the

records

arc linked

pointer

head under The

of records
to

of whose very hash

and

removed
expired the record

from
or
to

chain
in the

keys
table

hashing
list is

function
itself

that

Specifically including the

obsolete

linked as part

address
retrieving are

linked

searched

sequentially

be

accessed

removed

of

when
deletion

inserting

or deleting pointers

record Insertion
in

and
list

normal

search

procedure garbage
of collection

done

by
is

adjusting discussed

the

linked detail

lhis
65

incremental advantage without
taken

technique

has the unneeded

External

chaining

in considerable

in the

decided
records

automatically that the

eliminating information

aforementioned

text

by

Knuth
Edition

in

Data

Structures

and

requiring fur

storage

sys
is

Program Design

Second

by II

Kruse

Prentice-

tem

be

off-line

sueb

garbagc

collection

This

BTEX0000I

67

5893120
for

particularly requiring

important
rapid access

information

storage to

systems
the user

Central

Processing
controller input

Unit

and continuous

availability

Output
plurality

IO
of

CPU
such
as

10 also

controls

an Input
to

14 that in turn

provides access cathode
devices for ray

population

devices as

CRT
of

tube
as

More

specifically records

method using
at

for

storing
list

and

retrieving

terminal printer puter

information
access cally
list

linked

to the

storc records

and

provide

15 as well 16 lerminal
to introduce of

plurality

output

such

15

provides
instructions

mechanism

com

to

thc

records
is

least

some of
method
at It

automati
the linked

user

expiring of
records

disclosed The
identifies

accesses

computer
other located
10

system

FIG
such
as

and

and commands into the with may be supplemented
tape

and of the
expired

least

some

automatically at least

input

devices

magnetic

readers remotely
types

expired ones
automatically

records ones
is

also

removes

some
list

terminals Similarly
the of

optical printer

readers and 16
the

other

of input
for

of the

records

from the linked
the

devices
displaying

provides
operation of

mechanism
the Printer

when

the

linked

list

accessed

Furthermore

method

results for

of
the

computer 16
ray

provides for dynamically expired ones
list is

determining
to

maximum when

number of
the linked

system
similarly

FIG

computer

user

may
tube

of the

records

be

removed

be supplemented phototypesetters
types

by line printers
laser printers

cathode
graphical

accessed
is

displays and
other

plotters

of output of the
operation

devices computer
are

BRIEF

DESCRIPTION

VIEWS
Aeompletc gained

OF THE SEVERAL oi DIE DRAWING
of the present following
invention

The
their

constituents

system

of

FIG
art

and

asperative of
to
all

well-known

in the

and arc

typical

understanding
the

may be
in 20 puters operation further

computer

systems

from small personal

com
and
not

by considering with the

detailed

large

mainframe systems here
graphical for

systems
are

The

architecture

description in

conjunction

accompanying
general

drawing
diagram which of
the

which
computer

of such
described

well-known

and

will

be

HG
system
storage

shows hardware and

block
in

arrangement system

information might
25

FIG
software

shows
architecture

representation

of such

typical as that user

retrieval

of the present

invention

shown

in

be

HG

computer

system

The

software of

FIG
the

comprises

implemented

FIG
system

access mechanism that for simple personal computers
consist

may
larger

shows
software

general

block
in

diagram
the

of

computer stor

of nothing more providing

than

turning to

system

on

In

arrangement

which

information

systems

service

many
be

users login implemented mechanism
is

and
in

pass
user

age and retrieval

system of the present

invention

might find

word procedures
access mechanism
30

would

typically user

use

20 Once
login

access the user

20
in

has
the

llG
operation

shows
that

general

flow
in

chart

for

table storage

searching system
in

completed
operating coordinates

the

procedure

placed

might be used
the present

hashed

system
the

environment
of
all

21
in

Operating

system components

21

accordance

with

invention
for linked-list the table

activities

of the hardware

HG
remove
operation

shows procedure of

general that

flow chart forms
part

clement

of the

computer
utility

system

shown
for

FIG
use

and
to the

provides computer
basic
file

of

searching

number of
user

programs

22 of general

FIG
general

Utilities

22

might

example

comprise system

HG
operation

shows
that

flow chart
in

for

record insertion
storage

access
facilities

and and

manipulation programming

programs
language of
as

maintenance

might be used
the present

hashed

system

in

compilers

accordance

with

invention flow chart
storage for

The computer
record retrieval
in includes 40 application

software system programs such

FIG

typically

also

HG
operation

shows
for

general

application

software 25

use in

hashed

system

accordance

2324
for

25

Application

software 23 through
editor

might

with the

present

invention
general

and flow
in chart for record storage deletion

example

comprise
spreadsheet

text

document
database

formatting

HG
operation

shows
that

software hashed system
in

program
and
is

management

might he
the

used

system The
storage

game program
present invention
It

so forth concerned with
software

accordance

with

present

invention
identical reference to the

information packages
as

and retrieval
or

lo

facilitate

reader

can be application
parts operating retrieval

understanding
designate

numerals
figures

arc

used

to

elements

common

23-25
access

used

by 20

other or

of the

system 21

such

user

software

system technique

software provided
in

The

information DETAII..ED

storage are

and

by the

II3SCRIPIlON

OF ThE

so

present

invention

herein as

disclosed

as flowcharts

FIGS
in the

INVENTION
FiG
of the drawings shows general block
Central

through

and shown
to
this

PASCAL-like

pseudocode

APPENDIX
diagram of Before
the ss present

specification to
it

proceeding invention
in data

description
is first

of

one embodiment
to discuss

of

computer
ing unit Unit

hardware 10

system

comprising Access
in

Process

useful

CPU

and

Random

Memory
the

11

Computer

programs

stored

RAM
at

RAM
are

hashing and

techniques
retrieving storage

general
are
is

Many known in

fast

techniques

for storing

the prior

art In situations

where

accessed by

by CPU 10 and CPU 10 Data stored

executed
in other

one instruction
portions

time

of

RAM

space

considered
called in

cheap

compared
is

with retrieval used
storage to for In classic

11

are

time hashing
60 includes called

technique each

hashing
the

often

operated from

on by the program

instructions

accessed

by CPU 10
data

record

information unique
as the in value basis as array

system

tAIvl

11

all

in

accordance

with

well-known

distinguished the

field
is

each record
storing

processing
Central accesses digital disk data

techniques Processing
disk stored unit Unit

key
the

which
associated

used

and hash

CPU
unit

10 that

also in

controls accesses

and

retrieving table
is

record

Taken

whole
of

controller

12

turn

large

one-dimensional

logically storage

on one or more 13 until required
are in

disk

storage

units

such

as 65

contiguous units Such of

consecutively
table

numbered
is is

fixed-size stored in

storage

by

CPU 10
from disk

At this time
storage unit

of records each
record

typically

RAM
function

Ill

such

programs

and data and
stored

retrieved

FIG

where
in

an identifiable

and

addres

13 in blocks

RAM

11 for rapid

access

sable

location

physical

memory

hashing

BTEX0000I

68

5893120
translates the into

key

hash
the

table

array

subscript which
for the

is

successful

and

returns

success

in

box 35 followed by
box and

the
is

used
record the
tiled

as

an index into begin
that

array

where can

searches

data

procedures
entered terminates
If

termination failure
is

in terminal returned

37
the

If

not box 36

The

hashing

function

be any operation

on

where
in

procedure

again

key

results the

in subscripts

mostly uniformly hashing modulo
functions

distrib include

box of the

37
list

across

table

Known

the

end

has not

been

reached
is

as

determined determine by
to for

truncation combinations
functions

folding of

transposition

arithmetic

and by decision
if

box

thcsc

33

decision to has

box 38 expired
the

entered
is

to

operations
not

Unfortunately unique keys
locations
to

hashing
in the

the

record

generally in that

do

pointed

This

determined
the record

produce
distinct

hash

table

many
what
is

map

the

same
10 In

comparing

some

portion

of

contents

of
in

location
collision

producing
resolution

are

called in

collisions
all

Some form of
systems
location

some

external

condition he by compared
all

timestamp with
the

the

record
time-of-day the

example could
value

current

required

hashing an

maintained of an event event
in

every
for location the

occurrence
collided

of collision
is

computers compared
In
is

Alternatively

occur

finding

alternate the

rence record

can

he

with
if to

field

necessary reachable

Moreover
during future

identifying

alternate that the

record box 39
the in

must be readily record
collision
is

searches

for

any

case

the

record
if

has not
the

expired
in

decision

entered

determine
If
it

key

displaced

this record

matches
is

search

common
present invention external

resolution
is

strategy called table

with
external entry

which

the

key

does
is

the

address
If

of the record
record

saved

box 40
the

and box 41 search
directly to

entered

the

concerned each
at

chaining
stores
all

does

not

match

Under
the

chaining
collided

hash

of
the

bypasses box 44
the

and proceeds

key the procedure to box 41 In box 41
next record in the

records

that

that

location pointer

by storing
to the

not

records linked

themselves
list

hut instead

head
lists

of
are

procedure
list

advances
the

forward

the to that

20

linked If

and

of

those the

same

records

Such

procedure 38

returns

box
the

33
record to

linked in

decision

box

formed
allocated to the

determines box 42
is

under
the
list

by storing
storage location

records

individually

dynamically
question pointer on-the-fly

and maintaining with each record of the
search there not
is

has

expired

entered record

perform

next record key
is

in

the to the

chain hash
first

of collided
table

removal

of the expired
it

from the linked
to the

records
the

When
found does
to

hashed
to locate

entry
If the

and the return of the storage
25

occupies

system storage

pointer

used
the

record

pool

as

will

be

described

in

connection of box
linked that
first

with

HG

In

search there

key
is

match
the

key

found record

there the
In this

general the
pointer
to

remove

procedure from the
to

42

HG

operates
its if

used

locate
is

second

way

remove

an element
pointer
to

list

the

by adjusting

chain
record

of records
is

traversed the

sequentially

until

the
is

desired

predecessors
the 30 there
is

bypass
is

element element
table

However
array entry

found

or

until involves record

end

of the

chain
the

reached
to

element no

he removed

the

of the list then
is

Deletion of records bypass
the deleted

predecessor

and

the

hash of
table

merely adjusting and
returning the

pointers
it

storage

occu

adjusted

instead from box

On 42
that

completion
the search

procedure procedure

remove
returns to

pied to the available
llashing fast access table techniques to static

storage

pool maintained been term such used
data storage

invoked box
It

by the system
for

have
short in

33
can be
to

classically

very seen
the search table 35 operates the

such

as

compiler
deletions

procedure of records
to

of

11G
expired

examine

the

entire
is

symbol
are

Typically

systems

linked

list

of which

infrequent In

and the need

for the storage types
is

system disappears
storage

searched-for returning If the

record storage

part
to
is

and

remove

quickly

some common

of data long lived passage

systems can
the 40

records removal
records then the

the

storage

pool with and

each

however the storage system become obsolete merely by
occurrence
lete records

and

records

storage despite

pool such

depleted

many

expired

the

of time or by lapsed
or

remain
insertion

automatic
is

garbage

collection

of some event
arc not

If

such from

expired
the

obso
in

of new

records
is

inhibited the

boxes 76 and
procedure chance garbage

removed
the

system they will
of
the

77 of

FIG

until the

deletion search

time system

seriously

degrade

performance up
in

retrieval First the since 45

HG
to

made by

delete

or until the

table

procedure
its

has had
on-the-fly

Degradation of
expired the

shows
records

two

ways

replenish

storage

pool through

collection

presence
they

lengthens
to

search longer

times than

cause

external

chains

be

they

Though

the

search in

table

procedure

as

shown

in

HG

otherwise dynamically
returned
to

would

be

Second memory memory
into the

expired storage

records
that

occupy be

implemented
pseudoeode

the

APPENDIX
above and retrieval

as

PASCAL-like
in

allocated the the

could

and

described storage

appears

connection using the
on-the-fly

system

pool for useful pool
is

allocation

with an information
so

system
its list

Thus

when
be

system memory

depleted system

new
only
if

data the

hashing removal anywhere

technique technique
linked

with

external

chaining
linked

item can

inserted

storage
is

while traversing
list

can

be used appears
in the applied

memory
search ratory

occupied
then

by an
to

expired one
there
is

reclaimed
flowchart table in

of records
to

with expiring person can

data

Referring table to

FIG
for

shown
the

of

even
art

in contexts appreciate

unrelated that

hashing

skilled

procedure

searching

hash

prepa
accor

will

this technique not

be readily

inserting

retrieving

or deleting

record
the

to

manipulate

linked table in entire for

lists

necessarily

used with hashing

dance

with the present

invention
in

and involving
targeted linked

dynamic
as

The

search

procedure
the

shown

in

FIG
all

implemented above

removal
in

of expired records of the search being
table

list Starting the in search

pseudocode
the

APPENDIX
list

and

described

box 30

procedure
for
is

of

HG
In

traverses as 60
it

linked

removing

expired records can be readily records

key

of the record

scarched

hashed box

box
the

31

to

searches to

key match The

procedure
all

provide the subseript
table array
is

of an array
indicated
to

element
the

32

hash
in

adapted
thereby

remove

some

but

not
list

of the expired

location

by

subscript to the

generated
target to linked

shortening the linked
at

traversal

time and speeding

box 31
list

accessed box
the

provide the pointer examines
the

up the search
records in

the

expense For

of perhaps leaving

some

expired

Decision

33

pointer
list

value

deter
If to 65

the

list

mine whether
the

end of the linked reached match
decision

has been
is

reached
entered in decision

modified to terminate
like

example the when key match
alternate

procedure occurs

can

be

PASCALtahl has the even

end

has been
if

box

pseudocode

for

this

version

of search

determine box 39

key
will

was

previously

found
If

appears in the
is

APPENDIX

The

implementor
strategies

as

he

described

below

so

the

search

prerogative

of choosing

among

these

dynamically

BTEX0000I 69

5893120
at

the

time

search

table
all

is

invoked

by

the at
at

caller other other

thus

sometimes removing choosing
decision

removing

expired

records and
yet

times
times

begins at staring bps 70 from which box box 71 the search table procedure of FIG
the search

71
is

is

entered

In

invoked

with
in the

some
to

but

not

all

of them

key with

of

the

record the

to

he

inserted

As noted
finds

remove be

none based
is

of them Such on
factors
in

dynamic

runtime

connection
linked therein
list

FIG
whose
the

search

table

procedure
ceeord

might

such

as

for

example
pool
records other

element

key

value key

of the

contained time
list

how

much memory
system
residing

available

the the

matches expired box
the

search

system

storage

and
where

at

the same
that
it

general currently factors

load
in

time of day
the information

numher of
system and

removes Decision whether

records
is

on-the-fly entered

from

linked

72

then table
If

is

determined
record the

both

internal

and external
itself

to the

information
in the expired to

search

procedure
is

found where

with
record in In the

storage
art

and

retrieval

system
the

person

skilled
all

will

matching
to

key value
is

so box 73
into the

entered
list

be

inserted

appreciate

that

technique linked not the

of removing
list

records position include are replaced terminal

put

linked

element value

of the
insert

old

record

with matching
reports that the the

key
old

box

while searching techniques

the

can

be
all

expanded

74

the

procedure

record

has been
in

whereby
that

necessarily

expired records
if

removed and
records In
to

decision

regarding

and

how many

by the box

new record and

procedure

terminates

75
to

delete there

can
is

he

dynamic

one
Returning of remove system
as

decision

box
is

72

if

matching
to

record
if

is

not
is

FIG

shown
record

flowchart

proce
either will

found

decision storage
list

box

76

entered

determine

there

dure that removes an unexpired noted through with
in

from the
the

retrieval

sufficient

in the

system storage
If
is

pool to accommodate
is

record

through with
table

delete

procedure or an noted

be

new
that 20 inserted nal
If

linked

element system that

not
fall

box and
the

entered record

to

report

connection
the search In

FIG
is

expired
in

record

the

storage

cannot
in

be

procedure

as

connection

Following

the

procedure

terminates

termi

FIG
table

general this
the

accomplished procedure passing
list

by the invoking

box

75
box 76 determines system
is

procedure
search

being either procedure
pointer that to

delete

HG
the to array

or the

decision

that

sufficient

storage

can

FIG
linked predecessor

to

remove

be
list

allocated

from the
then
is

storage

pool for
the

new

linked

procedure
pointer linked to list

element element
table the In

elements

in the

remove same
location
list

element

box 78
In

entered

where

actual

memory
is is

25

allocation

made
the

box

79

the

record to he box

inserted

and the subscript
the pointer
is to

of the
the

hash of

copied entered
record to 30

into In

storage

allocated linked

in
list

78
into

and

box 80

containing

head

linked the case

from
the list

box

80
it

the in

element

containing the linked

the
list

which element
the the

the to

element

to
is

be
the

removed
first

that

copied
the that

into

box 79
record

is

inserted

be removed
pointer

element

of the linked procedure

which

contained
the record

bashed
inserted in

The procedure
into the

then

predecessor invoking
or

passed to the has
the

procedure value
to

ML

remove

by

reports storage terminates

was

information

sometimes
the

called

and

retrieval in

system

box

81

and

the

procedure

NULL
the

EMP1Y
element

indicating

to

remove

proce
in

box

75
detailed record Starting flowchart

dure that
list

the

he

removed

has no predecessor expects advanced now-removed
in that final the the

FIG
used
to retrieval

shows
retrieve

of

retrieve

The
on

invoking completion

procedure
to

remove passed element

from
in

the

information

storage

procedure and

procedure
pointer that
it if

have
to the

originally to the

pointed successor

dure
record
it

of

HG
to

system
is

box

invoked
as

in

box

90 the search table proce 91 using the key of the
key
not
In decision

so that
or

ML

points the

element

linked

list

be

retrieved
if

the

search

box 92
found
to

removed procedure

element of FIG

was

the

element

The
in

is

determined
the

record with procedure
retrieve If

matching box

key was 93
is

search the

table

in particular this

makes use of
the

by
40

search
failure in

table

entered

remove

procedures

advancing
use

passed pointer

described entered

way
directly

it

is

made

of in that box 33 of of box

FIG
as

report
is

of the
terminal
is

procedure

and

the

procedure
record

terminates

box
to

96
copy

If the

following
in

completion with

42

was

matching matching

was
into

descrihed The

ahove

connection

FIG
actual

found box 94
record store to
is

entered

record

for

processing

remove

procedure by element
has the

causes
the

removal

of

the

entered

return

by the calling program box 95 and an indication of successful retrieval
in terminal

designated that the array
it

element
the

adjusting to

predecessor
In

pointer

so
45

the

procedure

terminates detailed

box of

96
delete

bypasses

be removed

the

ease that
table role

HG.7
useful storage

shows
actively

flowchart records Starting search

procedure information

predecessor
entry

pointer

the

NIL value
is

the

hash
the

for

removing system
the

from the
at

indicated

by

passed subscript
adjusted the the

plays

and

retrieval

box

100

the

of the
its

predecessor Following
the

pointer pointer

and

same
storage

stead by

adjustments
is

way in occu
system

cedure of
in

FIG

invokes

table

procedure
to

of

HG
the

pro

box 101

using the key box
able

of the record

be deleted
if

as

pied
storage

removed

element
allocation starting

returned

to

the

seareh key In decision
table

102
to

it

is

determined

the

search

pool for future then
at

procedure box 103 and

was
is

to find

record

with matching of the
in as

key
box by

Beginning
to
it

box 50
is

of

FIG
in

the

pointer

If

not

entered

report

failure

deletion

the

list

element
its

to

remove
in the

advanced
list

box 51

so that box

procedure

the

procedure record remove
in

terminates

terminal

points

to

successor
if

linked to

Next
is

decision
first

106
in

If

matehing box 102
the

was

found
with

determined
is

52
in

determines
the

the

element
list

remove by

the the

element

decision

procedure

of

containing for the to

linked

pointer
is

ML

testing

predecessor
If

box

104

A_s

noted

connection of

FIG FIG
linked
is

invoked remove element
to the

the
list

value
the

as described
list

ahove
pointer

so box 54
in the

procedure from
report
its

causes removal containing
linked

designated

entered array

adjust to

linked the to

head

hash
the

list to

Box

105

then

entered

table

bypass on

first

element
If

after

which
is

successful

deletion

the

calling

program

and

procedure where element again
the to the to

continues

box 55
is

not box
to

entered the 60

procedure

terminates

in terminal

box

106 PASCAL-like

predecessor

pointer

adjusted

bypass

The

attached

APPENDIX
for
all

contains

remove

after

which
in

the

procedure

proceeds

once by

pseudocede necessary system
to

listings

box

55

of the programmed components
storage the will present

Finally
is

box 55 the
to the

storage

occupied
storage

implement
in

an information with
art

and retrieval invention no
difficulty

bypassed
the

element

returned

and

procedure shows
for

terminates detailed in the

system in terminal box of an

pool

operating

accordance
skill

56
procedure
retrieval 65

HG
suitable

My person
implementing
the

of ordinary
the

in the

have

flowchart information

insert

disclosed including

system

and procedures
for
all

use

storage insert

and

system of the present

inveotion

The

procedure

of

HG

APPENDIX
and system

programs

shown in common hard
basis

ware

software arrangements

on

the

of this

BTEX0000I

70

5893120
tO
description
the
It

including

flowcharts

and

information

shown

in

present that the

invention

It

is

also

clear

to

those in

skilled

in the

art

APPENDIX
should
also

invention and
is

can
it

be
is

used

diverse
to the

computcr
of

be clear

to those

skilled

in the

art

that

other those

applications tables
lists

that

not

limited techniques

use

hash
linked

embodiments
skilled in the

of the present
art

invention

may be wade by
from the teachings

but

applicable

to other

requiring

without departing

of the

with

expiring

records

Appendix

Functions

Provided

The

rolling
insert Returns

functions

are

made

available

to

the

application

program

record

record_type
if

replaced

record

associated

with

record.key

was

round

and

subsequently Returns passed Returns record retrieve Returns recorrt Returns delete

replaced
inserted
it

record subseqnently

associated inserted

with

recorstkey

was

not

frund

and

the

record
full if

was

record

associated

with no

recorrtkey

was
is

not

round

arid

the

passed

could

not

be

inserted

because

memory

available

record
success

record
if

type
record associated with reeord.key

was

found

and

assigned

to

failure

if

search

was

unsuccessful

record
success deleted

key record_key_type
if

Returns quently Returns

record

associated

with

record_key

was

found

sad subse

failure

if

not

found
Definitions

tire

following

formal

definitions global to
all

are

required

for

specifying functions

the

insertion

retrieval

and

deletion

procedures
connt rype type

They

are

procedures

and

shown

below
Size of of hash linked linked table list
list

table

.aize list_element Pointer

list_element_pointer
list...elenrent

to elements

rI

element of

record record

contenrs

record_type
/5 Singly-linked
lint

next end
var table

lrnt_etement_poutter

array

table_size

lJ

of

list_element_pointer

I-lash

table of lint

Each
Initial

array

entry

is

pointer

to

bead

state

of

table

tablefi

nil

table_size Insert Procedure

tnitially

empty

function var

insert position

record

record

type replaced

inserted

full
Pointer or into
list

list.element_pointe

of

found
if

record found

new element
positions to

not

dummy_pointer index
begin
if

list_element table aize

pointer fhble

Dont
index

need

predecessor hash function

mapped

by

search_table then begin

recordirey

position

dummy_pointer

index

Record

already passed

exist record
5/

Yea
.reeord_contenla

update

it

with

positiont return

record

replaced

end
else
if

No
available then return

insert /s
if

new

record

at

bead
to fur

of

list so

sI

no memory
else

full

memory
is

available available allocate

do

begin

Memory
record

node node
it

newposition
positiont .record .next contents

Dynamically

new hook

in

position

tablerindex
position

tablr
return

inserted
else /5 Retrieve insert 5/ begin 5/

end end

Procedure

function var

retrieve position

var

record

rordtype

success

failure
Pointer into
list

list_element_pointer list_element_pointer
table size

ot

round

record

durrtmy_poisrer drrmmy._indrx
begin
if

Dont Dont
need
table index

need

positions to

predecessor function

mapped

by hash

search_table then begin

record.key

position

dummy_pointer

dununy

index

Record

exist
caller

Yes
position success
.record

return

it

to

record return

contents

end
else return

failure
retrieve

/5

No

report

failure

end

BTEX0000I

71

5893120
11
-continued

12

Appendix

Delete

Procedure

function var

delete position

record

key record_key_type
elencnt_potnter

succcssinilure
/e /C Table Pointer Points into to
list

Iist_eleinent._potnter ...position
list..

of found

record

Cl 5/

previous

positions to

predecessor
function

index
begin
if

table_size

index

mapped

by hash

search_table then begin

record_key

position

previous_position

index

/5 te

Record Yes

exist
it

si

remove

remove
return

position success

previous_position

index

end
else return

failure
delete

No
Search
Ibble Procedure

report

failure

end

function

search

table var vat var

record
position

key

record_key_type

list_element_pointer
list_element

previous_position inder record_key

_pointer boolean

table_size

Search
point to

table located
is

for

and

delete

expired

records to
its

in

target

list

if

found
is

position

is

made
otherwise

to

record index

and
is

prevtous_position set to table

predecessor and
is

TRUE

returned
in

FALSE
ease
vsr 5/

returned-

subscript

thst

mapped

to

by hash

function

either

list_element

pointer

je

Used
Points

for to

traversing

chain

previous_p
begin index

list

element_pointer

ps predecessor
table_size before Cl

hash

record_keg

hash

returns

value

in

the

range /s

tsbl4indcxj previous_p
position previous_position while nil nil nil

tnitialization

loop
lilto /a Ditto Ditto 5/ 5/ 5/

ps

nil

HttAR1

OP

TI-lIt

TECHNIQUE

Traverse expired

entire records

lint as

deleting 5/

we sesrch

begin
if

pt
then else

.record_cnntenls

is

expired

remove
begin position

previous_p

index

/5

ON-THE-FLY

REMOVAL

OF EXPIRED

RECOI1Dt

if

nil

then

if

p1

.record_contents.key

record_key
/5 If this
is

record

wantedf

then

begin

position

pi

previous_position

previous_p

end
save
its

position to

WI

previous_p
.scxt

/s

Advance
next

record begin

5/

end

/5

else

end
return position nil Return /s Alternate Version

TRUE
table

if

record

located

otherwise

FAISF.

SI

end

search
thble

of Search

Procedure

function

search_table var var var

record_key
position previous

reeord_ key_type list_element_pointer
..position

list_element_pointer boolean

index

table_size

SAME AS VERSION SHOWN ABOVE EXCEPT THAT ITR3 RECORI IS FOUND INSTEAD OP ALWAYS TRAVERSING
var

SEARCH TERMNAEES 1TIE ENTIRE CHAIN
Used
Points for to

IF

lint_element previous_p

pointer

txaverning

chain

list_element_pointer

ps predecessor
table_size before /5 /n 5/

begin index hash

record_key

hash

returns

value

in

the

range

trrble
previous_p
position previous_position while
nil

Initialization

loop
Ditto Ditto Ditto 5/ 5/ 5/ 5/

nil nil nil

/5

hEART OF

TIlE

TECHNIQUE
/5 expired

Traverse records

list as

deleting

we search

begin
if

p1
then else
if

record_contents

is

expired

remove
begin

previous_

index

fS

ON fIB-PLY REMOVAl OF EXPIRED
If thin /5
in

RItCORDI

5/

.record_contents.key then begin

record_key

record
its

wanted5/
position 5/

save

positiott previous return position

previous
/5

true

We

found

the

record

so

terminate

search

5/

end
previous_p
next /s

Advance
next

to

5/ 5/

record

BTEX0000I 72

5893120
13
eontinued

14

Appendix

end

/5

else

begin

5/

end
return

false
/5 aearch.tnble

/5

Record

not

found

end Remove

Procedure

procedure

remove

var

elem

to

dcl

list_element.pointer

previous_elem index
/5 Delete

list_element_pointer

table_size

dent_to_del

from

list

advancing
nil if

elem_to_del
is

to

next

element
in

previous_clem

points

to

elem_to_dels
var begin

predecessor

or

etem_to_delt

element Save

lisL/
to

list_element_pointer

pointer

elem_to_del

ror

disposal

elem_to_del cleat_to_del
ir

/5

Save

so

we

can

dispose

wben

tmnisbcd

adjusting

pointers

dent
nil

to

deif

next
/a Deleting

previous_elem
then else

element head
/5 ja

requires as

changing opposed
pointer to 5/ 5/

tahl4index previous_elemf

dent
next

to

del

pointer

elem_to_del

predecessors

next

dispose

Dynamically

dc-allocate

node

end

rcmove/

claim

technique
storage

to

store

the the

records

with same hash
automatically search the

address

An

information

and retrieval

system

the

system
25

at

least

some of

records

expiring key
to access

comprising
linked
in list

record linked

search means
list

utilizing

to store

and provide access
at

to

records the

stored records the

of records

memory

of the system expiring means
utilizing

least

some of

having
including

same hash means

address

record search and removing
at

automatically record linkcd the record search list search

means
least
list

for identifying of the records
list is

search

key

to access

the
311

some expired ones when
the

from

the

linked

of records

linked

means
at

including

means
the

for identifying

acce.ssed

and
the

and

removing from and

least

some of
list

expired ones
the linked

of the
list is

meals

utilizing

record search
records
at

means

for

inserting

records

the

linked

when

retrieving the

and

deleting

from the system

and

at

accessed

same time removing
records in the

least linked

some expired ones of
list

means
the

utilizing linked
list

the

record
at

and

the

search means for accessing same time removing at least

the

accessed

of records according deter
to

The information
to

storage

and retrieval

system

some of
list

the

expired ones

of the

records

in the

linked

claim

further

including

means
for the
list

for record

dynamically
search

mining
storage

maximum
in the

number

means

The information
to

and retrieval

system according dynamically search deter
to

40

remove

accessed
for storing

linked

of records information
to the the records records records auto-

claim

further

including

means
for the
list

for record

method using hashing

and retrieving
to

mining remove

maximum
in the

numher

means

technique

provide access

accessed
for storing
list to

linked

of records information
to the records

and using an external with same hash
matieally

chaining technique
at least

to store the the

method using
at

and retrieving

address
the

some of

records steps

linked

store

and provide access
automatically

records
the

least

some

expiring

method
list

comprising
records

of
hash

of

the the

records steps
list

expiring

method

comprising
the

of
records
automatically expired

accessing address

linked

of

having

same

accessing identifying

linked

of

at least

some
and

of the

ones
so

identifying

at

least

some of

the

automatically

expired

ones

of the removing
records

of the removing
records

records
at

records
at least the

least the

some
linked

of

the
list

automatically

expired
list is

some
linked

of

the
list

automatically

expired
list is

from

when

the

linked

from and

when

the

linked

accessed The
step

accessed according
to

method

claim

further

including

the

inserting the

retrieving

or

deleting the to step

one

of

the

records

from

of

dynamically of the

determining
to

maximum when
the

number of
linked
list

system

following according

of removing
further including the

expired ones
is

records

remove

The method
step

claim

accessed

of

dynamically ones of the

determining
records to

maximum when
the

number
linked

of
list

An

information storage

and retrieval

system

the

system

expired
is

remove

comprising hashing

accessed

means
of the

to

provide access

to

records

stored

in

60

memory

system

and using an external

chaining

BTEX0000I

73