<> <> <> <<>> <> <<>> 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; <> CreateDictionnary: PUBLIC PROC [size: Index _ 64, data: REF _ NIL] RETURNS [dict: Dictionnary] ~ { <> 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] ~ { <> 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] ~ { <> 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] ~ { <> 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] ~ { <> 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] ~ { <> 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]; }; <> 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; }; <> 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] ~ { <> 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] ~ { <> <> <> <> <> val: HashTable.Value; [found: found, value: val] _ HashTable.Fetch[in.invtab, r]; IF found THEN index _ NARROW[val, RefIndex]^; }; END.