DIRECTORY
Basics,
BasicTime USING[GMT],
ConvertUnsafe,
DBCommon,
DBStorage,
DBDefs,
DB,
DBModel,
DBModelPrivate,
Rope,
SymTab;

DBModelIndexImpl: CEDAR PROGRAM
IMPORTS Basics, ConvertUnsafe, DB, DBStorage, DBModelPrivate, Rope
EXPORTS  DBModel, DBModelPrivate
SHARES Rope =

BEGIN OPEN DBCommon, DBDefs;

DeclareIndex: PUBLIC PROC [r: Relation, fields: FieldSequence, isKey: BOOL _ FALSE, doCheck: BOOL _ TRUE] RETURNS[index: Index] = {
sh: SegmentHandle = DBModelPrivate.SegmentToHandle[r.segment];
indicesToCheck: LIST OF IndexHandle;
DBModelPrivate.CheckRelationKey[r];
IF NOT r.indicesKnown THEN CacheIndices[r];
IF doCheck THEN {
IF isKey THEN indicesToCheck _ r.keys ELSE indicesToCheck _ r.indices;
FOR i: LIST OF IndexHandle _ indicesToCheck, i.rest UNTIL i = NIL DO
same: BOOL _ TRUE;
IF i.first.index.count # fields.count THEN LOOP;
FOR j: CARDINAL IN [0..fields.count) WHILE same DO
same _ same AND i.first.index[j] = fields[j]
ENDLOOP;
IF same THEN
RETURN [NEW[ IndexObject _ [fields: i.first.index, isKey: i.first.isKey, key: r.key, index: i.first.indexHandle ] ] ]
ENDLOOP };
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
FOR i: CARDINAL IN [0..r.attributes.count) DO
appears: BOOL _ FALSE;
FOR j: CARDINAL IN [0..fields.count) DO
IF i = fields[j] THEN {
IF appears THEN ERROR DB.Error[IllegalIndex] ELSE appears _ TRUE }
ENDLOOP
ENDLOOP;
BEGIN
indexTuple: DBStorage.TupleHandle = DBModelPrivate.CopyTupleHandle[DBStorage.CreateSystemPageTuple[x: DBModelPrivate.IndexTupleSet, y: r.tupleSet, s: r.segment]];
cachedIndexHandle: IndexHandle _ NEW[IndexHandleObject _ [indexHandle: indexTuple, isKey: isKey, index: NEW[FieldSequenceObject[fields.count]]]];
index _ NEW[IndexObject _ [isKey: isKey, index: indexTuple, fields: cachedIndexHandle.index, key: r.key]];
DBModelPrivate.SetBoolField[indexTuple, DBModelPrivate.IndexKeyField, isKey];
DBModelPrivate.SetCardField[indexTuple, DBModelPrivate.IndexCountField, fields.count];
DBModelPrivate.SetTupleField[indexTuple, DBModelPrivate.IndexRelationField, r.tupleSet];
BEGIN
indexFactorGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[indexTuple, indexHandle, Last];
FOR i: CARDINAL IN [0..fields.count) DO
indexFactorTuple: DBStorage.TupleHandle = DBStorage.CreateSystemPageTuple[x: DBModelPrivate.IndexTupleSet, y: indexTuple, s: r.segment];
DBModelPrivate.SetCardField[indexFactorTuple, attributeHandle, fields[i]];
DBStorage.WriteTID[indexFactorTuple, indexFactorGroup];
cachedIndexHandle.index[i] _ fields[i]
ENDLOOP;
DBStorage.CloseScanGroup[indexFactorGroup]
END;
sh.schemaUpdated _ TRUE;
index.key _ r.key;
index.isKey _ isKey;
IF isKey THEN r.keys _ CONS[cachedIndexHandle, r.keys]
ELSE r.indices _ CONS[cachedIndexHandle, r.indices];
FOR i: CARDINAL IN [0..index.fields.count) DO
r.attributes[index.fields[i]].indices _ CONS[cachedIndexHandle, r.attributes[index.fields[i]].indices]
ENDLOOP
END
};

