Refer#n€#~

vft NSS

Publi- : cations

ftX' AlllDM 3bll73

IMRSJR 78-1551

Access Functions for Packed

Scatter Tables

Bruce E. Martin

I

I Systems and Software Division

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D.C. 20234

August 1978

100

.U56

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

r 73-1551

i97B

W0SJ8T Sureao of Sfandards APk i ? ]Q7§

NBSIR 78-1551

an nn - : ACCESS FUNCTIONS FOR PACKED

SCATTER TABLES

Bruce E. Martin

Systems and Software Division

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D C. 20234

August 1 978

I

' ,1 , ; U.S. DEPARTMENT OF COMMERCE, Juanita M. Kreps, Secretary

Dr. Sidney Harman, Under Secretary

Jordan J. Baruch. Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDARDS. Ernest Ambler, Director
mmul ,3t>aiMsfeo^V^

^ 2 ,nMfm ,-: .3..,^ifiaflAay',,^H7i“=ro u'A^’«u'^!fAiftCHtAi^

*).

‘ • Rcjs ' •.^ :'

- ii*-

' ' :,-7«
NBSIR 78-1551

ACCESS FUNCTIONS FOR PACKED

SCATTER TABLES

Bruce E. Martin

Systems and Software Division

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D C. 20234

August 1978

U.S. DEPARTMENT OF COMMERCE. Juanita M. Kreps. Secretary

Dr. Sidney Harman, Under Secretary

Jordan J. Baruch, Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director

0
II 4
TABLE OF CONTENTS

SUMMARY OF THE ACCESS METHOD

USE OF THE ROUTINES

Declarations

Initializations ... Node (De ) al loca t ion

APPENDIX A:

APPENDIX B:

APPENDIX C:

Documentation

Listings of a Sample result

of PASCAL code

ccess routines

s .............

Page

2

5

6

6

7

8

16

21

-i i i-
-if ."M

p

s g.s"-s

'.< .

* -A'

' 1 i

I'H...,

i*

I g».

<

'?*'

«9

’ dSsr:;irv«!*k^,

' ' m..

« I »' r, ^ « » * '• *

•'

,» » >. « * '• i W j;4--« c» « i>- » I*,' » .»

'4' * K* S'HPS^

, .-__f

J f « .1 ' . ( • 1 < * !*.• » r f » »..?'' », » » f

• • t .. .».» ¥ *,>•» « .(,.!?'>,, ji * #.

5a<^‘p ^ ...

Ji: . -

S*iJi

iVi

« 4r“i. ' ••>»'0kn»e

m-'

K?-,

jsi¥" -

'

' ; , i

•v;- ;

,Jt;-

•

^ V:,

;

.. >,5,'

M

'4

, "T ...

» / ^ :>.: M

,® 5>:::.k''*>'
DISCLAIMER

The table functions described in this r written and tested carefully. The possibi

application requires that NBS expressly disc

consequences of using the functions, A pa

must be issued on attempts to speed table ac

indices; such schemes are guaranteed fail

move with new insertions.

epor t ha

1 ity of

la im any

rt icu lar

cess by

ure , s in

ve been

improper

and all

warning

s tor ing

ce items

- 1 -
Access Functions for Packed Scatter Tables

Bruce E. Martin

Three PASCAL access routines are given for

packed scatter tables. INSERT packs tables of integer keys; FIND retrieves the keys; DELETE

deletes keys. While the routines currently access

integer keys (for use in performance testing with

pseudo - random integers), they can easily be converted to access other data types -- character

strings in a symbol table, for example. To

enhance portability, the code is straightforward

PASCAL without any input-output capabilities. Append i ces conta i

specific comments on the

routines. listings. and sample results.

SUMMARY OF THE ACCESS METHOD

Hashing techniques allow insertion and retrieval of

keys by computing a function h(key) and storing the key in

T[h(key)], where T is an indexed table. Since the function

h(key) generally does not compute unique addresses, different keys may "collide". Simple collision-resolving

methods search for an alternate location to store the key

- 2 -
being inserted. But such methods can cause slow retrieval

of keys. More sophisticated methods search for alternate

locations for other keys as well as for the key being inserted. INSERT uses a generalized collision-resolving

method that recursively considers table rearrangement. The

user controls the method to be used with the parameter

DEPTH. Lyon gives a more detailed discussion of the algorithm in [1]. A summary of the method appears here.

Specific comments on the PASCAL code appear in appendix A.

Integer keys are inserted in the scatter table by first

calculating a table address using a primary hash function

(key mod tablesize) . If the slot in the table addressed by

the primary hash function is not occupied, the key is inserted. Otherwise, the cost of displacing the contents of

the slot is calculated by calling the function DISPLACE.

Next, the cost of displacing the key is calculated by a second call of DISPLACE. DISPLACE returns a stack that indicates how the table should be rearranged. The table is

rearranged using the stack returned by the call of DISPLACE

with the least displacement cost.

The function DISPLACE makes

increments of the secondary hash

+1) until an open slot is found,

