-- NodeNameTableImpl.Mesa
-- written by Paxton. December 1980
-- last written by Paxton. April 5, 1981 3:16 PM

DIRECTORY
NodeNameTable,
TextNode,
TextLooks,
NodeProps,
TiogaAlloc,
SafeStorage,
Inline,
RopeReader,
RunReader,
Rope;

NodeNameTableImpl: PROGRAM
IMPORTS nodeI:TextNode, propsI:NodeProps, ropeI:Rope,
ropeRI:RopeReader, runRI:RunReader, allocI:TiogaAlloc,
SafeStorage, Inline
EXPORTS NodeNameTable =
BEGIN OPEN NodeNameTable, looksI:TextLooks;

qZone: ZONE ← SafeStorage.NewZone[quantized];
-- quantized zone for allocating name table entries

NameTable: TYPE = REF NameTableBody;
NameTableBody: PUBLIC TYPE = RECORD [nodes: HashTable];

HashTable: TYPE = REF HashTableArray;
HashTableArray: TYPE = ARRAY [0..hashTableSize) OF NodeList;
hashTableSize: NAT = 32; -- should be a power of 2

NodeList: TYPE = REF NodeListCell;
NodeListCell: TYPE = RECORD [next: NodeList, node: TextNode];

-- ***** Operations

Create: PUBLIC PROC RETURNS [tab: NameTable] = {
-- creates an empty name table.
tab ← NEW[NameTableBody]; tab.nodes ← NEW[HashTableArray]};

Get: PUBLIC PROC [n: Node] RETURNS [NameTable] = {
-- find the name table for node n.
-- look for nametable prop on n or ancestor.
-- returns NIL if reaches root node without finding a name table
table: NameTable ← NIL;
UNTIL n=NIL OR (table ← propsI.GetNameTable[n])#NIL DO
n ← nodeI.Parent[n];
ENDLOOP;
RETURN [table]};

Add: PUBLIC PROC [n: TextNode, table: NameTable] = {
-- add n to table. i.e., asserts that n now has a name
lst, nxt: NodeList;
nodeHash: NAT;
IF n.hasname THEN RETURN;
n.hasname ← TRUE;
nodeHash ← NodeHash[n];
IF (lst←table.nodes[nodeHash])=NIL THEN -- this is the first entry
table.nodes[nodeHash] ← NewNodeEntry[n]
ELSE DO
IF lst.node=n THEN ERROR; -- already on list
IF (nxt←lst.next)=NIL THEN { -- have reached end of list
lst.next ← NewNodeEntry[n]; RETURN };
lst ← nxt;
ENDLOOP };

Remove: PUBLIC PROC [n: TextNode, table: NameTable] = {
-- remove n from table. i.e., asserts that n no longer has a name
prev, lst: NodeList;
nodeHash: NAT ← NodeHash[n];
IF ~n.hasname THEN RETURN;
n.hasname ← FALSE;
IF (lst ← table.nodes[nodeHash])=NIL THEN ERROR; -- no entries
IF lst.node=n THEN { table.nodes[nodeHash] ← lst.next; RETURN };
DO
prev ← lst;
IF (lst ← lst.next)=NIL THEN ERROR; -- failed to find node
IF lst.node=n THEN { prev.next ← lst.next; RETURN };
ENDLOOP };

RemoveSpan: PUBLIC PROC
[parent: Node, start, len: Card, table: NameTable] = {
-- remove all names for len children of parent starting at start.
-- and for all their children, recursively
OPEN nodeI;
node: Node ← NthChild[parent,start];
topnode: Node ← node;
nodeChild: Node;
prev, lst: NodeList;
nodeHash: NAT;
IF len=0 OR node=NIL THEN RETURN;
DO
IF node.hasname THEN {
node.hasname ← FALSE;
nodeHash ← NodeHash[node];
IF (lst ← table.nodes[nodeHash])=NIL THEN ERROR; -- table is empty
IF lst.node=node THEN table.nodes[nodeHash] ← lst.next
ELSE DO -- search the list for the current node
prev ← lst;
IF (lst ← lst.next)=NIL THEN ERROR; -- failed to find it
IF lst.node=node THEN { prev.next ← lst.next; EXIT };
ENDLOOP };
IF (nodeChild ← FirstChild[node]) # NIL THEN node ← nodeChild
ELSE DO -- move to next node
IF node=topnode THEN
IF (len←len-1)=0 OR (topnode←node←Next[topnode])=NIL THEN RETURN
ELSE EXIT;
IF ~IsLastSibling[node] THEN { node ← Next[node]; EXIT };
node ← Parent[node];
ENDLOOP;
ENDLOOP };

