NamesImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Christian LeCocq September 11, 1986 9:52:03 am PDT
Management of a collection of ropes which are elementary elements, and can be concatenated to construct more names without copy.
DIRECTORY
Checksum,
HashTable,
Names,
Rope;
NamesImpl: CEDAR PROGRAM
IMPORTS Checksum, HashTable, Rope
EXPORTS Names
~ BEGIN OPEN Names;
Key: TYPE ~ HashTable.Key;
RefIndex: TYPE ~ REF Index;
Heading
CreateDictionnary: PUBLIC PROC [size: Index ← 64, data: REF ← NIL] RETURNS [dict: Dictionnary] ~ {
Description of the procedure.
dict ← NEW[NameTabRec ← [next: 1, data: data]]; --index=0 <=> ROPE=NIL
dict.tab ← NEW[TabRec[size]];
dict.invtab ← HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope];
};
NameFromRope: PUBLIC PROC [r: ROPE, in: Dictionnary, sep: ROPE ← "."] RETURNS [name: Name ← NIL] ~ {
Description of the procedure.
found: BOOLEAN;
index: Index;
ropeList: LIST OF ROPE ← Parse[r, sep];
UNTIL ropeList=NIL DO
[found, index] ← Fetch[ropeList.first, in];
name ← CONS[IF found THEN index ELSE Allocate[ropeList.first, in], name];
ropeList ← ropeList.rest;
ENDLOOP;
};
NameFromRopeWord: PUBLIC PROC [r: ROPE, in: Dictionnary] RETURNS [name: Name ← NIL] ~ {
Description of the procedure.
found: BOOLEAN;
index: Index;
[found, index] ← Fetch[r, in];
name ← CONS[IF found THEN index ELSE Allocate[r, in], name];
};
RopeFromName: PUBLIC PROC [name: Name, in: Dictionnary, sep: ROPE ← "."] RETURNS [r: ROPE ← NIL] ~ {
Description of the procedure.
IF name=NIL THEN RETURN;
r ← in.tab[name.first];
name ← name.rest;
UNTIL name=NIL DO
r ← Rope.Cat[in.tab[name.first], sep, r];
name ← name.rest;
ENDLOOP;
};
AppendRopeToName: PUBLIC PROC [name: Name, r: ROPE, in: Dictionnary, sep: ROPE ← "."] RETURNS [newName: Name] ~ {
Description of the procedure.
found: BOOLEAN;
index: Index;
ropeList: LIST OF ROPE ← Parse[r, sep];
newName ← name;
UNTIL ropeList=NIL DO
[found, index] ← Fetch[ropeList.first, in];
newName ← CONS[IF found THEN index ELSE Allocate[ropeList.first, in], newName];
ropeList ← ropeList.rest;
ENDLOOP;
};
AppendRopeWordToName: PUBLIC PROC [name: Name, r: ROPE, in: Dictionnary] RETURNS [newName: Name] ~ {
Description of the procedure.
found: BOOLEAN;
index: Index;
newName ← name;
[found, index] ← Fetch[r, in];
newName ← CONS[IF found THEN index ELSE Allocate[r, in], newName];
};
Equal: PUBLIC PROC [n1, n2: Name] RETURNS [eq: BOOLEAN] ~ {
IF n1=n2 THEN RETURN[TRUE]; --nobody checks that they point toward the same table...
UNTIL n1=NIL OR n2=NIL DO
IF n1.first#n2.first THEN RETURN[FALSE];
n1 ← n1.rest;
n2 ← n2.rest;
ENDLOOP;
IF n1#NIL OR n2#NIL THEN RETURN[FALSE] ELSE RETURN[TRUE];
};
HashTable Utilities
NameEqual: PUBLIC PROC [k1, k2: Key] RETURNS [eq: BOOL] = {
n1: Name = NARROW[k1];
n2: Name = NARROW[k2];
IF n1=n2 THEN RETURN[TRUE];
eq ← Equal[n1, n2];
};
HashName: PUBLIC PROC [k: Key] RETURNS [hash: CARDINAL] = {
n: Name ← NARROW[k];
hash ← 0;
UNTIL n=NIL DO
TRUSTED {hash ← Checksum.ComputeChecksum[hash, SIZE[Index], @n.first]};
n ← n.rest;
ENDLOOP;
};
Internal Dictionnary Management
Parse: PROC [r, sep: ROPE] RETURNS [lr: LIST OF ROPE] ~ {
lenr, lensep, i, j: INT;
lr2: LIST OF ROPE;
lenr ← Rope.Length[r];
lensep ← Rope.Length[sep];
i ← 0;
lr ← LIST[NIL];
lr2 ← lr;
UNTIL i>=lenr DO
j ← Rope.Index[r, i, sep]; -- do not begin by the separator !!!
lr2.rest ← LIST[Rope.Substr[r, i, j-i]];
i ← j+lensep;
lr2 ← lr2.rest;
ENDLOOP;
lr ← lr.rest;
};
Grow: PROC [nameTab: Dictionnary] ~ {
newTabRef: REF TabRec ← NEW[TabRec[nameTab.tab.size*2]];
FOR i: Index IN [0..nameTab.tab.size) DO
newTabRef[i] ← nameTab.tab[i];
ENDLOOP;
nameTab.tab ← newTabRef;
};
Allocate: PROC [r: ROPE, in: Dictionnary] RETURNS [index: Index] ~ {
Description of the procedure.
refIndex: RefIndex;
index ← in.next;
refIndex ← NEW[Index ← index];
in.tab[index] ← r;
in.next ← in.next+1;
IF in.next=in.tab.size THEN Grow[in];
[] ← HashTable.Store[table: in.invtab, key: r, value: refIndex];
};
Fetch: PROC [r: ROPE, in: Dictionnary] RETURNS [found: BOOLEAN, index: Index] ~ {
Description of the procedure.
found ← FALSE;
FOR i: Index IN [0..in.next) DO
IF Rope.Equal[r, in.tab[i]] THEN RETURN[TRUE, i];
ENDLOOP;
val: HashTable.Value;
[found: found, value: val] ← HashTable.Fetch[in.invtab, r];
IF found THEN index ← NARROW[val, RefIndex]^;
};
END.