DestroyIndex: PUBLIC PROC [r: Relation, index: Index] = {
sh: SegmentHandle = DBModelPrivate.SegmentToHandle[r.segment];
DBModelPrivate.CheckRelationKey[r];
IF NOT r.indicesKnown THEN CacheIndices[r];
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
IF NOT DBModelPrivate.IsLegalIndex[r, index] THEN ERROR DB.Error[IllegalIndex];
IF index.isKey THEN ERROR DB.Error[IllegalIndex]; -- Can't destroy a key index!
DestroyIndexTuple[index.index];
BEGIN
r.indicesKnown _ FALSE;
r.keys _ r.indices _ NIL;
FOR i: CARDINAL IN [0..index.fields.count) DO
r.attributes[index.fields[i]].indices _ NIL
ENDLOOP
END;
sh.schemaUpdated _ TRUE
};

DestroyIndexTuple: PUBLIC PROC[handle: DBStorage.TupleHandle] = {
indexFactors: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[handle, indexHandle, First];
FOR indexFactor: TupleHandle _ DBStorage.NextInGroup[indexFactors], DBStorage.NextInGroup[indexFactors] UNTIL indexFactor = NIL DO
DBStorage.WriteTIDNil[indexFactor, indexHandle];
DBStorage.DestroyTuple[indexFactor]
ENDLOOP;
DBStorage.CloseScanGroup[indexFactors];
DBStorage.WriteTIDNil[handle, IndexRelationField]; -- remove it from the group for the relation
DBStorage.DestroyIndex[handle];
DBStorage.DestroyTuple[handle] };

DeleteTupleFromIndex: PUBLIC PROC[t: TupleHandle, r: Relation, iHandle: IndexHandle] = {
entry: Rope.ROPE = IndexEntryForTuple[t, r, iHandle.index];
DBStorage.DeleteFromIndex[x: iHandle.indexHandle, k: entry, v: t]
};

AddTupleToIndex: PUBLIC PROC[t: TupleHandle, r: Relation, iHandle: IndexHandle] = {
entry: Rope.ROPE = IndexEntryForTuple[t, r, iHandle.index];
DBStorage.InsertIntoIndex[x: iHandle.indexHandle, k: entry, v: t]
};

IndexEntryForTuple: PROC[t: TupleHandle, r: Relation, index: FieldSequence] RETURNS[entry: Rope.ROPE] = TRUSTED {
entry _ "";
FOR i: CARDINAL IN [0..index.count) DO
attr: REF AttributeObject = r.attributes[index[i]];
SELECT attr.type FROM
ropeType => entry _ Rope.Concat[entry, NCodeRope[DBModelPrivate.GetRopeField[t, attr.fh]]];
boolType => entry _ Rope.Concat[entry, NCodeBool[DBModelPrivate.GetBoolField[t, attr.fh]]];
intType => entry _ Rope.Concat[entry, NCodeInt[DBModelPrivate.GetIntField[t, attr.fh]]];
timeType => entry _ Rope.Concat[entry, NCodeTime[DBModelPrivate.GetTimeField[t, attr.fh]]];
ENDCASE => entry _ Rope.Concat[entry, NCodeTuple[DBModelPrivate.GetTupleField[t, attr.fh]]];
ENDLOOP };