the search for an open slot is

by recursive calls of DISPLACE.

probes into the table by

step (key mod ( tablesi ze-2)

Each slot probed during

considered for displacement

The recursion terminates

- 3 -
when the deepest level of recursion, as specified by the

user with the parameter DEPTH, is reached or whenever displacement of further slots cannot possibly find a better

solution. The deepest call of DISPLACE returns the additional penalty to probe to the free slot; that is,

PENALTY ( number of probes to free slot) minus PENALTY ( number

of probes to table address), where PENALTY is a forcing

function defined by the user (see [1]). The rearrangement

stack returned by the deepest call of DISPLACE consists of

the table address of the item being displaced and the address of the free slot. At higher levels, the total displacement cost of each subsequent slot is calculated to be

the additional cost to probe to the slot plus its displacement cost, and the minimum is returned. The stack at higher

levels of DISPLACE consists of the address of the item being

displaced and the stack returned from the chosen call of

DISPLACE

A table of counters of search lengths is maintained for

faster rejection of keys not in the table. As keys are inserted, the number of probes to find each key is recorded by

incrementing a counter in the search length counter table,

KICKOUT, where the search length is the index of KICKOUT.

Since key insertion possibly causes other keys to be displaced, thus changing each displaced key's search length,

old and new search lengths of displaced keys are also returned on the rearrangement stack to keep KICKOUT updated

- 4 -
and maintained. When a key is deleted, the appropriate

search length counter is decremented.

Keys are retrieved by first calculating their original

primary hash function and secondary hash step. Next, the

table is probed until the key or an open slot is found or

the number of slots probed equals the maximum search length.

Generally, the performance of retrieving keys in the table

does not improve as keys are deleted. For example, a table

half filled performs much better than a table that is first

completely filled and then has half of its keys deleted. Rejecting keys not in the table improves as keys are deleted

provided deletions cause the maximum search length to decrease. Again, the half-filled table performs better than

the table that is half-deleted. However, as keys are reinserted, both rejection and acceptance improve because insertion of keys causes the table to be rearranged more optimally. See Appendix C for measurements that are typical of

correctly executing functions: Testing of the routines on a new system should give similar results.
USE OF THE ROUTINES

Decl ar at i ons

The following must be declared by the calling program:

const

tablesize {the size of the table into which keys

maxr eal

ki cksize

type

will be inserted. Must be prime!}

(largest real for particular installation. } (size of the search counter table}*

table=array [0 . . tablesi ze-lj of integer;

kicktab= array [-1 .. kicksi ze+1] of integer;

stkptr = stkelmnt"stkelmnt

= record

ind, oldlen, newlen: integer;

next: stkptr

end

var

oldnodes : stkptr; {for node (de ) al locat i on

}

* Kicksi ze should be the expected longest probe for a particular depth, penalty function and table filling. If the estimate of the maximum search length

is too small, the rejection performance of the table

may deteriorate. Therefore, a generous estimate of

kicksize is desirable.

Ini t i al i zat ions

The following

gr am

must be initialized by the calling proVARIABLES WHEN INITIALIZED TO

of type TABLE

OLDNODES

for new table -1

first use of routines nil

- 6 -
of type KICKTAB for new table as follows:

k i ckout [ -1 ]

: =0 ; {no overflow with new table}

ki ckout [ 0 ] ; =1 ; {maximum probes with new table}

kickout{l..kicksize+l] :=0;

Node (De) al location

Since node (de) al location differs from one PASCAL installation to the next, the INSERT routine, in the interest

of portability, explicitly controls node (de) al locat ion for

its rearrangement stack via procedures GETNODE and FREENODE.

The procedures use a global variable OLDNODES, which points

to a linked list of nodes that grows and shrinks during execution.

REFERENCES

[1] Lyon, G.E. "Packed Scatter Tables", Comm . of the ACM

(tentative October, 1978)

[2] Lyon, G.E. "Batch scheduling from short lists",

Information Processing Letters , (to appear)

- 7 -
APPENDIX A: Documentation of PASCAL code

Procedure insert

PARAMETER TYPE

tab table

key integer

depth integer

kickout kicktab

the table in which keys are inserted .

the integer to be inserted.

depth of recursion for displacement.

table of counters of search

lengths, KICKOUT [1 , ,KICKSIZE] are

counters of search lengths, where

the length is the index in KICKOUT,

KICKOUT [0] = longest search length,

KICKOUT [-1] = longest search length

if an overflow occurs,

KICKOUT [KICKSIZE+1] is counter of

overflow search lengths,

KICKOUT [0] traps to KICKSIZE+1 if

overflow ocurs.

VARIABLE TYPE

index integer

primary hash index, TAB [INDEX] is

considered for displacement if a collision occurs,

temp integer

stores the contents of TAB [INDEX]

while displacement of the new key

is being considered,

lenl integer

length of the longest search returned when TAB [INDEX] is considered for displacement.

- 8 -
Ien2 integer

length of the longest search returned when the key is considered

for displacement.

costl real

cost of displacing TAB [INDEX],

cost2 real

cost of displacing the key.

stkl stkptr

rearrangement stack returned when

TAB [INDEX] is considered for displacement.

stk2 stkptr

rearrangement stack returned when

the key is considered for displacement.

LINE NUMBER (S)

142. .144

The primary hash index is calculated.

Another key has search length of 1 so

KICK0UT[1] is incremented. If the slot

is empty or marked deleted, the key is

inserted and INSERT is exited. -1 indicates empty slots; -2 marks deleted

slots

148. .149

The cost of displacing TAB [INDEX] is

calculated provided DEPTH > 0. DEPTH=0

means the key should be inserted in the

first free slot and no displacements occur ,

150. .152

The cost of displacing the key is calculated by temporarily storing TAB [INDEX]

in TEMP. The key is inserted in

tab[index] and DISPLACE is called. This

was designed so that DISPLACE would have

the table address as an parameter

(necessary for recursive calls) and so

INSERT would have the key as a parameter, making table addresses invisible to

the user. Note that with the second

call of DISPLACE, COSTl is the actual

parameter corresponding to the DISPLACE

-9-
formal parameter MAX, This keeps the

second call of DISPLACE from considering

any displacements that are more costly

than the displacement found by the first

call of DISPLACE.

153. .162

If both the key and TAB [INDEX] were considered for displacement, the table is

rearranged by REARRANGE according to the

stack returned by the call of DISPLACE

returning the lower cost. If only the

key was considered for displacement, the

table is rearranged by STK2. Finally,

after table rearrangement, both stacks

are deallocated by FREENODE.

procedure getnode

7. .15

A node is allocated from OLDNODES or by

the pascal function NEW,

procedure f reenode

16. . 27

A linked list

to OLDNODES.

is walked and deallocated

procedure rearrange

30

If the search

greater than

length passed

the current

to it

maximum

IS

in

KICKOUT[0], KICKOUT[0] is updated.

31. .47

Each node in the stack has four fields:

IND,OLDLEN,NEWLEN and NEXT. For each

node: a) OLDLEN and NEWLEN are tested

for overflow. If so, KICKOUT[0] traps to

the overflow counter, b) KICKOUT [NEWLEN]