Find: PUBLIC PROC [name: Rope, table: NameTable, prev: TextNode ← NIL]
RETURNS [n: TextNode] = {
-- returns a node that has the given name.
-- let prev be NIL for first call.
-- if prev # NIL, will return next node with that name.
-- returns NIL when no more nodes with the name.
-- or when prev # NIL is not on list.
FindName: PROC [node: TextNode] RETURNS [BOOLEAN] = INLINE {
lookRuns: looksI.Runs;
pos: Card ← 0;
nameStart: Card;
rope: Rope ← node.rope;
size: Card ← ropeI.Size[rope];
insideName: BOOLEAN ← FALSE;
IF (lookRuns ← node.runs)=NIL THEN ERROR; -- shouldn’t be in name table
runRI.SetPosition[runrdr,lookRuns];
UNTIL pos=size DO
looks: looksI.Looks;
len: Card;
[len,looks] ← runRI.Get[runrdr];
IF ~insideName THEN { -- see if about to start a name
IF looks[’n] THEN { insideName←TRUE; nameStart←pos }}
ELSE IF ~looks[’n] THEN { -- have just reached end of name
IF pos-nameStart = nameSize THEN { -- sizes match
rdr1↑ ← namerdr↑; -- restore to start of name
IF ropeRI.EqSubstr[name,rope,nameStart,nameSize,rdr1,rdr2] THEN
RETURN [TRUE] };
insideName ← FALSE };
pos ← pos+len;
ENDLOOP;
RETURN [FALSE] };
takeNext: BOOLEAN ← prev=NIL;
namerdr: ropeRI.Ref ← allocI.GetRopeReader[];
rdr1: ropeRI.Ref ← allocI.GetRopeReader[];
rdr2: ropeRI.Ref ← allocI.GetRopeReader[];
runrdr: runRI.Ref ← allocI.GetRunReader[];
nameSize: Card;
IF table=NIL OR name=NIL THEN RETURN [NIL];
ropeRI.SetPosition[namerdr,name];
[] ← ropeRI.Peek[namerdr]; -- prime the pump
nameSize ← ropeI.Size[name];
FOR i:NAT IN [0..hashTableSize) DO
lst: NodeList;
next: NodeList ← table.nodes[i];
UNTIL (lst←next)=NIL DO
next ← lst.next;
IF ~takeNext THEN { IF lst.node=prev THEN takeNext ← TRUE }
ELSE IF FindName[lst.node] THEN { n ← lst.node; GOTO FoundIt };
ENDLOOP;
REPEAT FoundIt => NULL;
ENDLOOP;
allocI.FreeRunReader[runrdr];
allocI.FreeRopeReader[namerdr];
allocI.FreeRopeReader[rdr1];
allocI.FreeRopeReader[rdr2] };

Map: PUBLIC PROC [table: NameTable, action: MapAction]
RETURNS [BOOLEAN] = {
-- applies action to each entry in table until an action returns true
-- action can remove entries; may or may not apply action to added entries
FOR i:NAT IN [0..hashTableSize) DO
lst: NodeList;
next: NodeList ← table.nodes[i];
UNTIL (lst←next)=NIL DO
next ← lst.next;
IF action[lst.node] THEN RETURN [TRUE];
ENDLOOP;
ENDLOOP;
RETURN [FALSE] };

NewNodeEntry: PROC [node: TextNode] RETURNS [NodeList] = INLINE {
RETURN [ qZone.NEW[NodeListCell ← [NIL,node]] ] };

NodeHash: PROC [node: nodeI.Ref] RETURNS [NAT] = INLINE { RETURN [
(LOOPHOLE[Inline.LowHalf[node],NAT]/16) MOD hashTableSize]};

-- ***** Initialization

Start: PUBLIC PROC = {
};

END.