CacheIndices: PUBLIC PROC[r: Relation] = {
indexHandles: LIST OF IndexHandle _ NIL;
keyHandles: LIST OF IndexHandle _ NIL;
indexGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[r.tupleSet, DBModelPrivate.IndexRelationField, First];
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
FOR t: TupleHandle _ DBStorage.NextInGroup[indexGroup], DBStorage.NextInGroup[indexGroup] UNTIL t = NIL DO
factorCount: CARDINAL = DBModelPrivate.GetCardField[t, DBModelPrivate.IndexCountField];
isKey: BOOL = DBModelPrivate.GetBoolField[t, DBModelPrivate.IndexKeyField];
thisHandle: IndexHandle _ NEW[IndexHandleObject _ [indexHandle: DBModelPrivate.CopyTupleHandle[t], isKey: isKey, index: NEW[FieldSequenceObject[factorCount]]]];
indexFactorGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[t, indexHandle, First];
thisFactor: CARDINAL _ 0;
FOR if: TupleHandle _ DBStorage.NextInGroup[indexFactorGroup], DBStorage.NextInGroup[indexFactorGroup] UNTIL if = NIL DO
thisHandle.index[thisFactor] _ DBModelPrivate.GetCardField[if, attributeHandle];
thisFactor _ thisFactor + 1
ENDLOOP;
DBStorage.CloseScanGroup[indexFactorGroup];
IF isKey THEN keyHandles _ CONS[thisHandle, keyHandles]
ELSE indexHandles _ CONS[thisHandle, indexHandles];
FOR i: CARDINAL IN [0..factorCount) DO
r.attributes[thisHandle.index[i]].indices _ CONS[thisHandle, r.attributes[thisHandle.index[i]].indices]
ENDLOOP
ENDLOOP;
DBStorage.CloseScanGroup[indexGroup];
r.indicesKnown _ TRUE;
r.indices _ indexHandles;
r.keys _ keyHandles };

Keys: PUBLIC PROC[r: Relation] RETURNS[keys: LIST OF Index] = {
DBModelPrivate.CheckRelationKey[r];
CacheIndices[r];
IF r.isSurrogate THEN { 
fields: FieldSequence _ NEW[FieldSequenceObject[1]];
fields[0] _ 0;
keys _ LIST[NEW[IndexObject _ [key: r.key, isKey: TRUE, fields: fields]]] };
FOR kL: LIST OF IndexHandle _ r.keys, kL.rest UNTIL kL = NIL DO
keys _ CONS[NEW[IndexObject _ [key: r.key, index: kL.first.indexHandle, isKey: TRUE, fields: kL.first.index]], keys]
ENDLOOP };

Indices: PUBLIC PROC[r: Relation] RETURNS[indices: LIST OF Index] = {
DBModelPrivate.CheckRelationKey[r];
CacheIndices[r];
FOR kL: LIST OF IndexHandle _ r.indices, kL.rest UNTIL kL = NIL DO
indices _ CONS[NEW[IndexObject _ [key: r.key, index: kL.first.indexHandle, isKey: FALSE, fields: kL.first.index]], indices]
ENDLOOP};

NCode: PUBLIC PROC [v: Value] RETURNS [code: Rope.ROPE] ~ TRUSTED {
WITH v: v SELECT FROM
rope => code _ NCodeRope[v.value];
boolean => code _ NCodeBool[v.value];
integer => code _ NCodeInt[v.value];
time => code _ NCodeTime[v.value];
entity => code _ NCodeTuple[v.value.tuple];
null => code _ "\000\000";
ENDCASE };

NCodeRope: PUBLIC PROC[rope: Rope.ROPE] RETURNS [code: Rope.ROPE] = {
code _ Rope.Concat[rope, "\000\000"] };

NCodeBool: PUBLIC PROC[bool: BOOL] RETURNS [code: Rope.ROPE] = {
code _ Rope.Concat[IF bool THEN "T" ELSE "F", "\000\000"] };

NCodeTuple: PUBLIC PROC [t: TupleHandle] RETURNS [code: Rope.ROPE] ~ {
code _ NCodeCard[t.tid] };

NCodeInt: PUBLIC PROC[int: INT] RETURNS [code: Rope.ROPE] = TRUSTED {
i: LONG CARDINAL = LOOPHOLE[int, LONG CARDINAL]+20000000000B;
code _ NCodeCard[i] };

NCodeTime: PUBLIC PROC[time: BasicTime.GMT] RETURNS [code: Rope.ROPE] = TRUSTED {
i:  LONG CARDINAL = LOOPHOLE[time];
code _ NCodeCard[i] };