is incremented and KICKOUT [OLDLEN] is

decremented. c) the contents of

TAB [NEXT" . IND] are moved to TAB[IND], d)

the next node of the stack is used.

When the last node is encountered, the

key is moved to TAB[IND],

- 10 -
function displace

PARAMETER TYPE

index integer

address of item to be considered

for displacement.

depth integer

depth of recursion for which displacement should be considered.

max real

MAX is an upper limit on cost for

displacement consideration. It is

the best solution found so far at

higher levels of recursion.

rjstack stkptr

contains indicies of slots rejected

at higher levels of recursion, A

slot which is rejected at a higher

level of recursion will not lead to

a better solution at a deeper level . stack stackptr

returns the rearrangement stack for

best solution at a given level,

(var parameter)

length integer

returns the length of the longest

search, (var parameter)

VARIABLE TYPE

ind integer

used to calculate subsequent slots

in the table.

probetoind integer

number of probes to hash to

TAB [INDEX]

probetofree integer

number of probes to the first free

slot.

counter integer

slot counter. Used in calculating

subsequent locations to probe the

-11-
table

step

hashl

next

sr chlen

upl im

totcost

pentonext

th isnode

sav r j

bes tack

tstack

integer

equal to the secondary hash function for probing.

integer

equal to the primary hash function

for probing.

integer

integer

address of the next slot

longest search from deeper levels

of recur sion.

real

real

real

s tkptr

s tkptr

the upper

cost at a the minimum

TAB [INDEX]

(the least

levels)

limit on d

given level

of the cos

to a free s cost found

isplacement

. UPLIM is

t to move

lot and MAX

at higher

additional cost of probing to next

slot plus cost of displacing next

slot.

additional cost of probing to next

slot, that is PENALTY (probes to

next slot) - PENALTY (probetoind )

pointer to node pushed on stack.

It is used to update the new search

length

saves a copy of rjstack upon first

execution of DISPLACE,

stkptr

stkptr

saves the stack

PLACE returning

BESTACK is in

higher levels of

returned by DISthe lowest cost,

turn returned to

DISPLACE.

temporary stack for calls of

- 12 -
DISPLACE

LINE NUMBER (S)

84. .95

The primary and secondary hash functions

are calculated. Slots are probed to

find the number of probes to INDEX and a free slot.

96. .100

INDEX, number of probes to index, number

of probes to free slot are pushed on

STACK as IND, OLDLEN and NEWLEN, respectively. NEWLEN may have to be updated

later if a better solution is found.

Therefore, THISNODE saves the node. So

far, the best solution found is to move

TAB [INDEX] to a free slot so BESTACK is

set to STACK. RJSTACK is saved.

101. .103

The tentative longest search is PROBETOFREE so LENGTH defaults to PROBETOFREE.

The index of the free slot and two dummy

constants are pushed on BESTACK. UPLIM

is the additional cost of probing to the

free slot.

104

If DEPTH=0, no subsequent slots are to

be considered for displacement. The recursion has terminated. The stack with

INDEX and the address of the free slot

is returned. The value of DISPLACE is

UPLIM. Otherwise, subsequent slots are

considered for displacement.

105. .109

If a better solution than UPLIM was

found from a higher level of recursion

then UPLIM is updated. The primary hash

location is the first to be considered

for relocation. The cost to probe to

the first location is PENALTY (1)

PENALTY (probetoind)

110

While the cost to probe to the next slot

is greater than UPLIM, the following is

done

-13-
112. .135

136. .140

procedure push

function member

If the next slot has not already been

considered, it is considered for relocation. If the total cost, TOTCOST, is

lower than the current lowest cost

UPLIM, a better solution has been found

and UPLIM, BESTACK and LENGTH are updated to TOTCOST, TSTACK and SRCHLEN,

respectively. Otherwise, the slot being

considered for relocation is pushed on

the reject stack, RJSTACK. The next

slot to be considered and the additional

cost to probe to it are calculated.

The value of DISPLACE returned is the

UPLIM. BESTACK is returned as the rearrangement stack.

PUSH gets a new node and pushes the arguments I ,OLDLEN,NEWLEN onto the stack.

MEMBER returns true if its integer argument is a member of the stack. Otherwise it returns false.

function penalty

PENALTY is a forcing function defined by

the user. Currently it is linear; it

returns its argument. To force insertion of keys in a different manner the

user must change the forcing function.

function f ind

FIND tries to find the key in the table.

If found, its table location is returned, otherwise -1 is returned. The

variable probes returns the number of

probes to find (or reject) the key.

procedure delete

DELETE finds the key in the table by

calling function FIND, deletes the key

- 14 -
a’-S'^r . ..

i-s^, 'r '''‘iJ^-' »; '"^ v'; and updates KICKOUT accordingly. A js slot

is marked deleted by setting it to ~2.

;

i;.

' '

.i'

' y « ;. C '.

''. '.’X

-' ' ' '<

: - ,-

't.f

'".- yV;> . :t;/

,.- V,"

'• •• '

i.Sift'B.I i/.ni3i , \., :v'^. o.n j, 'i.

,.v ..Ib-^y.,. sVx^^vv.^' h 1''.:^€;x,.-;^ €

-ti i; .V ^ ,

" g

•‘1 ' : B :i<^ - q

\

;-rv,,, i.' '. .. |t £-S, ;+(J ’f

^ \ , >'. < ^}f^^f^ n’Lkii..i i ^

;'«' .•

mm- f. \ ^ XOil'.. ’ S'd' <0 >', b !• @ fiDi'ii’O i-0

,

• * C) s *

.;j>

- f

’ .

. $p. i

'

.'' ' i^?v

' ' ; ^

' > .J

' ns f i '^'iS i. < >'i £ J n,- 5 i

"

. Vii

' ‘''

? lo’^ “ :tX‘iiiili. a .;i ’

- '. - .fjsbonylo

' "

,- :5bJ'o

^pns:i,')EiS«,a 37<^by:;niq

h::#icx'a3iM'5i'--

<' 'Xi&lMmfi ^ M

- nx(?'*9d

J' i &idno-)^oid

„. „ ...

.

,?:i

.?i t

- r

Ji n

u

;li

as:.

B.-

li-. if

U

i^C .&c"

^.t S:v

'$>

;t*

m:.

. ":
12

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

APPENDIX B: Listings of access routines

procedure insert (var tab: table; key, depth: integer;

var kickout : kicktab)

var

index, temp, lenl, len2: integer;

costl, cost2: real;

stkl, stk2: stkptr;

procedure getnode (var p:stkptr);

beg in

if oldnodes=nil then new(p)

else begin

p

: =oldnodes

oldnodes : =oldnodes" . nex t

end

p" .next: =nil

end

procedure freenode ( f irst , last : stkptr )

var

X : stkptr

beg in

if firstOlast then

beg in

X : = f i r s t

while first" .nextOlast do first:=f irst" .next;

first". next: =oldnodes;

oldnodes : =x end

end;

procedure rearrange (stack: stkptr; key, length: integer);

beg in

if length > kickout[0] then kickout [ 0 ]: =length

repeat

if stack" .newlen > kicksize then

beg in

if kickout[-l] < stack" .newlen then

kickout[-l] : =stack" .newlen;

kickout [ 0 ]: =kicksize+l ; { trap to overflow counter } stack" .newlen : =kicksize+l

end

if stack" .oldlen > kicksize then

stack" .oldlen: =kicksize + 1;

kickout [ stack" .newlen] : =k ickout [stack" .newlen] + 1;

kickout [stack" .oldlen] : =kickout [stack" .oldlen] - 1;

if stack". next <> nil then

- 16 -
44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

tab [stack ^ . ind] : =tab [ stack ^ .next" . ind]

else tab [stack" , ind] : =key;

stack :=s tack". next

until stack=nil;

while kickout [kickout [0] ] = 0 do kickout [ 0 ] ; =kickout [0 ] -1

end

function displace ( index , depth : integer ; maxrreal; r jstack rstkptr

var stack: stkptr; var length: integer ): real

var

ind, probetoind, probetofree, counter, step, hashl,

next, srchlen: integer;

uplim, totcost, pentonext: real;

thisnode, savr j , bestack, tstack: stkptr;

procedure push (i ,oldlen,newlen: integer ; var stack : stkptr )

var

node: stkptr;

beg in

getnode (node)

node" . ind : =i

node" .newlen: =newlen;

node" .oldlen : =oldlen

node" .next : =s tack

stack : =node

end

function member (i:integer; stk: stkptr ): boolean

var

found: boolean;

begin

found : =f alse

while (stk <> nil) and (not found) do

if stk".ind=i then found:=true

else stk : =stk" .next;

member : =f ound

end

function penalty ( i : integer ) : real;

{to be defined as desired; currently linear}

beg in

penalty : =fl oat ( i)

end

begin { function displace } step: = (tab [ index] mod (tablesize-2) ) +1

hashl : =tab [ index] mod tablesize;

probeto ind : =0

repeat

- 17 -
88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

ind:=(hashl + probetoind * step) mod tablesize;

probetoind : =probetoind + 1

until ind=index;

probetof ree : =0

;

repeat

ind;=(hashl + probetofree * step) mod tablesize;

probetof ree : =probetof ree + 1

until (tab [ ind] =-l) or ( tab [ ind] =-2)

;

push ( index , probetoind , probetofree , stack) ; thisnode : =stack

;

tstack : =stack

;

bestack : =stack

;

savr j

: =rj stack

;

length ; =probetof ree

;

uplim: =penalty (probetofree) -penalty (probetoind)

;

push(ind, 1,1, be stack)

;

if depth > 0 then

beg in

if uplim > max then uplim :=max;

counter : =0

;

next : =hashl

;

pentonext : =penalty (1) - penalty (probeto ind ) ; while uplim > pentonext do

beg in

if (not member (next , stack) ) and (not member (next , r js tack )

)

then

beg in

totcost ; =pentonext + displace (next , depth-1, upl im-pentonex t

,

rjstack, tstack, srchlen)

;

if totcost < uplim then

beg in

upl im: =totcost

;

freenode (bestack , stack)

;

bestack : = tstack ; thisnode" . newlen : =counter+l

;

if 1+counter > srchlen then length : =l+counter

else length : =srchlen

;

end

else begin

push (next, 1, 1, rjstack )

;

freenode (tstack , stack)

end

;

tstack : =stack

;

end

;

counter : =counter + l

;

next:=(hashl + counter * step) mod tablesize;

pentonext : =penalty (1+counter ) - penalty (probetoind

)

end

;

freenode (rjstack,savrj)

end

;

stack : =bestack

;

displace : =uplim

- 18 -
140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

end

;

begin { procedure insert }

index:=key mod tablesize;

kickout[lJ : =kickout [1 ] +1

;

if (tab [ index] =-l ) or (tab [ index] =-2 ) then tab [ index] : =key

else begin

stkl : =nil

;

stk2: =nil

;

if depth>0 then

costl: =displace ( index , depth-1, maxreal, nil, stkl, lenl);

temp: =tab [ index] ; tab [ index] : =key

;

cost2 : =displace ( index , depth, costl, nil, stk2, len2)

;

if (depth =0) or (cost2 < costl) then rear range (stk2 , temp, len2)

else begin

tab[index] ;=temp;

rear range (stkl , key, lenl)

end

;

freenode (stkl, nil) ; f reenode (stk2,nil)

end

end

;

{ procedure insert }

- 19 -
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

function f ind (var tab: table; key: integer; var kickout: kicktab;

var probes: integer): integer;

var

hashl , step , index , 1 imit : integer;

begin

probes : =0

;

hashl:= key mod tablesize;

step:= key mod (tablesize - 2) +1;

if kickout [0] =kicksize+l then limit:=kickout [-1]

else limit:=kickout [0]

;

repeat

index := (hashl + probes * step) mod tablesize;

probes : =probes+l

until ( tab [ index j =key) or (tab [ index] =-l) or (probes=l imi t )

;

if tab [ index j =key then find: = index

else find:=-l

end

;

{ function find }

procedure delete (var tab; table; key: integer; var kickout: kicktab);

var

where , probes ; integer;

beg in

where:=find (tab, key, kickout, probes)

;

if where = -1 then wr iteln (output , key ,' not found')

else begin

tab [where] : =-2

;

if probes > kicksize then probes:= kicksize+1;

kickout [probes] :=kickout [probes] -1

;

while (kickout [0] <>1) and (kickout [ kickout [ 0 ]] =0

)

do kickout [0] :=kickout [0] -1

end

end

;

{ procedure delete }

- 20 -
APPENDIX C: Sample results

The table was 98% filled. The following was done for

DEPTh = 0,1,2,3,4,10; 4899 random integers were generated

from a 1 inear-congr uential formula i

: =3309*1+885321 (mod

4194304). The same 4899 keys were retrieved from the table

to calculate retrieval performances, 4899 keys not in the

table were generated and rejected to calculate rejection

performances. This was repeated 18 times.

TABLESIZE; 4999

NUMBER OF KEYS INSERTED: 4899

PERCENT OF TABLE FILLED; 98

DEPTH OF RECURSION; 0

PENALTY FUNCTION USED; LINEAR

TRIAL LONGEST PROBE MEAN PROBES MEAN REJEC

1 179 4.05429 48.17125

2 154 3.96142 47.80567

3 266 4.00204 49.21779

4 181 3.93957 48.19289

5 158 4.06940 48.14002

6 407 3.84057 48.72545

7 210 3.92712 49.15839

8 131 3.84057 45.55154

9 171 3.92733 47.68626

10 170 3.84751 48.78914

11 144 3.96366 47.68279

12 155 3.92998 47.07409

13 220 4.03184 50.97244

14 249 3.96529 48.20759

15 142 3.82384 45.78485

16 264 4.08389 50.35047

17 195 4.03123 48.02571

18 169 3.89957 48.48152

MEAN 198.05 3.95217 48.22322

- 21 -
TABLESIZE: 4999

NUMBER OF KEYS INSERTED: 4899

PERCENT OF TABLE FILLED: 98

DEPTH OF RECURSION: 1

PENALTY FUNCTION USED: LINEAR

TRIAL LONGEST PROBE MEAN PROBES

1 20

2 15

3 26

4 20

5 21

6 18

7 20

8 25

9 20

10 20

11 20

12 21

13 19

14 19

15 27

16 19

17 21

18 18

2.14696

2.12880

2.12247

2.13574

2.11614

2.16431

2.13247

2.14778

2.11859

2.12267

2.14227

2.14206

2.13655

2.12288

2.15554

2.15819

2.15839

2.14472

mean 20.50 2.13870

MEAN REJECTION

16.64258

13.07817

20.30557

16.49112

17.29679

15.17922

16.63400

19.72320

16.67462

16.68748

16.52582

17.05817

15.84547

15.99224

20.89773

16.01285

17.33210

15.43233

16.87830

22 -
TABLESIZE: 4999

NUMBER OF KEYS INSERTED; 4899

PERCENT OF TABLE FILLED: 98

DEPTH OF RECURSION; 2

PENALTY FUNCTION USED; LINEAR

TRIAL LONGEST PROBE MEAN PROBES MEAN REJECTION

1 13 1.89855 11.64564

2 11 1.90936 10.04123

3 12 1.90304 10.67605

4 15 1.89895 13.08532

5 11 1.92284 10.01408

6 13 1.89548 11.58522

7 11 1.91181 9.95264

8 12 1.91202 10.74402

9 11 1.92304 9.93794

10 14 1.91712 12.29271

11 12 1.89712 10.78138

12 13 1.87711 11.53031

13 12 1.91855 10.76546

14 13 1.91835 11.58236

15 11 1.92876 10.05409

16 14 1.89875 12.42600

17 11 1.91345 9.99183

18 12 1.90814 10.75648

MEAN 12.27 1.90847 10.99237

- 23 -
TABLESIZE: 4999

NUMBER OF KEYS INSERTED: 4899

PERCENT OF TABLE FILLED: 98

DEPTH OF RECURSION: 3

PENALTY FUNCTION USED: LINEAR

TRIAL LONGEST PROBE MEAN PROBES

1 11 1.83710

2 9 1.84486

3 11 1.83445

4 11 1.81812

5 10 1.81771

6 9 1.80608

7 10 1.84323

8 10 1.81853

9 11 1.82629

10 11 1.84996

11 11 1.85772

12 9 1.83996

13 10 1.81833

14 11 1.83568

1

9 1.81853

16 10 1.83200

17 10 1.81975

18 8 1.81363

MEAN 10.05 1.82955

MEAN REJECTION

9.95407

8.35211

9.95733

10.00489

9.12349

8.28373

9.17962

9.17350

9.95611

9.94284

9.97958

8.37170

9.16084

9.92794

8.28965

9.14064

9.17228

7.42416

9.18858

- 24 -
TABLESIZE: 4999

NUMBER OF KEYS INSERTED: 4899

PERCENT OF TABLE FILLED: 98

DEPTH OF RECURSION: 4

PENALTY FUNCTION USED: LINEAR

TRIAL LONGEST PROBE MEAN PROBES MEAN REJECTION

1 8 1.80894 7.42559

2 10 1.79975 9.11900

3 8 1.77873 7.45621

4 9 1.80036 8.31006

5 9 1.79199 8.26495

6 10 1.80261 9.11696

7 8 1.78362 7.44886

8 9 1.81036 8.28026

9 10 1.79159 9.16411

10 10 1.80159 9.17452

11 9 1.80547 8.28271

12 9 1.80016 8.27434

13 9 1.79056 8.28699

14 9 1.78648 8.29067

15 8 1.79567 7.41192

16 8 1.80159 7.43702

17 8 1.82159 7.46540

18 8 1.79465 7.47846

MEAN 8.83 1.79809 8.14933

- 25 -
TABLESIZE: 4999

NUMBER OF KEYS INSERTED: 4899

PERCENT OF TABLE FILLED: 98

DEPTH OF RECURSION: 10

PENALTY FUNCTION USED: LINEAR

TRIAL LONGEST PROBE MEAN PROBES

1 7

2 7

3 8

4 7

5 7

6 7

7 7

8 7

9 7

10 7

11 7

12 7

13 7

14 7

15 7

16 7

17 8

18 7

1.75199

1.76546

1.76484

1.75688

1.77709

1.74321

1.76811

1.76219

1.77342

1.76260

1.75750

1.74239

1.76423

1.76832

1.77995

1.75423

1.75729

1.76382

MEAN 7.11 1.76186

- 26 -

MEAN REJECTION

6.62482

6.58685

7.40579

6.56195

6.59951

6.59420

6.60318

6.59154

6.56031

6.58562

6.62318

6.60073

6.58215

6.58603

6.62237

6.59889

7.48867

6.58154

6.68874
The table was filled to 98% loading

All the keys in the

table were retr ieved to calculate retr ieval performances

An equal number of keys not in the table were rejected to

calculate rejection performances. 49% of the keys were

deleted. Retrieval and rejection statistics were again calculated. The table was filled back to a 98% loading

Retrieval and rejection statistics were again calculated.

These are the mean results of 18 trials:

TABLE SIZE: 4999

DEPTH OF RECURSION: 4

PENALTY FUNCTION USED: LINEAR

# OF KEYS % TABLE LONGEST MEAN PROBES TO

ACTION IN TABLE LOADED PROBE ACCEPT/REJECT

INSERT 4900

LOOKUP 4900

4900 97,9 9,06

1.80268 AC

LOOKUP-4900

DELETE 2450 2450 48,9 8.61

8.35276 RJ

LOOKUP 2450 1.78899 AC

LOOKUP-2450 7.98171 RJ

INSERT 2450

LOOKUP 2450

4900 97,9 9.50

1.86280 AC

LOOKUP-2450

AVERAGES OF EIGHTEEN TRIALS

9.43040 RJ

- 27 -
NBS-1 1 4A IR E V 7-73)

U.S. DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET

1. PUBLIC ATION OR REPORT NO.

NBSIR 78-1551

2. Gov’t Accession

No.

3. Recipient’s Accession No.

4. TITLE AND SUBTITLE

ACCESS FUNCTIONS FOR PACKED SCATTER TABLES

5. Publication Date August 1978

6. Performing Organization Code

7. AUTHOR(S)

Bruce E. Martin

8. Performing C^rgan. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

10. Project/Task/Work Unit No. 6401129

11. Contract/Grant No.

12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP)

see 9 above

13. Type of Report & Period Covered

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less (actual summary ol most significant information. If document includes a significant

bibliography or literature survey, mention it here.)

Three PASCAL access routines are given for packed scatter tables. INSERT packs

tables of integer keys; FIND retrieves the keys; DELETE deletes the keys. While the

routines currently access integer keys (for use in performance testing with pseudorandom integers) , they can easily be converted to access other data types —

character strings in a symbol table, for example. To enhance portability, the code

is straightforward PASCAL without any Input/output capabilities. Appendices

contain specific comments on the routines, listings, and sample results.

17. KHY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons

Access functions; fast retrievals; hashing; PASCAL; scatter storage

18. AVAILABILITY ^ Unlimited

For Official Distribution. Do Not Release to NTIS

Order From Sup. of Doc., U.S. Government Printing Office Washington, D.C. 20402, SD Cat. No. C13

[_J Order From National Technical Information Service (NTIS)

Springfield, Virginia 22151

19. SECURITY CLASS

(THIS REPORT)

UNCL ASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

29

22. Price

USCOMM-DC 290<2-P74

i'I