DIRECTORY AlpineEnvironment USING [LockOption], DBCommon, IO USING [STREAM], Rope USING [ROPE]; DBStorage: CEDAR DEFINITIONS = BEGIN ROPE: TYPE = Rope.ROPE; SegmentID: TYPE = DBCommon.SegmentID; VersionOptions: TYPE = DBCommon.VersionOptions; Segment: TYPE = DBCommon.Segment; SegmentIndex: TYPE = DBCommon.SegmentIndex; TuplesetObjectSize: CARDINAL = 20; IndexObjectSize: CARDINAL = 20; FieldObjectSize: CARDINAL = 5; TupleHandle: TYPE = DBCommon.TupleHandle; TupleObject: TYPE = DBCommon.TupleObject; TuplesetHandle: TYPE = TupleHandle; SystemTuplesetHandle: TYPE = REF SystemTuplesetObject; SystemTuplesetObject: TYPE; SystemTupleID: TYPE = LONG CARDINAL; -- Really [1..MaxSystemTupleID] MaxSystemTupleID: CARDINAL = 128; FieldDescriptor: TYPE = RECORD[ variantPart: SELECT basicType: FieldClass FROM OneWord,TwoWord => NULL, NWord => [length: CARDINAL], VarWord,VarByte => [lengthHint: CARDINAL], Group => [groupID: GroupID], ENDCASE ];--FieldDescriptor FieldClass: TYPE = {OneWord, TwoWord, NWord, VarWord, VarByte, Group}; FieldHandle: TYPE = REF FieldObject; FieldObject: TYPE; ListOfFieldHandle: TYPE = LIST OF FieldHandle; TuplesetScanHandle: TYPE = REF TuplesetScanObject; TuplesetScanObject: TYPE; GroupID: TYPE = TupleHandle; GroupScanHandle: TYPE = REF GroupScanObject; GroupScanObject: TYPE; IndexHandle: TYPE = TupleHandle; IndexScanHandle: TYPE = REF IndexScanObject; IndexScanObject: TYPE; Selection: TYPE = RECORD[lowerBound, upperBound: Rope.ROPE, includeLowerBound, includeUpperBound: BOOLEAN, lowerBoundInfinity, upperBoundInfinity: BOOLEAN _ FALSE]; Initialize: PROC [nCachePages: NAT, cacheFileName: ROPE]; AttachSegment: PROC [fileName: ROPE, s: Segment, segmentIndex: SegmentIndex, lock: AlpineEnvironment.LockOption, readonly: BOOL, version: VersionOptions, nPagesInitial, nPagesPerExtent: NAT]; MakeTransaction: PROC[server: Rope.ROPE] RETURNS[t: DBCommon.Transaction]; OpenTransaction: PROC [segment: Segment, handle: DBCommon.TransactionHandle, eraseAfterOpening: BOOL _ FALSE]; FinishTransaction: PROC [handle: DBCommon.TransactionHandle, abort: BOOL, continue: BOOL]; CreateTupleset: PROC [x: TuplesetHandle]; CreateSystemTupleset: PROC [x: SystemTupleID] RETURNS [SystemTuplesetHandle]; SetSystemTupleTable: PROC [REF ARRAY [1..MaxSystemTupleID] OF TupleHandle]; DestroyTupleset: PROC [x: TuplesetHandle]; AddField: PROC [x: TuplesetHandle, y: FieldDescriptor] RETURNS [FieldHandle]; AddSystemField: PROC [x: SystemTuplesetHandle, y: FieldDescriptor] RETURNS [FieldHandle]; CreateFieldHandle: PROC RETURNS [FieldHandle]; DeleteField: PROC [x: TuplesetHandle, z: ListOfFieldHandle, i: INTEGER] RETURNS [ListOfFieldHandle]; FirstLast: TYPE = DBCommon.FirstLast; OpenScanTupleset: PROC [--x-- TuplesetHandle, --start-- FirstLast] RETURNS [TuplesetScanHandle]; NextScanTupleset: PROC [--x-- TuplesetScanHandle] RETURNS [TupleHandle]; PrevScanTupleset: PROC [--x-- TuplesetScanHandle] RETURNS [TupleHandle]; CloseScanTupleset: PROC [--x-- TuplesetScanHandle]; CreateTuple: PROC [x: TuplesetHandle, y: TupleHandle _ NIL] RETURNS [newTuple: TupleHandle]; CreateSystemPageTuple: PROC [x: SystemTuplesetHandle, y: TupleHandle, s: Segment] RETURNS [newTuple: TupleHandle]; DestroyTuple: PROC [x: TupleHandle]; FreeTupleHandle: PROC [x: TupleHandle]; ConsSystemTupleObject: PROC [] RETURNS [TupleHandle]; ReadTupleset: PROC [x: TupleHandle] RETURNS [TuplesetHandle]; Read1Word: PROC [x: TupleHandle, f: FieldHandle] RETURNS [CARDINAL]; Read2Word: PROC [x: TupleHandle, f: FieldHandle] RETURNS [LONG CARDINAL]; ReadNWord: PROC [x: TupleHandle, f: FieldHandle, space: REF ANY]; ReadVarByte: PROC [x: TupleHandle, f: FieldHandle] RETURNS [Rope.ROPE]; ReadVarByteViaStream: PROC [x: TupleHandle, f: FieldHandle] RETURNS [IO.STREAM]; ReadVarWord: PROC [x: TupleHandle, f: FieldHandle] RETURNS [DESCRIPTOR FOR ARRAY OF CARDINAL]; Write1Word: PROC [x: TupleHandle, f: FieldHandle, val: CARDINAL]; Write2Word: PROC [x: TupleHandle, f: FieldHandle, val: LONG CARDINAL]; WriteNWord: PROC [x: TupleHandle, f: FieldHandle, val: REF ANY]; WriteVarByte: PROC [x: TupleHandle, f: FieldHandle, val: Rope.ROPE]; WriteVarByteViaStream: PROC [x: TupleHandle, f: FieldHandle, val: IO.STREAM]; WriteVarWord: PROC [x: TupleHandle, f: FieldHandle, val: DESCRIPTOR FOR ARRAY OF CARDINAL]; ReadTID: PROC [--x-- TupleHandle, --f-- FieldHandle] RETURNS [--z-- TupleHandle]; GetGroupIDs: PROC [--z-- TupleHandle] RETURNS [LIST OF GroupID]; OpenScanGroup: PROC [--z-- TupleHandle, --f-- FieldHandle, --start-- FirstLast] RETURNS [--r-- GroupScanHandle]; WriteTID: PROC [--x-- TupleHandle, --r-- GroupScanHandle]; WriteTIDNil: PROC [--x-- TupleHandle, --f-- FieldHandle]; NextInGroup: PROC [--r-- GroupScanHandle] RETURNS [--x-- TupleHandle]; PrevInGroup: PROC [--r-- GroupScanHandle] RETURNS [--x-- TupleHandle]; CloseScanGroup: PROC [--r-- GroupScanHandle]; RootIndicesFromSegment: PROC [s: Segment] RETURNS [indices: ARRAY[0..DBCommon.systemIndexCount) OF IndexHandle]; CreateIndex: PROC [x: IndexHandle]; DestroyIndex: PROC [x: IndexHandle]; InsertIntoIndex: PROC [x: IndexHandle, k: Rope.ROPE, v: TupleHandle]; DeleteFromIndex: PROC [x: IndexHandle, k: Rope.ROPE, v: TupleHandle]; OpenScanIndex: PROC [x: IndexHandle, y: Selection, startPosition: FirstLast] RETURNS [IndexScanHandle]; NextScanIndex: PROC [x: IndexScanHandle] RETURNS [tuple: TupleHandle]; PrevScanIndex: PROC [x: IndexScanHandle] RETURNS [tuple: TupleHandle]; PrevScanKey: PROC[x: IndexScanHandle] RETURNS [key: DBCommon.IndexKey]; NextScanKey: PROC[x: IndexScanHandle] RETURNS [key: DBCommon.IndexKey]; ThisScanTuple: PROC[x: IndexScanHandle] RETURNS [tuple: TupleHandle]; IgnoreEntry: PROC[x: IndexScanHandle]; CloseScanIndex: PROC [x: IndexScanHandle]; END. -- DBStorage 7ćFile DBStorage.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Last edited by: MBrown on December 16, 1982 2:46 pm Cattell on September 14, 1983 4:12 pm Willie-Sue on February 21, 1985 6:09:37 pm PST Widom, September 3, 1985 2:58:54 pm PDT Donahue, March 10, 1986 8:45:04 am PST This interface contains all procedures defined by the storage level and used by the tuple level. CONSTANTS and TYPES Sizes of data structures that are shared between storage and tuple levels: tupleset, index, and field "objects". Apart from this size information, these objects are opaque above the storage level. FieldObjects do not change unless DeleteField is done, so these may be cached by the tuple level; FieldObjects are stored in the database, but pointers to in-core copies are always passed to the storage level. Tupleset and Index objects may change due to tuple creation, index insertion, etc; these are stored in the database and accessed directly by the storage level, using the convention that the first-created field in a tuple containing a Tupleset or Index object must contain the object, and have the agreed-upon size. The first-created field of this tuple is an NWord field of length TuplesetObjectSize, which is used to store the tupleset object (containing information about the tupleset such as the size of a tuple and the list of pages that contain tuples from this tupleset). A tupleset object is never copied, it is always updated in place. Defined in DBStorageConcrete. Supplied as an argument to CreateSystemTupleset. CreateSystemPageTuple assigns this number as tupleset ID, and whenever a tupleset ID is turned into a tuple, it is range-checked to see if it is a system tupleset. Number of words in the field Number of words/bytes that can be stored inline in the field A GroupID is a TupleHandle. The TID contained therein is considered to be the unique ID of the Group field. Normally this is the TID of a dictionary tuple that describes this attribute. In the case of the attributes of the dictionary tuples themselves, a SystemTupleID is used; this points to no real tuple. A FieldDescriptor is used only as a parameter to AddField. The FieldHandle is used to do field read/writes. The interface implies that a field handle actually contains the FieldDescriptor that was used to create it, as well as other stuff such as the offset within the tuple, etc. The FieldObject is allocated by a call to CreateFieldHandle, then filled in by ReadNWord. Defined in DBStorageConcrete. Defined in DBStorageConcrete. The first-created field of this tuple is an NWord field of length IndexObjectSize, which is used to store the index object (information about the index such as the location of the root page). An index object is never copied, it is always updated in place. Defined in DBStorageConcrete. Notes on allocation of storage for interface objects FieldDescriptor, Selection: Alloc/Dealloc by tuple level. FieldHandle: Created by storage level, copied to database by tuple level, then deallocated by tuple level (who thus must know correct pool). Copied from database, then alloc/dealloc by tuple level. Initialization Initializes the database system. Use nCachePages pages for cache size. Segment/Transaction interface This operation "attaches" given segment to a given section of the database system's internal address space. At most one segment may be attached to a particular section. When a transaction is opened on this segment, using OpenTransaction (below), the following actions occur. The file with full path name fileName is looked up on the appropriate server. If the file is not there and version = OldFileOnly, ERRORs DBException.BadOperation[FileNotFound]; if it is there and version = NewFileOnly, ERRORs DBException.BadOperation[FileAlreadyExists]. Otherwise, creates a new segment or returns an existing one with the given name, as appropriate. In creating a new segment, at least nPagesInitial pages are allocated, and nPagesPerExtent pages will be allocated whenever the newly-created segment is extended. If readonly, then any subsequent request to write into the segment will raise an ERROR. Things are organized in this peculiar way so that an application may attach segments just once, even though it may execute many transactions (some of which may abort) on the segments. Note the lack of a "DetachSegment" proc. Return a transaction on the given server. This can be used to build a TransactionHandle to be passed to OpenTransaction below Open a transaction for the segment, attaching the segment to the transaction handle provided. If eraseAfterOpening is TRUE, then the segment is emptied after opening and the transaction is marked (committed) If NOT abort AND continue, then all segments using the indicated transaction continue to have a transaction, but updates to these segments have been committed. Tupleset interface The procedures in this group deal with the definition and manipulation of the entire set of tuples of a given type. Some involve either implicit or explicit sequencing through a tuple set; the search order is system-defined. 1) Definition. Creates a new tupleset, whose tuples have no fields, in the same segment as x. The parameter x is an existing tuple whose first-created field is an NWord field, TuplesetObjectLength words long. Information describing the new tupleset is placed in this field. Tuple x is returned by a ReadTupleset call (see next page) on any tuple created in this tupleset. Note that the TuplesetHandle is used primarily by CreateTuple, but is also modified by AddField/DeleteField. Creates a new system tupleset (system tuplesets do not live in a single segment and pages containing their tuples are not chained together at storage level). The system tuple table defines TupleHandles that represent the system tuples. There are two cases in which a storage level operation needs to return a system tuple. These are ReadTupleset and GetGroupIDs, applied to a dictionary tuple. In these cases the storage level is careful to check for a TID in the range [1..MaxSystemTupleID], and when one is encountered the corresponding entry from the system tuple table is returned. In effect this procedure performs DestroyTuple on every tuple of the set described by x, and undoes whatever was done by the CreateTupleset call that created the tupleset. Any further user of TuplesetHandle x is an error. (DestroyTupleset has no effect on system tuplesets). In effect this procedure modifies each tuple of set x, adding a new field of type y. It returns a FieldHandle for the new field. This procedure adds to x the length of y. Returns a FieldHandle for the new field. Since the FieldObject type is opaque, this procedure is needed to allocate a FieldHandle, to be passed to ReadNWord when retrieving a FieldHandle stored in the data schema. In effect this procedure modifies each tuple of set x, deleting the i-th field in list z. Parameter z describes all of the fields of tuples in x, and the result gives new handles for the undeleted fields, in the same order (handles will change due to deletion). Note: will the field handles be presented in order of creation? This avoids a sort. (DeleteField NOT be implemented in the first system). 2) Navigation. We provide a collection of functions to scan through a tupleset and return all of the tuples that satisfy a predicate called a selection. Informally, a selection is a disjunction of comparisons (equality, inequality, or range) on some subset of fields. Initializes for a sequential search through all tuples in set x. Starts scan either before first tuple or after last, according to start parameter. Returns the next tuple in the scan, or NIL when the scan is empty. The TuplesetScanHandle is modified as a side-effect of the Next call. Returns the previous tuple in the scan, or NIL when the scan is empty. The TuplesetScanHandle is modified as a side-effect of the Prev call. Destroys the TuplesetScanHandle x. Tuple interface: The procedures in this group deal with individual tuples. 1) Creation and destruction. Attempts to create a new tuple of type x "near" existing tuple y. (If y=NIL then this creates a new tuple of type x, according to the default algorithm for tupleset x.). Returns with newTuple=NIL iff this is not possible; in this case no tuple has been created. Attempts to create a new system tuple of type x on the same page as existing system tuple y. If this is not possible, the new tuple placed on an otherwise empty page in the same segment as tuple y. If y = NIL then the new tuple is placed on an otherwise empty page in segment s. Note that s is completely ignored when y # NIL, and that unlike CreateTuple, this procedure ALWAYS creates a tuple. Destroys tuple x, then performs FreeTupleHandle[x] (see below). Logical no-op and not necessary, though may free some storage structures. Allocates a new TupleObject with no particular contents. 2) Field access. We provide individual routines for each value type. Two parameters are common to most of the routines in this section: x, the tuple to be accessed, and f, a FieldHandle describing the position within tuple x containing the value to be read or written. The storage for values returned from ReadNWord and ReadVarWord is acquired from a single internal heap allocator; this allocator may someday appear in the interface. Pointers to cached pages are NOT given out as values; database values are alwaye copied. Returns a tuple handle for the tuple representing x's tupleset. Returns an n-word record, where n is encoded in f, storing it into the locations space..space+n-1 (beware!). The result stream can to GetChar, GetBlock, EndOf, etc. The val parameter points to an n-word record, where n is known from f. The val stream must do GetChar, GetBlock, EndOf, etc. Group interface A group is an ordered list of tuples, used in representing one-many relationships. The relationship is between the group's head, which is a single tuple, and the group itself. The relationship is named; we say that "x belongs to a g-group" if x has a TID field with groupID g, and this field has a non-null value z; z is the head of the group. The groupID g is bound into the field handle f of a TID field when it is created. Thus it also makes sense to call a group an f-group when f is a TID field handle. One tuple may be head of an unlimited number of groups, but only one g-group for any groupID g. A GroupScanHandle is a handle on a group. It specifies a position that is either before the first tuple, between two consecutive tuples, or after the last tuple. It is used both for scanning through a group and for specifying a position to insert a new tuple in a group. The tuple level is responsible for using the storage level primitives in ways that preserve stronger invariants. Note also that the storage level does not implement a set structure for groups. Thus it is not possible for the storage level to sequence through all of the groups of a given type, as it can do for tuples. If x belongs to an f-group, ReadTID returns the head of the group; otherwise it returns NIL. Returns a list containing all GroupIDs g such that z is the head of a g-group. The Tuple level is responsible for mapping from GroupIDs to FieldHandles, so that the next procedure can be called when necessary. Returns a GroupScanHandle positioned before the first (or after the last) tuple of the f-group that has tuple z as head (first or last depending upon the value of start). Returns a non-NIL GroupScanHandle even if there is no group. Makes tuple x join the group specified by r at r's current position (i.e. between the tuple just read and the next tuple that would be read by NextInGroup). A NextInGroup following WriteTID returns the tuple following x; a PrevInGroup returns x itself. Note that: (1) if x's field y had a non-NIL value before the WriteTID call, then WriteTID has the effect of deleting x from some group (using WriteTIDNIL below), (2) WriteTID cannot delete a tuple from one group without inserting it into another, so WriteTIDNil below is necessary for that case, and (3) inserting or deleting a tuple from a group requires the storage level to check all outstanding GroupScanHandles to assure that they stay consistent with the deletion. Makes x's TID field point to the null tuple, i.e. removes x from whatever f-group it currently belongs. Returns the tuple x immediately following the position r in a group, and moves r one position forwards. Returns NIL if r was already positioned after the last tuple in the group. Returns the tuple x immediately preceding the position r in a group, and moves r one position backwards. Returns NIL if r was already positioned before the first tuple in the group. The group interface may be expanded in the future to allow searches by value within a group, especially if we choose to support ordered groups. Index interface 1) Definition. An index implements a map from byte string keys to doubleword values. The byte strings are ordered in the obvious way, and the index allows efficient range queries on key values. Note that the tuple level is responsible for mapping tuple field values into keys that can be compared using the simple-minded routine in the storage level, and for ensuring that all of and only the tuples of a single type are actually entered into an index. Each segment has a small collection of builtin index handles Creates a new index. x is a tuple whose first-created field is an NWord field, IndexObjectSize words long. Information about the index is stored in this field. Pages for the index are obtained from the segment containing tuple x. Destroys the index x. 2) Maintainance. These routines allow insertion and deletion of associations in an index. Associates value v with key k . Deletes the given association from the index (v is necessary since multiple values may be present for the same key). ERRORs DBException.InternalBug[...] if the association is not present in the index x. 3) Navigation. Two means of navigating through indices are provided, either by using the Next and Previous operators to return tuple handles or by enumerating all of the keys in a certain range and then selecting those tuples that are of interest. ťĘ ăšś™Jšś Ďmś1™<—šś™Jšś#™#Jšś%™%Jšś.™.J™'Icode™&J—šĎk Jšśžś%J JšžśžśžśJšśžśžśJ—Jšśžśžśž$JšžśžśžśJšśžś%Jšśžś/JJšś žś!Jšśžś+JJšśS™SJšś™JJšś™JJšśžś"JšśžśJšśžśJšśŐ™ŐJJšś žś)Jšś žś)JJšśžś#JšśÉ™ÉJJšśžśžś6JšśžśJšś™JJšśžśžśžśĎcDJšśžś!JšśŐ™ŐJšśžśžśšś žśž.JšśžśšśžśJšś™—šś žś*Jšś<™<—Jšś¶™¶——Jšž—JšśźJšś:™:JJšśžś7GJJšś žśžś $Jšś žśJšśžśžśžś .Jšśą™ąJJšśžśžś2šśžśJšś™J—Jšś žśJJšśžśžś,šśžśJšś™J—Jšś žś Jšś€™€JJšśžśžś,šśžśJšś™J—šśžśžśžś;Jšś&žś.Jšś(žśžś9JJ—Jšś4™4JJšś9™9JJšśĹ™Ĺhead1šś™šĎn śžśžśžś9JšśG™G——šś™š śžśžśXžś;žśżJšś©™©JJšśŮ™ŮJJšśá™á—Jš śžśžśžśJJšś~™~—Jš śžśKžśžśnJšśĐ™Đ—Jš śžś-žśžśZJšśź™ź——šś™Jšśá™áJ™šś™Jš śžś)JšśÖ™Ö—Jš śžśžśMJšśť™ť—Jš śžśžśžśžśKJšś™—Jš śžś*Jšś’™’—Jš śžś)žśMJšś€™€—Jš śžś/žśYJšśR™R—Jš śžśžś.Jšś¬™¬—Jš śžś.žśžśdJšś’™’——Jšś™Jšś˙™˙JJšśžś%Jš śžśźśź śžś`Jšś”™”—Jš śžśźśžśHJšś‰™‰—Jš śžśźśžśHJšśŤ™Ť—Jš śžśźś3Jšś"™"———šśK™Kšś™Jš śžś&žśžś\Jšś‡™‡—Jš śžś6žśrJšśŤ™Ť—Jš śžś$Jšś?™?—Jš śžś'JšśI™I—Jš śžśžś5Jšś8™8—J—šś™Jšśü™üJšś˙™˙Jš śžśžś=Jšś?™?J—Jš śžś"žśžśDJJš śžś"žśžśžśIJš śžś)žśžśAJšśl™lJ—Jš śžś"žśžśGJš śžś"žśžśžśPJšś7™7J—Jš śžś"žśž śžśžśžśžś^JJš śžś'žśAJJš śžś'žśžśFJš śžś'žśžś@JšśF™FJ—Jš śžś,žśDJš śžś'žśžśMJšś5™5J—Jš śžś'ž śžśžśžśžś[——šś™šśÝ™ÝJ—šśŹ™ŹJ—šśŔ™ŔJJš śžśźśźśžśźśSJšś\™\J—š śžśźśžśžśžś @JšśŃ™ŃJ—š śžśźśźśź śOšžśźś"Jšśč™čJ——š śžśźśźś:JšśÔ™ÔJ™—š śžśźśźś9Jšśg™gJ—š śžśźśžśźśHJšśł™łJ—š śžśźśžśźśHJšś¶™¶J—Jš śžśźś-JJšśŹ™Ź——šś™šśÂ™ÂJ—šś‚™‚Jš śžśžśžśžśpJšś<™<—Jš śžś#Jšśç™ç—Jš śžś$Jšś™——JšśZ™ZJš śžśžśEJšś™—Jš śžśžśEJšśŇ™Ň——Jšśř™řJJš śžś:žśgJJš śžśžśFJJš śžśžśFJJš śžśžśGJJš śžśžśGJJš śžśžśEJJš śžś&JJš śžś*J———JšžśźJ—…—ĐY™