LowByte: PROC [n: CARDINAL] RETURNS [CHAR] = TRUSTED INLINE
{RETURN[LOOPHOLE[LOOPHOLE[n, Basics.BytePair].low]]};

HighByte: PROC [n: CARDINAL] RETURNS [CHAR] = TRUSTED INLINE
{RETURN[LOOPHOLE[LOOPHOLE[n, Basics.BytePair].high]]};

NCodeCard: PUBLIC PROC[i: LONG CARDINAL] RETURNS [code: Rope.ROPE] = TRUSTED {
s: STRING _ [4];
s.length _ 4;
s[0] _ HighByte[Basics.HighHalf[i]];
s[1] _ LowByte[Basics.HighHalf[i]];
s[2] _ HighByte[Basics.LowHalf[i]];
s[3] _ LowByte[Basics.LowHalf[i]];
code _ Rope.Concat[ConvertUnsafe.ToRope[s], "\000\000"] };

DCode: PUBLIC PROC[key: DBCommon.IndexKey, ropes: RopeSequence] = TRUSTED {
start: INT _ 0;
end: INT _ 0;
ropeText: Rope.Text;
IF key = NIL THEN RETURN;
FOR i: CARDINAL IN [0..ropes.length) DO
UNTIL key.text[end] = '\000 AND key.text[end+1] = '\000 DO end _ end+1 ENDLOOP;
ropeText _ Rope.NewText[end - start];
ropeText.length _ end - start;
FOR j: INT IN [0 .. end-start) DO ropeText[j] _ key.text[start+j] ENDLOOP;
ropes[i] _ ropeText;
start _ end _ end+2
ENDLOOP };

CheckKeyInIndex: PUBLIC PROC[i: IndexHandle, key: Rope.ROPE] RETURNS [yes: BOOL] = {
yes _ DBModelPrivate.GetNamedTuple[i.indexHandle, key] # NIL };


IndexCountField: PUBLIC DBStorage.FieldHandle;

IndexRelationField: PUBLIC DBStorage.FieldHandle;

IndexKeyField: PUBLIC DBStorage.FieldHandle;

IndexFactorTupleSet: DBStorage.SystemTuplesetHandle;

IndexFactorDomain: DBCommon.TupleHandle;

attributeHandle, indexHandle: DBStorage.FieldHandle;

InitializeIndexSchema: PUBLIC PROC[] = TRUSTED {
[IndexFactorTupleSet, IndexFactorDomain] _ DBModelPrivate.SetSystemTable[DBModelPrivate.IndexFactorTSID];

[] _ DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.IndexDescriptor];
IndexCountField _ DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.OneWordDescriptor];
IndexRelationField _ DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBStorage.FieldDescriptor[Group[groupID: DBModelPrivate.RelationDomain]]];
IndexKeyField _ DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.OneWordDescriptor];
indexHandle _ DBStorage.AddSystemField[IndexFactorTupleSet, DBStorage.FieldDescriptor[Group[groupID: DBModelPrivate.IndexDomain]]];
attributeHandle _ DBStorage.AddSystemField[IndexFactorTupleSet, DBModelPrivate.OneWordDescriptor] };

END.
	ZFile: DBModelIndexImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Contents: Implementation of DBModel, DBModelPrivate operations on relations.
Last edited by:
Donahue, June 20, 1986 9:11:32 am PDT
Check to see if index already exists
Ensure that each attribute appears at most once in the index
Add the index factors to the database
Finally, include the new index in the list for all of the attributes
Remove it from the database
Remove it from the cache (this is a little aggressive, but simple!)
Enumerate all of the attributes of the relation tuple
Now enumerate each of the factors of the index
Finally, hook up with the attributes
Add the implied key of the surrogate
This procedure takes apart a key that has been composed as a concatenation of calls to NCode and places each component in the given element of the rope sequence that was passed in
Find the end of the next piece
Create a new rope and copy the text
4. Definition of the structure of Indices in the Database
The structure of the storage of the relations, attributes and index factors component of a Cypress database is reasonably complicated and takes advantage of the ability to define many groups at the storage level.
An index tuple is the head of an index-factor group; it also contains a count of the number of factors in the index.  Elements of the index factor domain contain links to the attribute that defines the factor and are linked in the order in which the index factors are to be used in accessing the index.
Handles for the index factor domain
The IndexDomain tuples are all used as indices; the first field is used to store the index information, the second may store the number of index factors that make up the index entries (if the index is client-created), the third gives the relation for which the index is being maintained, and the final field specifies whether the index is an index of keys of the relation

