UnsafePropList.mesa
Copyright Ó 1992 by Xerox Corporation. All rights reserved.
Created by Christian Jacobi, April 9, 1992 11:48:58 am PDT
Christian Jacobi, April 15, 1992 3:18 pm PDT
Package which allows applications to support property lists. The idea is to use UnsafePropList to implement property lists but to hide usage of UnsafePropList and support application specific safe access procedures. (This package uses less memory than Atom's implementation).
While simple property lists may be easy to implement inline, using this package guarantees a time and memory efficient implementation. It also provides some non-trivial primitives which would probably not be supported in casual implementations.
This package is UNSAFE because it deals with the addresses of property lists.
PropListContainer's must not be assigned directly (except NIL). E.g. Record assignment of things which contain PropListContainer's is not allowed. As this error is very easy to make, it is checked against at runtime before a property list is modified.
UnsafePropList does all the necessary monitoring to allow asynchronous acces to a property list.
UnsafePropList: CEDAR DEFINITIONS ~
BEGIN
PropListAddr:
TYPE =
LONG
POINTER <<
TO PropListContainer>>;
Use listAddr: PropListAddr ¬ @x if x is of a type like PropListContainer
PropListContainer: TYPE = REF ¬ NIL; --Applications may use their own types instead; all which is required is that the type used by the application has the same size, and, initializes to NIL.
GetProp:
PROC [listAddr: PropListAddr, key:
REF]
RETURNS [
REF];
Fetches a value from the property list; returns NIL if not found.
PutProp:
PROC [listAddr: PropListAddr, key, val:
REF]
RETURNS [
REF];
Puts a property (key value pair) on the property list and returns the previous value.
A NIL value removes the property.
RemProp:
PROC [listAddr: PropListAddr, key:
REF]
RETURNS [
REF];
Like PutProp[listAddr, key, NIL]
ConditionalPutProp:
PROC [listAddr: PropListAddr, key, expect, new:
REF]
RETURNS [val:
REF, done:
BOOL];
Atomically val ¬ GetProp[listAddr, key]; done ¬ (val=expect); IF done THEN [] ← PutProp[listAddr, new];
InitializeProcType:
TYPE ~
PROC [data:
REF, key:
REF]
RETURNS [val:
REF ¬ $x];
Type used for procedure initializing property.
GetPropOrInit:
PROC [listAddr: PropListAddr, key:
REF, init: InitializeProcType, data:
REF ¬
NIL]
RETURNS [val:
REF, done:
BOOL];
Atomically executes init exactly when the property list has no key property, then puts the return value as key property. (Atomic versus other calls of GetPropOrInit using the same listAddr and the same key only).
Returns value of property, and, whether init was called.
Simple calls of PutProp, RemProp, ConditionalPutProp, NiloutPropList etc. even with the same key are not blocked while init executes. However, of course, the value returned from init is put on the list atomically versus all other operations.
EachPropProc:
TYPE =
PROC [data:
REF, key, val:
REF]
RETURNS [quit:
BOOL ¬
FALSE];
Type used for procedure enumerating properties on list.
Enumerate:
PROC [listAddr: PropListAddr, map: EachPropProc, data:
REF ¬
NIL]
RETURNS [quit:
BOOL ¬
FALSE];
Enumerate the key value pairs of the property list in unspecified order.
Quits enumerating and returns TRUE if map returns TRUE.
TrustedAddNewProp:
PROC [listAddr: PropListAddr, key, val:
REF];
Like PutProp except UnsafePropList trusts the caller that key is not found on property list (and avoid the checking). This is useful to avoid n**2 cost algorithms, like in the following examples:
1) key was just created with NEW.
2) listAddr was just created with NEW and it is initialized by copying another property list using Enumerate.
In case of violation, the property list might end up with multiple entries for the key, which might cause any UnsafePropList procedure to handle either, none or multiple values. However this would not cause UnsafePropList to crash.
NiloutPropList:
PROC [listAddr: PropListAddr];
Like listAddr ¬ NIL, but better. Does not raise errors, even if the PropListContainer-assignement test fails.
CopyPropList:
PROC [destAddr, sourceAddr: PropListAddr];
Assigns a copy of sourceAddr to destAddr. The previous contents of destAddr is lost. Making a copy is an atomic operation, so is the assignment. However, the monitor lock may be released after the copy and re-aquired for the assignment.
END.