-- 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.(635)