An index tuple is the head of an index-factor group; it also contains a count of the number of factors in the index.  Elements of the index factor domain contain links to the attribute that defines the factor and are linked in the order in which the index factors are to be used in accessing the index.

The IndexFactor tuples have the following fields:
1.  the index for the factor,
2.  the position (a CARDINAL) of the corresponding attribute in the relation
�Ê°˜š
œ™Jšœ
Ïm
œ1™<—Jš
œL™Lš
œ™Icode™%—J˜š
Ïk	˜	J˜Jšœ
žœ
žœ˜J˜Jš
œ	˜	J˜
J˜Jšžœ
˜J˜J˜J˜Jš
œ˜J˜—šœžœ
ž˜Jšžœ;˜BJšžœ˜ šžœ˜
J˜——šžœ
žœ˜J˜šÏnœžœ
žœ-žœžœžœžœžœ˜ƒ
Jš
œ>˜>Jšœžœ
žœ
˜$Jš
œ#˜#Jšžœ
žœžœ˜+šžœ	žœ˜Jš
œ$™$Jšžœžœžœ˜Fšžœžœ
žœ&žœžœ
ž˜DJšœžœžœ
˜Jšžœ$žœ
žœ
˜0š	žœžœ
žœžœž˜2Jšœžœ˜,Jšžœ
˜—šžœž˜Jšžœžœj˜u—Jšžœ˜
——Jšžœ
žœžœ#˜@Jš
œ<™<šžœžœ
žœž˜-Jšœ	žœžœ
˜šžœžœ
žœž˜'šžœžœ˜Jšžœ	žœ
žœ
žœžœžœ˜B—Jš
ž˜—Jšžœ
˜—š
ž˜Jš
Ϣ
˜¢
Jšœ!žœDžœ&˜‘
Jšœžœ_˜jJ˜MJ˜VJš
œX˜XJš
œ%™%š
ž˜Jš
œe˜ešžœžœ
žœž˜'Jš
œˆ
˜ˆ
Jš
œJ˜JJš
œ7˜7Jš
œ&˜&Jšžœ
˜—Jš
œ*˜*Jšžœ
˜—Jšœžœ
˜J˜J˜Jšžœžœ
žœ˜6Jšžœ
žœ˜4Jš
œD™Dšžœžœ
žœž˜-Jšœ(žœ:˜fJš
ž˜—Jš
ž˜—Jš
œ˜—J˜šŸœžœ
žœ ˜9Jš
œ>˜>Jš
œ#˜#Jšžœ
žœžœ˜+Jšžœ
žœžœ#˜@Jš
žœ
žœ'žœ
žœ
žœ˜OJš	žœ
žœ
žœ
žœÏc˜OJš
œ™Jš
œ˜Jš
œC™Cš
ž˜Jšœžœ
˜Jšœž˜šžœžœ
žœž˜-Jšœ(ž˜+Jš
ž˜—Jšžœ
˜—Jšœž˜Jš
œ˜—J˜šŸœžœ#˜AJš
œ^˜^šžœežœžœ
ž˜‚
Jš
œ0˜0Jš
œ#˜#Jšžœ
˜—Jš
œ'˜'Jšœ3 ,˜_Jš
œ˜Jš
œ!˜!—J˜šŸœžœ
žœ7˜XJšœžœ+˜;Jš
œA˜AJš
œ˜—J˜šŸœžœ7˜SJšœžœ+˜;Jš
œA˜AJš
œ˜—J˜š
Ÿœžœ4žœ
žœžœ˜qJ˜šžœžœ
žœž˜&Jšœžœ*˜3šžœž˜Jš
œ[˜[Jš
œ[˜[Jš
œX˜XJš
œ[˜[—JšžœU˜\Jšžœ˜
——J˜šŸœžœ˜*Jšœžœ
žœžœ
˜(Jšœžœ
žœžœ
˜&Jš
œv˜vJšžœ
žœžœ#˜@Jš
œ5™5šžœWžœžœ
ž˜jJšœ
žœB˜WJšœžœ@˜KJšœžœ[žœ%˜ 
Jš
œ.™.Jš
œ]˜]Jšœžœ˜šžœdžœžœ
ž˜xJš
œP˜PJ˜Jšžœ
˜—Jš
œ+˜+Jšžœžœžœ˜7Jšžœžœ˜3Jš
œ$™$šžœžœ
žœž˜&Jšœ,žœ7˜gJš
ž˜—Jšžœ
˜—Jš
œ%˜%Jšœžœ
˜Jš
œ˜Jš
œ˜J˜—šŸœžœ
žœžœžœ
žœ˜?Jš
œ#˜#Jš
œ˜šžœžœ˜Jš
œ$™$Jšœžœ˜4Jš
œ˜Jšœžœ
žœ#žœ˜L—šžœžœ
žœžœžœ
ž˜?Jšœžœ
žœ@žœ!˜tJšžœ˜
——J˜šŸœžœ
žœžœ
žœ
žœ˜EJš
œ#˜#Jš
œ˜šžœžœ
žœ"žœžœ
ž˜BJšœ
žœ
žœ@žœ$˜{Jšžœ˜	——J˜š
Ÿœžœžœ
žœžœ˜Cšžœžœ
ž˜Jš
œ"˜"Jš
œ%˜%Jš
œ$˜$Jš
œ"˜"J˜+Jš
œ˜Jšžœ˜
—K˜—šŸ	œžœ
žœžœžœ
žœ˜EJš
œ'˜'—J˜šŸ	œžœ
žœžœžœ
žœ˜@Jšœžœžœžœ˜<—J˜šŸ
œžœžœ
žœ˜FJš
œ˜—K˜šŸœžœ
žœžœžœ
žœžœ˜EJšœžœ
žœžœžœ
žœ˜=Jš
œ˜—J˜šŸ	œžœ
žœžœžœ
žœžœ˜QJšœžœ
žœžœ˜#Jš
œ˜—J˜š
Ÿœžœžœžœžœžœ
ž˜;Jšœ
žœ
žœ
žœ˜5—J˜š
Ÿœžœžœžœžœžœ
ž˜<Jšœ
žœ
žœ
žœ˜6—J˜šŸ	œžœ
žœžœ
žœžœ
žœžœ˜NJšœžœ˜Jš
œ
˜
J˜$J˜#J˜#J˜"Jš
œ:˜:—J˜šŸœžœ
žœ0žœ˜KKš
œ³
™³
Kšœžœ˜Kšœžœ˜
K˜Kšžœžœ
žœ
žœ
˜šžœžœ
žœž˜'Kš
œ™Kšžœžœžœ
žœ
˜OKš
œ#™#K˜%K˜Kš
žœžœ
žœžœ!žœ
˜JK˜K˜Kšžœ˜
——K˜š
Ÿœžœžœžœžœ˜TKšœ9žœ˜?——
head1š
œ9™9Jš
œÔ
™Ô
J˜Jš
œ®™®J˜Jšœžœ˜.J˜Jšœžœ˜1J˜Jšœžœ˜,J˜Jšœž
œ˜4J˜Jš
œ(˜(J˜š
œ#™#Jš
œ4˜4—J˜šŸœžœ
žœžœ˜0J™óJ™Jš
œ®™®J™Jš
œi˜iJ˜Jš
œ\˜\Jš
œk˜kJš
œ–
˜–
Jš
œi˜i™1J™J™L—Jš
œƒ
˜ƒ
Jš
œd˜d—J˜—Jšžœ
˜—…—*v?€