<> <> <> <> <> <> <> DIRECTORY DBCache, DBCommon, DBEnvironment, DBStorageInternal, DBStoragePagetags, DBIndexFilePage, DBIndex, Rope; DBIndexFilePageImpl: CEDAR PROGRAM IMPORTS DBEnvironment, Rope EXPORTS DBIndexFilePage = BEGIN CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize; FullPage: CARDINAL = DBIndex.FullPage; ROPE: TYPE = Rope.ROPE; WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging Page: TYPE = DBIndex.Page; ItemHandle: TYPE = DBIndex.ItemHandle; IndexKey: TYPE = DBIndex.IndexKey; KeyBody: TYPE = DBIndex.KeyBody; FakeIndexKey: TYPE = REF KeyBody; <> <> <> <> fakeIndexKeys: LIST OF FakeIndexKey; fakeIndexKeyCount: INT _ 0; -- Should equal fakeIndexKey.Length[], never more than 2 or 3 <> SetSize: PUBLIC PROC [p: Page, i: CARDINAL] = TRUSTED BEGIN p.pointer.size _ i END; <> FreeSpace: PUBLIC PROC [p: Page] RETURNS [CARDINAL] = <> TRUSTED BEGIN indexArraySize: CARDINAL _ p.pointer.size; free: CARDINAL_ IF indexArraySize=0 THEN CoreIndexSize ELSE p.pointer.index[indexArraySize - 1] - indexArraySize; IF free>CoreIndexSize THEN ERROR; RETURN[free] END; FrontSize: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL] = <> TRUSTED BEGIN RETURN[CoreIndexSize - p.pointer.index[index]] END; CoreAddr: PUBLIC PROC [p: Page, i: CARDINAL] RETURNS [ItemHandle] = <> TRUSTED BEGIN base: LONG POINTER _ @p.pointer.index; index: CARDINAL _ (base+i)^; IF i>CoreIndexSize THEN ERROR; RETURN[LOOPHOLE[base+index, ItemHandle]]; END; EndAddr: PUBLIC PROC [p: Page] RETURNS [LONG POINTER] = <<(Address of the word of the end of the page)+1>> TRUSTED BEGIN RETURN[p.pointer + FullPage] END; SizeOfEntries: PUBLIC PROC [page: Page, from: CARDINAL, to: CARDINAL] RETURNS [CARDINAL] = <> TRUSTED BEGIN left, right: CARDINAL; IF to < from THEN RETURN[0]; left _ page.pointer.index[to]; right _ IF from = 0 THEN CoreIndexSize ELSE page.pointer.index[from - 1]; RETURN[right - left] END; <> Value: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage] = TRUSTED BEGIN RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.DBPage]]; END; Tid: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBStorageInternal.TID] = TRUSTED BEGIN RETURN[LOOPHOLE[CoreAddr[p, index].value, DBStorageInternal.TID]]; END; Key: PUBLIC PROC [page: Page, index: CARDINAL] RETURNS [IndexKey] = <> <> TRUSTED BEGIN base: LONG POINTER _ @page.pointer.index; offset: CARDINAL _ (base+index)^; key: IndexKey_ LOOPHOLE[base+offset+2, IndexKey]; IF key.length>CoreIndexSize AND (page.depth=1 OR index#0) THEN ERROR; RETURN[key] END; <> CopyKey: PUBLIC PROC[key: IndexKey] RETURNS [IndexKey] = <> <> <> TRUSTED BEGIN ret: IndexKey _ AllocateIndexKey[key.length]; FOR i: CARDINAL IN [0..key.length) DO ret.text[i]_ key.text[i] ENDLOOP; RETURN[ret]; END; CreateIndexKey: PUBLIC PROC [s: ROPE] RETURNS [IndexKey] = <> TRUSTED BEGIN sLength: INT _ s.Size[]; ret: IndexKey _ AllocateIndexKey[sLength]; IF sLength>CoreIndexSize THEN ERROR; -- key too big FOR i: INT IN [0..sLength) DO ret.text[i]_ s.Fetch[i] ENDLOOP; RETURN[ret] END; AllocateIndexKey: PUBLIC PROC [bytes: INT] RETURNS[key: IndexKey] = <> <> <> <> BEGIN fk: FakeIndexKey; fk_ NEW[KeyBody[bytes]]; fakeIndexKeys_ CONS[fk, fakeIndexKeys]; fakeIndexKeyCount_ fakeIndexKeyCount+1; RETURN[LOOPHOLE[fk]] END; FreeKey: PUBLIC PROC[key: IndexKey] = <<"Deallocates" key; actually, just removes it from the fakeIndexKeys list so that the>> <> BEGIN fk: FakeIndexKey; TRUSTED { fk _ LOOPHOLE[key] }; IF key=NIL THEN RETURN; fakeIndexKeyCount_ fakeIndexKeyCount-1; IF fakeIndexKeys=NIL THEN ERROR DBEnvironment.InternalError; IF fk=fakeIndexKeys.first THEN {fakeIndexKeys_ fakeIndexKeys.rest; RETURN}; FOR fkl: LIST OF FakeIndexKey _ fakeIndexKeys, fkl.rest UNTIL fkl.rest=NIL DO IF fkl.rest.first=fk THEN {fkl.rest_ fkl.rest.rest; RETURN} ENDLOOP; ERROR DBEnvironment.InternalError; END; <> GreaterEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] = <=right>> TRUSTED BEGIN rightChar: CHAR; i: CARDINAL; FOR i IN [0..MIN[left.length, right.length]) DO rightChar _ right[i]; SELECT left[i] FROM > rightChar => RETURN[TRUE]; < rightChar => RETURN[FALSE]; ENDCASE; ENDLOOP; IF left.length >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE] END; LessEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] = <> TRUSTED BEGIN rightChar: CHAR; i: CARDINAL; FOR i IN [0..MIN[left.length, right.length]) DO rightChar _ right[i]; SELECT left[i] FROM > rightChar => RETURN[FALSE]; < rightChar => RETURN[TRUE]; ENDCASE; ENDLOOP; IF left.length <= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE] END; Less: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] = BEGIN RETURN[NOT GreaterEq[left, right]] END; Greater: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] = BEGIN RETURN[NOT LessEq[left, right]] END; <> <> FindTheFirstLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret:CARDINAL] = <> TRUSTED BEGIN m: CARDINAL; low: CARDINAL _ 0; high, sizePMinusOne: CARDINAL _ p.pointer.size-1; m _ (low + high)/2; IF p.pointer.size = 0 THEN -- ouch! try to push on anyway... {SIGNAL WhatDoYouThinkOfThis; RETURN[0]}; UNTIL m = low DO IF LessEq[key, Key[p, m]] THEN high _ m ELSE low _ m; <> m _ (low + high)/2; ENDLOOP; IF low=0 THEN IF LessEq[key, Key[p, 0]] THEN ret _ 0 ELSE IF high=sizePMinusOne AND Greater[key, Key[p, high]] THEN ret _ high+1 ELSE ret _ high ELSE IF high=sizePMinusOne AND Less[Key[p, high], key] THEN ret _ high+1 ELSE ret _ high; RETURN[ret] END; FindTheLastLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret: CARDINAL] = <> <> TRUSTED BEGIN pSize: CARDINAL _ p.pointer.size; low: CARDINAL _ 0; high: CARDINAL _ pSize - 1; m: CARDINAL; m _ (low + high)/2; UNTIL m = low DO IF GreaterEq[key, Key[p, m]] THEN low _ m ELSE high _ m; <> m _ (low + high)/2; ENDLOOP; IF low=0 THEN IF Less[key, Key[p,0]] THEN ret _ 0 ELSE IF high=pSize-1 AND GreaterEq[key, Key[p, high]] THEN ret _ high+1 ELSE ret _ high ELSE IF high=pSize-1 AND GreaterEq[key, Key[p,high]] THEN ret _ high+1 ELSE ret _ high END; FindTheInternalKey: PUBLIC PROC [ page: Page, key: IndexKey, Upper, Lower: PROC [IndexKey, IndexKey] RETURNS [BOOLEAN]] RETURNS [ret: CARDINAL] = <> <> TRUSTED BEGIN pageSize: CARDINAL _ page.pointer.size; max: CARDINAL _ pageSize - 1; min: CARDINAL _ 1; m: CARDINAL; IF min>max THEN RETURN[0]; DO m _ (max + min)/2; IF m = min THEN EXIT; IF Upper[key, Key[page, m]] THEN min _ m ELSE max _ m; <> <<(min=1 | Key[page, min](Upper)key)&(max=Size[page]-1|key(Lower)Key[page,max])>> ENDLOOP; IF min=1 THEN IF Lower[key,Key[page,min]] THEN ret _ 0 ELSE IF min#max AND max=pageSize - 1 AND Upper[key, Key[page,max]] THEN ret _ max ELSE ret _ min ELSE IF max=pageSize-1 AND Upper[key, Key[page,max]] THEN ret _ max ELSE ret _ min END; JustOver: PUBLIC PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL] = <> <> TRUSTED BEGIN i: CARDINAL; pSize: CARDINAL _ p.pointer.size; FOR i IN [0..pSize) DO IF p.pointer.index[i]+size < FullPage + (i + 1) THEN GOTO Over; REPEAT Over => RETURN[i]; FINISHED => RETURN[pSize - 1]; ENDLOOP; END; END. Change Log Changed the meaning of FindTheLastLeafKey by Suzuki: November 24, 1980 1:09 PM Changed JustOver to match the meaning by Suzuki: December 2, 1980 9:46 AM Changed FindTheInternalKey to assign min to ret in the most general case by Suzuki: December 3, 1980 9:28 AM Changed FindTheInternalKey so that it can handle 1 entry page by Suzuki: December 3, 1980 1:11 PM Allocate storage from DBHeapStorage. by MBrown: February 27, 1981 6:34 PM Added checks on key lengths, index passed to CoreAddr, and FreeSize returned value. by Cattell: June 19, 1982 3:51 pm Changed name of CopyIndexKey to CreateIndexKey. Added check on key length too big, and signal KeyTooBig. by Cattell: June 20, 1982 6:32 pm Changed FindTheFirstLeafKey to try to signal and attempt to push on if it encounters a zero-size page ('cause my personal database is in a rubble of bits otherwise...) by Cattell: August 11, 1982 10:15 am Removed some procs to DBIndexModImpl. Moved some procs here. by Cattell: September 21, 1982 8:37 pm Fixed B-tree bug #19: this one took 4 man-hours, because it took so long to reproduce and involved a fairly complicated call stack. The symptom was a garbage key in the root node after a deletion. If re-arranging two sons of a node causes a new larger key to be stored in the node, which in turn is over threshold to cause the node to split, then in certain cases the pointer that SplitPage creates as the splitKey, the last key on the node, gets overwritten before it gets used by the grandparent. The solution is that SplitPage should copy the key. This ripples through several procedures in other modules which change their assumptions about allocation/deallocation of keys: DBIndexImpl.SplitInternal, etc. Changed by Willie-Sue on February 18, 1985 <>