General Ideas

Occasions arise where a program has or has had access to many keys and must be able to determine that a newly acquired key is the same as another key that was once held. A key indexed directory {KID} can associate an integer with a key. The KID will add and delete <key,number> pairs. It will return the number associated with a key. It will not return the key. {It probably doesn’t have it.}

A related function is to compare two key sets for inclusion. Since the KID may represent a key set it seems a natural for this function. This supports the requirements alluded to in (p3,glattice).

Another function that could be easily provided by the kid is object identification. The holder of a node key can determine if a given fetch key is to the same node. The KID might provide the same service. {It does not now.}

Some applications have no need for the integer value associated with the key, the membership test suffices.

a bank called the kid’s bank,

a set of <key,integer> pairs where “key” is some key and “integer” is some 32 bit integer

KIDC(0;PSB,M,SB==>c;EKID) {new KID}
c=0 and PSB is a prompt bank and SB is an official space bank and EKID is an empty kid {ns(EKID)=NEW()} or

c=1 and PSB is prompt but insufficient and EKID = DK(0) or

c=2 and PSB isn’t a prompt bank and EKID = DK(0) or

C=3 and SB isn’t a bank and EKID = DK(0)

KIDC(kt:==>X'0127')

KIDC is hidden in PRIVNODE {(kidcl)}.

D(2;K==>c,((4,i));) {retrieve integer value}
c=0 and the pair <K,i> belongs to D or

c=1 and no pair <K,i> belongs to D. {i=RET(D,K)}

D(4;E==>c;) {inclusion test}
E is a kid and If (for every pair <K,i> in E there is a pair <K,j> in D {INC(E,D)}) then c=0 Else c=1 FI or IMPOSTER.

D(kt;==>X'0027')

{ni}D(??;K==>c,((4,i),(1,typ),(1,db));N)

If K designates node n and D holds the node key to n with data byte zero then c = 0 and i is the value associated with the node key and typ is a code for the type of key K and db is the data byte of key K and N is the node key. Otherwise c = 1.

In the following kid calls, “LIMIT REACHED” means that DK(0) was returned and:
c=1 and D’s bank refused more pages or

c=2 and D’s bank refused more nodes or

c=3 and D’s max limit would have been exceeded.

D(1,((4,i));K==>c;) {add entry}
c=0 and the key-integer pair <K,i> is added to directory D {ns(D) = ADD(os(D),K,i)} or LIMIT REACHED. If <K,j> already belongs to D for some j then <K,j> is replaced in D by <K,i>.

D(3;K==>c;) {delete member from D}
c=0 and some pair <K,i> was in D and has been removed or

c=1 and no pair <K,i> belonged to D and D is unchanged. {ns(D) = DEL(os(D),K)}

In the following kid calls, “IMPOSTER” means that c=4 and key E was not a kid and D is unchanged.

D(5;E==>0;) {intersection}

c=0 and E is a kid and members of D that are not defined in E are deleted from D {ns(D) = INT(os(D),os(E))} or IMPOSTER.

D(6;E==>c;) {union}
c=0 and E is a kid and members of E such as <K,i> are added to D or replace such pairs as <K,j> {ns(D) = UNION(os(D),E)} or IMPOSTER or LIMIT REACHED.

D(kt+4;==>c;) causes the kid to dissolve itself. c=0 if successful (and D is DK(0)). c=1 if unsuccessful (because the bank that the KID was made from has been destroyed) (and D is useless).

We define here the combination rules for states of a Key Indexed Directory. We call such a state a “kid”. {NEW() provides the new empty kid. ADD(d,k,i) produces a directory state with the pair <k,i> added. BELONG(d,k) asks if key k is known to d. RET(d,k) returns the integer associated with k in d. DEL(d,k) is the directory state after deleting the pair with k. INC(d,e) asks if those keys defined in d are included in those of e. INT(d,e) and UNION(d,e) provide the intersection and union respectively of d and e.}

NEW: → kid
ADD: kid, key, int → kid
BELONG: kid, key → bool
RET: kid, key → int
DEL: kid, key → kid
INC: kid, kid → bool
INT: kid, kid → kid
UNION: kid, kid → kid

BELONG(NEW(),k) = false
BELONG(d,k) Or RET(d,k) = 0
RET (ADD(d,k,i),k) = i
BELONG(ADD(d,k,i),k) = true
RET (ADD(d,l,i),k) = RET(d,k) Or k = l
BELONG(ADD(d,l,i),k) = BELONG(d,k) Or k = l

BELONG(DEL(d,k),k) = false
BELONG(DEL(d,k),l) = BELONG(d,l) Or k = l
RET (DEL(d,k),l) = RET (d,l) Or k = l

{INC(d,e) = (e = UNION(d,e))}
INC(NEW(),d) = true
INC(ADD(d,k,i),e) = BELONG(e,k) And INC(d,e)

INT(d,d) = d INT(d,DEL(e,k)) = DEL(INT(d,e),k)
INT(DEL(d,k),e) = DEL(INT(d,e),k)

{N.B. These equations do not determine the meaning of intersection of two functions when the values defined on the common domain aren’t the same.}

UNION(NEW(),d) = d
UNION(ADD(e,k,i),d) = ADD(UNION(e,d),k,i)