DIRECTORY
YggEnvironment,
YggInternal,
Basics,
BasicTime,
YggDID,
YggFileLock,
YggLock,
YggLockControl,
YggLockInternal,
YggDummyProcess,
Rope,
YggTransactionMap;

YggLockCoreImpl: CEDAR MONITOR
IMPORTS
Basics,
BasicTime,
YggFileLock,
YggDID,
YggDummyProcess,
Rope,
YggTransactionMap,
YggLockInternal
EXPORTS
YggDID,
YggInternal,
YggLock,
YggLockControl,
YggLockInternal
= BEGIN

DID: PUBLIC TYPE ~ REF DIDRep;
DIDRep: PUBLIC TYPE ~ Rope.ROPE;



LockID: TYPE = YggLock.LockID;
nullLockID: LockID = YggLock.nullLockID;
LockMode: TYPE = YggLock.LockMode;
ModeReleasableSet: TYPE = YggLock.ModeReleasableSet;
Lock: TYPE = YggLockInternal.Lock;
LockRep: TYPE = YggLockInternal.LockRep;
Header: TYPE = YggLockInternal.Header;
Request: TYPE = YggLockInternal.Request;
GrantedRequest: TYPE = YggLockInternal.GrantedRequest;
WaitingRequest: TYPE = YggLockInternal.WaitingRequest;
LockTransHeader: TYPE = YggLockInternal.LockTransHeader;


LockTransHeaderObject: PUBLIC TYPE = YggLockInternal.LockRep.request.transHeader;
Failed: PUBLIC ERROR [why: YggEnvironment.LockFailure] = CODE;
Error: PUBLIC ERROR [YggLock.ErrorType] = CODE;
TransAborting: PUBLIC ERROR = CODE;


Compat: PUBLIC ARRAY LockMode OF PACKED ARRAY LockMode OF BOOL _ [
none: [none: TRUE, read: TRUE, update: TRUE, write: TRUE,
readIntendUpdate: TRUE, readIntendWrite: TRUE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE],
read: [none: TRUE, read: TRUE, update: TRUE, write: FALSE,
readIntendUpdate: TRUE, readIntendWrite: FALSE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE],
update: [none: TRUE, read: TRUE, update: FALSE, write: FALSE,
readIntendUpdate: FALSE, readIntendWrite: FALSE,
intendRead: TRUE, intendUpdate: FALSE, intendWrite: FALSE],
write: [none: TRUE, read: FALSE, update: FALSE, write: FALSE,
readIntendUpdate: FALSE, readIntendWrite: FALSE,
intendRead: FALSE, intendUpdate: FALSE, intendWrite: FALSE],
readIntendUpdate: [none: TRUE, read: TRUE, update: FALSE, write: FALSE,
readIntendUpdate: FALSE, readIntendWrite: FALSE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE],
readIntendWrite: [none: TRUE, read: FALSE, update: FALSE, write: FALSE,
readIntendUpdate: FALSE, readIntendWrite: FALSE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: FALSE],
intendRead: [none: TRUE, read: TRUE, update: TRUE, write: FALSE,
readIntendUpdate: TRUE, readIntendWrite: TRUE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE],
intendUpdate: [none: TRUE, read: TRUE, update: FALSE, write: FALSE,
readIntendUpdate: TRUE, readIntendWrite: TRUE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE],
intendWrite: [none: TRUE, read: FALSE, update: FALSE, write: FALSE,
readIntendUpdate: FALSE, readIntendWrite: FALSE,
intendRead: TRUE, intendUpdate: TRUE, intendWrite: TRUE]];

Sup: PUBLIC ARRAY LockMode OF PACKED ARRAY LockMode OF LockMode _ [
none: [none: none, read: read, update: update, write: write,
readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite,
intendRead: intendRead, intendUpdate: intendUpdate, intendWrite: intendWrite],
read: [none: read, read: read, update: update, write: write,
readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite,
intendRead: read, intendUpdate: readIntendUpdate, intendWrite: readIntendWrite],
update: [none: update, read: update, update: update, write: write,
readIntendUpdate: update, readIntendWrite: update,
intendRead: update, intendUpdate: update, intendWrite: update],
write: [none: write, read: write, update: write, write: write,
readIntendUpdate: write, readIntendWrite: write,
intendRead: write, intendUpdate: write, intendWrite: write],
readIntendUpdate: [none: readIntendUpdate,
read: readIntendUpdate, update: update, write: write,
readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite,
intendRead: readIntendUpdate, intendUpdate: readIntendUpdate,
intendWrite: readIntendWrite],
readIntendWrite: [none: readIntendWrite,
read: readIntendWrite, update: update, write: write,
readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite,
intendRead: readIntendWrite, intendUpdate: readIntendWrite,
intendWrite: readIntendWrite],
intendRead: [none: intendRead, read: read, update: update, write: write,
readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite,
intendRead: intendRead, intendUpdate: intendUpdate, intendWrite: intendWrite],
intendUpdate: [
none: intendUpdate, read: readIntendUpdate, update: update, write: write,
readIntendUpdate: readIntendUpdate, readIntendWrite: readIntendWrite,
intendRead: intendUpdate, intendUpdate: intendUpdate, intendWrite: intendWrite],
intendWrite: [
none: intendWrite, read: readIntendWrite, update: update, write: write,
readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite,
intendRead: intendWrite, intendUpdate: intendWrite, intendWrite: intendWrite]];


lookupAndInsert: Header;
nLocks, nRequests, nSetCalls, nSetCallsWaited: INT;

MakeLockID: PUBLIC PROC  [did: DID] RETURNS [lock: LockID] ~ {
lockBuffer: ARRAY [0..24) OF CHAR _ ALL['\000];
noRootChar: INT;
sizeOfString: INT;
didAsRope: Rope.ROPE;
noRootChar _ Rope.Length[YggDID.RootPath];
didAsRope _ did^;
sizeOfString _ Rope.Length[didAsRope];
IF sizeOfString - noRootChar <= 24 THEN TRUSTED {
nBytes: CARD;
subFlatRope: Rope.Text;
subFlatRope _ Rope.Flatten[base: didAsRope, start: noRootChar];
nBytes _ Basics.ByteBlt[
from: [blockPointer: LOOPHOLE[subFlatRope, POINTER]+UNITS[TEXT[0]], startIndex: 0, stopIndexPlusOne: sizeOfString - noRootChar],
to: [blockPointer: @lockBuffer, startIndex: 0, stopIndexPlusOne: sizeOfString - noRootChar]
];
IF nBytes # sizeOfString THEN ERROR;
}
 ELSE {
charPos: INT _ sizeOfString;
storePos: INT _ 23;
WHILE charPos > noRootChar DO
nowChar: CHAR;
charPos _ charPos - 1;
nowChar _ Rope.Fetch[didAsRope, charPos];
IF nowChar = '/ THEN LOOP;
lockBuffer[storePos] _ nowChar;
storePos _ storePos -1;
IF storePos < 0 THEN EXIT;
ENDLOOP;
IF charPos > noRootChar THEN {
storePos _ 0;
WHILE charPos > noRootChar DO
nowChar: CHAR;
charPos _ charPos - 1;
nowChar _ Rope.Fetch[didAsRope, charPos];
IF nowChar = '/ THEN LOOP;
lockBuffer[storePos] _ LOOPHOLE[Basics.BITXOR[LOOPHOLE[lockBuffer[storePos]], LOOPHOLE[nowChar]]];
storePos _ storePos + 1;
IF storePos >= 24 THEN storePos _ 0;
ENDLOOP;
};
};
};


Set: PUBLIC ENTRY PROC [
trans: YggInternal.TransHandle, lock: LockID, mode: LockMode, wait: BOOL]
RETURNS [resultMode: LockMode] = {
h: Header;
wr: WaitingRequest _ NIL;
thisTransGrantedRequest: GrantedRequest;
useMode: LockMode;
{ -- EXITS CreateGrantedRequest, ConvertExistingRequest
nSetCalls _ nSetCalls + 1;
lookupAndInsert.lockID _ lock;
IF (h _ LookupAndInsert[lookupAndInsert]) = lookupAndInsert THEN {
lookupAndInsert _ NEW[LockRep.header _ [body: header []]];
lookupAndInsert.requestList _ lookupAndInsert;
nLocks _ nLocks + 1;
GOTO CreateGrantedRequest;
};
useMode _ mode;
DO
{ -- EXITS Conflict, TryConversionMode
{ -- EXITS NoWaitingRequests, WaitingRequests
thisTransGrantedRequest _ NIL;
FOR r: Lock _ h.requestList, r.requestList DO
WITH r SELECT FROM
hh: Header=> GOTO NoWaitingRequests;
rh: Request =>
WITH rh SELECT FROM
grh: GrantedRequest => {
IF grh.trans = trans THEN thisTransGrantedRequest _ grh
ELSE IF NOT Compat[useMode][grh.mode] THEN GOTO CannotGrant;
};
wrh: WaitingRequest => {
IF wr # NIL AND wr # wrh THEN GOTO CannotGrant;
GOTO WaitingRequests;
};
th: LockTransHeader => ERROR;
ENDCASE;
ENDCASE;
ENDLOOP;
EXITS
NoWaitingRequests => {
IF thisTransGrantedRequest = NIL THEN GOTO CreateGrantedRequest;
IF Sup[mode][thisTransGrantedRequest.mode] = useMode THEN
GOTO ConvertExistingRequest;
GOTO TryConversionMode;
};
WaitingRequests => {
IF thisTransGrantedRequest # NIL AND
Sup[mode][thisTransGrantedRequest.mode] # useMode THEN
GOTO TryConversionMode;
IF wr # NIL THEN {
UnregisterWaitingRequest[wr];
RemoveFromRequestList[r: wr, deleteHeaderIfNoRequests: FALSE];
nRequests _ nRequests - 1;
};
IF thisTransGrantedRequest # NIL THEN GOTO ConvertExistingRequest;
PromoteWaitingRequests[h, trans];
GOTO CreateGrantedRequest;
};
};-- EXITS NoWaitingRequests, WaitingRequests
EXITS
CannotGrant => {
IF NOT wait THEN RETURN WITH ERROR Failed [conflict];
IF wr = NIL THEN {
wr _ RegisterWaitingRequest[trans, lock, mode];
EnterWaitingInRequestList[h, wr];
nRequests _ nRequests + 1;
nSetCallsWaited _ nSetCallsWaited + 1;
};
WAIT wr.somethingChanged;
IF wr.giveUp THEN {
UnregisterWaitingRequest[wr];
RemoveFromRequestList[wr];
SELECT wr.whyGivingUp FROM
abort => RETURN WITH ERROR TransAborting;
timeout => RETURN WITH ERROR Failed [timeout];
ENDCASE => ERROR;
};
useMode _ mode;
};
TryConversionMode => {
useMode _ Sup[mode][thisTransGrantedRequest.mode];
};
};-- EXITS Conflict, TryConversionMode
ENDLOOP;
EXITS
CreateGrantedRequest => {
t: LockTransHeader = YggTransactionMap.GetLockHeader[trans];
r: GrantedRequest _ NEW[LockRep.request.granted _ [
requestList: h.requestList, body: request [
trans: trans, transList: t.transList, lockID: lock, mode: mode, rest: granted [count: 1]]]];
h.requestList _ r;
t.transList _ r;
t.nLocks _ t.nLocks + 1;
nRequests _ nRequests + 1;
RETURN [mode];
};
ConvertExistingRequest => {
thisTransGrantedRequest.mode _ useMode;
thisTransGrantedRequest.count _ thisTransGrantedRequest.count + 1;
RETURN [useMode];
};
};-- EXITS CreateGrantedRequest, ConvertExistingRequest
};--Set

Release: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle, lock: LockID,
releasable: ModeReleasableSet] RETURNS [LockMode] = {
h: Header;
IF (h _ Lookup[lock]) = NIL THEN RETURN WITH ERROR Error [unknown];
FOR r: Lock _ h.requestList, r.requestList DO
WITH r SELECT FROM
hh: Header => RETURN WITH ERROR Error [unknown];
rh: Request =>
WITH rh SELECT FROM
grh: GrantedRequest =>
IF grh.trans = trans THEN {
IF releasable[grh.mode] = no THEN
RETURN WITH ERROR Error [lockUnreleasable];
IF (grh.count _ grh.count - 1) = 0 THEN {
UnlinkFromTrans[trans, grh];
RemoveFromRequestList[grh];
DemoteWaitingRequests[h, trans];
RETURN [none];
}
ELSE RETURN [grh.mode];
};
wrh: WaitingRequest => RETURN WITH ERROR Error [unknown];
th: LockTransHeader => ERROR;
ENDCASE;
ENDCASE;
ENDLOOP;
};

ReleaseFileLocks: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle, prototype: LockID, releasable: ModeReleasableSet] = {
transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans];
rNext: Request;
FOR rh: Request _ transHeader.transList, rNext DO
rNext _ rh.transList;
WITH rh SELECT FROM
grh: GrantedRequest =>
IF releasable[grh.mode] = yes THEN {
handleLockID: LockID _ YggLockInternal.LockIDFromRH[ grh ];
IF handleLockID.entity = prototype.entity AND handleLockID.subEntity = prototype.subEntity THEN {
UnlinkFromTrans[trans, grh];
RemoveFromRequestList[grh];
};
};
wrh: WaitingRequest => ERROR;
th: LockTransHeader => RETURN;
ENDCASE;
ENDLOOP;
};

RemoveFromRequestList: INTERNAL PROC [
r: Request, deleteHeaderIfNoRequests: BOOL _ TRUE] = {
rPred: Lock;
notifyDone: BOOL _ FALSE;
FOR rPred _ r.requestList, rPred.requestList UNTIL rPred.requestList = r DO
WITH rPred SELECT FROM
wrh: WaitingRequest =>
IF NOT notifyDone THEN {
NOTIFY wrh.somethingChanged;
notifyDone _ TRUE;
};
ENDCASE;
ENDLOOP;
IF rPred = r.requestList AND deleteHeaderIfNoRequests THEN {
rPred.requestList _ NIL;
Delete[NARROW[rPred]];
nLocks _ nLocks - 1;
}
ELSE {
rPred.requestList _ r.requestList;
};
r.requestList _ NIL;
nRequests _ nRequests - 1;
};

Initialize: PUBLIC ENTRY PROC [lockZoneInitialSize: INT, hashArraySize: NAT] = {
InitWaitingRequestList[];
InitializeHashTable[
numHashSlotsDesired: hashArraySize,
hashHandle: NEW[LockRep.header _ [body: header []]]];
lookupAndInsert _ NEW[LockRep.header _ [body: header []]];
lookupAndInsert.requestList _ lookupAndInsert;
nLocks _ 0;  nRequests _ 0;  nSetCalls _ 0;  nSetCallsWaited _ 0;
};



EnterWaitingInRequestList: INTERNAL PROC [
h: Header, wr: WaitingRequest] = {
r: Lock;
FOR r _ h, r.requestList UNTIL r.requestList = h DO ENDLOOP;
r.requestList _ wr;
wr.requestList _ h;
};

PromoteWaitingRequests: INTERNAL PROC [
h: Header, trans: YggInternal.TransHandle] = {
};

DemoteWaitingRequests: INTERNAL PROC [
h: Header, trans: YggInternal.TransHandle] = {
};


ConsTransHeader: PUBLIC PROC [trans: YggInternal.TransHandle]
RETURNS [lockHeader: LockTransHeader] = {
lockHeader _ NEW[LockRep.request.transHeader _ [body: request [
trans: trans, transList: NIL, mode: none, rest: transHeader [nLocks: 0]]]];
lockHeader.transList _ lockHeader;
RETURN [lockHeader];
};

UpgradeLocks: PUBLIC PROC [trans: YggInternal.TransHandle] = {
ugh: LockTransHeader = YggTransactionMap.GetLockHeader[trans];
r: Request _ ugh;
lockID: LockID;
DO
[r, lockID] _ GetNextInTransNeedingUpgrade[r];
IF r = NIL THEN RETURN;
[] _ Set[trans, lockID, Upgrade[r.mode], TRUE];
ENDLOOP;
};

GetNextInTransNeedingUpgrade: ENTRY PROC [r: Request]
RETURNS [next: Request, nextLockID: LockID] = {
FOR next _ r.transList, next.transList DO
IF ISTYPE[next, LockTransHeader] THEN RETURN [NIL, nullLockID];
IF NeedsUpgrade[next.mode] THEN EXIT;
ENDLOOP;
FOR h: Lock _ next.requestList, h.requestList DO
WITH h SELECT FROM
hh: Header => RETURN [next, hh.lockID];
ENDCASE;
ENDLOOP;
};


Upgrade: ARRAY LockMode OF LockMode _ [
none: none, read: read, update: write, write: write,
readIntendUpdate: readIntendWrite, readIntendWrite: readIntendWrite,
intendRead: intendRead, intendUpdate: intendWrite, intendWrite: intendWrite];

NeedsUpgrade: ARRAY LockMode OF BOOL _ [
none: FALSE, read: FALSE, update: TRUE, write: FALSE,
readIntendUpdate: TRUE, readIntendWrite: FALSE,
intendRead: FALSE, intendUpdate: TRUE, intendWrite: FALSE];

Downgrade: ARRAY LockMode OF LockMode _ [
none: none, read: read, update: read, write: read,
readIntendUpdate: read, readIntendWrite: read,
intendRead: intendRead, intendUpdate: intendRead, intendWrite: intendRead];

ReleaseLocks: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle] = {
transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans];
rNext: Request;
FOR r: Request _ transHeader.transList, rNext DO
rNext _ r.transList;
r.transList _ NIL;
r.trans _ NIL;
WITH r SELECT FROM
gr: GrantedRequest => RemoveFromRequestList[gr];
wr: WaitingRequest => ERROR;
th: LockTransHeader => RETURN;
ENDCASE;
ENDLOOP;
};

UnlinkFromTrans: INTERNAL PROC [
trans: YggInternal.TransHandle, gr: GrantedRequest] = {
transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[trans];
rPred: Request;
FOR rPred _ transHeader, rPred.transList UNTIL rPred.transList = gr DO ENDLOOP;
rPred.transList _ gr.transList;
gr.transList _ NIL;
gr.trans _ NIL;
transHeader.nLocks _ transHeader.nLocks - 1;
};

TransferLocks: PUBLIC ENTRY PROC [from, to: YggInternal.TransHandle] = {
transHeader: LockTransHeader = YggTransactionMap.GetLockHeader[from];
FOR r: Request _ transHeader.transList, r.transList DO
r.trans _ to;
IF NOT (YggFileLock.IsWholeFileLock[r.lockID] AND (r.mode=write OR r.mode=update)) THEN r.mode _ Downgrade[r.mode];	
IF r = transHeader THEN RETURN;
ENDLOOP;
};


waitingRequestList: WaitingRequest;

InitWaitingRequestList: INTERNAL PROC [] = {
waitingRequestList _ NEW[LockRep.request.waiting _ [body: request [
trans: NIL, transList: NIL, mode: none, rest: waiting [startTime: BasicTime.earliestGMT]]]];
};

RegisterWaitingRequest: INTERNAL PROC [
trans: YggInternal.TransHandle, lockID: LockID, mode: LockMode]
RETURNS [wr: WaitingRequest] = {
wr _ NEW[LockRep.request.waiting _ [
requestList: NIL, body: request [
trans: trans, transList: waitingRequestList.transList, lockID: lockID, mode: mode, rest: waiting [
startTime: BasicTime.Now[]]]]];
waitingRequestList.transList _ wr;
TRUSTED {YggDummyProcess.DisableTimeout[@wr.somethingChanged];};
};

UnregisterWaitingRequest: INTERNAL PROC [wr: WaitingRequest] = {
r: Request;
FOR r _ waitingRequestList, r.transList UNTIL r.transList = wr DO ENDLOOP;
r.transList _ wr.transList;
wr.transList _ NIL;
wr.trans _ NIL;
};

AbortWaitingRequests: PUBLIC ENTRY PROC [trans: YggInternal.TransHandle] = {
FOR r: Request _ waitingRequestList.transList, r.transList UNTIL r = NIL DO
IF r.trans = trans THEN
WITH r SELECT FROM
wr: WaitingRequest => {
wr.giveUp _ TRUE;
wr.whyGivingUp _ abort;
NOTIFY wr.somethingChanged;
};
ENDCASE => ERROR;
ENDLOOP;
};

TimeoutWaitingRequest: PUBLIC ENTRY PROC [wr: WaitingRequest] = {
wr.giveUp _ TRUE;
wr.whyGivingUp _ timeout;
NOTIFY wr.somethingChanged;
};

EnumerateWaitingRequests: INTERNAL PROC [
proc: PROC [wr: WaitingRequest] RETURNS [stop: BOOL]] = {
FOR r: Request _ waitingRequestList.transList, r.transList UNTIL r = NIL DO
IF proc[NARROW[r]].stop THEN RETURN;
ENDLOOP;
};

GetInfo: PUBLIC ENTRY PROC [
generalInfoProc: YggLockInternal.GeneralInfoProc,
lockEnumProc: YggLockInternal.LockEnumProc,
waitingRequestEnumProc: YggLockInternal.WaitingRequestEnumProc,
waitingRequestEnumProc2: YggLockInternal.WaitingRequestEnumProc] = {
IF generalInfoProc # NIL THEN
generalInfoProc[nLocks, nRequests, nSetCalls, nSetCallsWaited];
IF lockEnumProc # NIL THEN
EnumerateWithProc[lockEnumProc];
IF waitingRequestEnumProc # NIL THEN
EnumerateWaitingRequests[waitingRequestEnumProc];
IF waitingRequestEnumProc2 # NIL THEN
EnumerateWaitingRequests[waitingRequestEnumProc2];
};


HashHandle: TYPE = Header;
Key: TYPE = LockID;

PrimeTable: ARRAY PrimeTableIndex OF NAT _ [37, 67, 131, 257, 513, 1031, 2003];
PrimeTableIndex: TYPE = [0 .. 6];

ClientHashInit: PROC [numHashSlotsDesired: NAT]
RETURNS [numHashSlotsAllowed: NAT] = {
FOR i: PrimeTableIndex IN PrimeTableIndex DO
IF PrimeTable[i] >= numHashSlotsDesired THEN RETURN [PrimeTable[i]];
ENDLOOP;
RETURN [PrimeTable[PrimeTableIndex.LAST]];
};

ClientHash: INTERNAL PROC [hashHandle: HashHandle]
RETURNS [NAT--[0..numHashSlots)--] = INLINE {
ID6: TYPE = RECORD [a, b, c, d, e, f, g: WORD32];
RETURN [Basics.BITXOR[
Basics.BITXOR[
LOOPHOLE[hashHandle.lockID, ID6].b, LOOPHOLE[hashHandle.lockID, ID6].d],
Basics.BITXOR[
LOOPHOLE[hashHandle.lockID, ID6].f, LOOPHOLE[hashHandle.lockID, ID6].c]]
MOD numHashSlots];
};

ClientEqualKeys: INTERNAL PROC [hashHandle1, hashHandle2: HashHandle]
RETURNS [equal: BOOL] = INLINE {
ID5: TYPE = RECORD [a, b, c, d, e, f, g: CARD32];
RETURN [
LOOPHOLE[hashHandle1.lockID, ID5].b = LOOPHOLE[hashHandle2.lockID, ID5].b AND
LOOPHOLE[hashHandle1.lockID, ID5].d = LOOPHOLE[hashHandle2.lockID, ID5].d AND
LOOPHOLE[hashHandle1.lockID, ID5].c = LOOPHOLE[hashHandle2.lockID, ID5].c AND
LOOPHOLE[hashHandle1.lockID, ID5].e = LOOPHOLE[hashHandle2.lockID, ID5].e AND
LOOPHOLE[hashHandle1.lockID, ID5].a = LOOPHOLE[hashHandle2.lockID, ID5].a AND
LOOPHOLE[hashHandle1.lockID, ID5].f = LOOPHOLE[hashHandle2.lockID, ID5].f]
};

ClientSetKey: INTERNAL PROC [hashHandle: HashHandle, key: Key] = INLINE {
hashHandle.lockID _ key;
};


LookupAndInsert: INTERNAL PROC [hashHandle: HashHandle]
RETURNS [HashHandle] = INLINE {
index: NAT _ ClientHash[hashHandle];
FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next
UNTIL newHashHandle = NIL DO
IF ClientEqualKeys[newHashHandle, hashHandle]
THEN RETURN [newHashHandle];
ENDLOOP;   
hashHandle.next _  hashSlots[index];
hashSlots[index] _ hashHandle;
RETURN [hashHandle];
};
















hashSlots: REF HashSlots _ NIL;
HashSlots: TYPE = RECORD[SEQUENCE nSlots: NAT OF HashHandle];

numHashSlots: NAT _ 0;  -- boy, will they be sorry if they don't init this package.
lookupHashHandle: HashHandle _ NIL; -- for the "package's" use only.


HashPkgCallerProgrammingError: ERROR = CODE; -- various fatal conditions.
HashPkgDuplicateKey: ERROR = CODE; -- from Insert.


InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashHandle: HashHandle] =
BEGIN  -- errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0).
numHashSlots _ ClientHashInit[numHashSlotsDesired];
IF numHashSlots = 0 THEN ERROR HashPkgCallerProgrammingError;
lookupHashHandle _ hashHandle;
hashSlots _ NEW[HashSlots[numHashSlots]];
FOR index: NAT IN [0..numHashSlots)
DO hashSlots[index] _ NIL; ENDLOOP;
END;


Insert: INTERNAL PROCEDURE[hashHandle: HashHandle] = INLINE
BEGIN  -- errors: HashPkgDuplicateKey.
index: NAT _ ClientHash[hashHandle];
FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next
UNTIL newHashHandle = NIL
DO
IF ClientEqualKeys[newHashHandle, hashHandle]
THEN ERROR HashPkgDuplicateKey;
ENDLOOP;   
hashHandle.next _  hashSlots[index];
hashSlots[index] _ hashHandle;
END;


Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashHandle: HashHandle] = INLINE
BEGIN  -- returns hashHandle = NIL if not found.
ClientSetKey[lookupHashHandle, key];
FOR hashHandle _ hashSlots[ClientHash[lookupHashHandle]], hashHandle.next
UNTIL hashHandle = NIL
DO IF ClientEqualKeys[hashHandle, lookupHashHandle] THEN RETURN;
ENDLOOP;   
RETURN[NIL];
END;


Delete: INTERNAL PROCEDURE[hashHandle: HashHandle] = INLINE
BEGIN  -- errors: HashPkgCallerProgrammingError (not found).
index: NAT _ ClientHash[hashHandle];
prevHashHandle: HashHandle _ NIL;
FOR newHashHandle: HashHandle _ hashSlots[index], newHashHandle.next
UNTIL newHashHandle = NIL
DO
IF ClientEqualKeys[newHashHandle, hashHandle] THEN EXIT;
prevHashHandle _ newHashHandle;
REPEAT FINISHED => ERROR HashPkgCallerProgrammingError;
ENDLOOP;
IF prevHashHandle = NIL
THEN hashSlots[index] _ hashHandle.next
ELSE prevHashHandle.next _ hashHandle.next;
hashHandle.next _ NIL;
END;



EnumerateNext: INTERNAL PROCEDURE[prevHashHandle: HashHandle] RETURNS
[hashHandle: HashHandle] =
BEGIN  -- errors: none.
index: NAT;
IF prevHashHandle = NIL
THEN index _ 0
ELSE BEGIN index _ ClientHash[prevHashHandle];
FOR hashHandle _ hashSlots[index], hashHandle.next
UNTIL hashHandle = NIL
DO
IF ClientEqualKeys[hashHandle, prevHashHandle] THEN GOTO found;
REPEAT
found => BEGIN
IF hashHandle.next # NIL THEN RETURN[hashHandle.next];
index _ index + 1;
END;
ENDLOOP;
END;
UNTIL index >= numHashSlots
DO
IF hashSlots[index] # NIL THEN RETURN[hashSlots[index]];
index _ index + 1;
ENDLOOP;
RETURN[NIL];
END;


EnumerateWithProc: INTERNAL PROCEDURE[proc: PROCEDURE[hashHandle: HashHandle]
RETURNS[stop: BOOLEAN]] =
BEGIN  -- errors: none.
FOR index: NAT IN [0..numHashSlots)
DO
FOR hashHandle: HashHandle _ hashSlots[index], hashHandle.next
UNTIL hashHandle = NIL
DO IF proc[hashHandle] THEN RETURN;
ENDLOOP;
ENDLOOP;
END;


END.--LockCoreImpl

CHANGE LOG

Changed by MBrown on February 8, 1983 5:47 pm
Changed by MBrown on February 9, 1983 4:16 pm
"ÒYggLockCoreImpl.mesa
Copyright Ó 1984, 1988 by Xerox Corporation.  All rights reserved.
MBrown on January 31, 1984 10:04:32 am PST
Kupfer, July 23, 1984 11:16:49 am PDT
Carl Hauser, January 25, 1986 12:25:39 pm PST
Bob Hagmann May 3, 1988 2:35:29 pm PDT
NOTES
YggLock.Set has a long argument record.  It also calls YggTransactionMap.GetLockHeader, which can be avoided at the cost of being compilation dependent upon Worker (as LogImpl is).
Revise the ClientEqualKeys proc after conversion to Trinity instruction set.
Implement a better scheduling algorithm for waiting requests.
Do not call out of this monitor into any other Yggdrasil monitor.
For Phase 0, the DIDRep is just a string that names a directory (without the trailing /).
YggInternal.LockTransHeader
YggLock.Failed
YggLock.Error
YggLock.TransAborting
YggLock.Compat
YggLock.Sup
Holds a free lock header for use in Set.  Set may add this lock header to the lock data structure, in which case it replenishes this value by NEWing.  This odd arrangement keeps the interface to the hash routines simple and yet avoids the overhead of two hash calls for the most common case.
Instrumentation, available outside of the monitor through GetInfo.
Construct the lock identifier for the did
We know that the LockID is 6 32-bit words and that YggDID.DID is a Rope.  Fix this when we use real dids
Ignore the prefix that is common for all dids.
If the rest is less than 24 characters, copy it to the lockBuffer
 else copy all the non "/" characters into the buffer from right to left.
 If there are still characters, then xor them in fetching the characters from the buffer from right to left, but xoring cycically from left to right.
This does not generate a unique id, but is should be good enough until read dids are used.  Also, the id collisions only mean that extra lock conflicts will occur, but these should be none at all.
YggLock.Set
Holds lock header corresponding to LockID "lock".  This is a constant during execution of this procedure, even if the procedure waits. 
If this procedure waits, wr holds the record of the waiting request.
If this request is for a LockID already held in some mode by trans, thisTransGrantedRequest holds the existing granted request (reevaluated if the procedure waits).
Request is for a lock not previously held by any transaction.
The main loop.  This loop is traveled multiple times for two reasons:
(a) if the request is a conversion, the loop is traveled first with the requested mode, then again with the supremum of the current and requested modes.
(b) if the request cannot be granted without waiting, the loop is traveled by the request as it attempts to acquire the lock.  Only the first waiting request for a given LockID may acquire the lock, and usually this is the only request that wakes up when something interesting changes, but a request may travel the loop only to find that it is not first in line (and go right back to sleep) under some conditions.
Is useMode compatible with all granted requests for other transactions?
Is the lock granted in some mode to this transaction?
Is there a first waiting request for this lock (and are we it)?
This request is not first in line for this LockID, so go back to sleep.
All granted requests have been examined. 
This request will be granted.
This request cannot be granted now.  Wait or fail.
Create waiting request
This request is a conversion.  Retry with a stronger lock mode.
CreateGrantedRequest is outside of the loop to allow the loop to be bypassed when the request is for a LockID not previously held by any transaction.
YggLock.Release
YggLock.ReleaseFileLocks --  
NOTIFY the first waiting request, if any, following r.  Then remove r from its requestList.  If this leaves this requestList empty, delete the header.
Called from Set, Release, ReleaseLocks.
YggLockControl.Initialize
Scheduling policy for waiting requests.
The present scheduling algorithm for waiting requests is strict FIFO.  However, by elaborating the procedures EnterWaitingInRequestList, PromoteWaitingRequests, and DemoteWaitingRequests it is possible to implement System R's scheduling strategy (e.g. priority for waiting conversion requests), as well as others.
Link wr into h, by its requestList, where it belongs.
For now: link wr in at end of h's requestList.
We are about to grant a lock to transaction trans.  Promote any waiting requests for h from trans to be conversions.
For now: no-op.
We are about to release a lock now held by transaction trans.  Demote any waiting requests for h from trans to be non-conversions.  If the identity of the first waiting request changes, NOTIFY the new first waiting request.
For now: no-op.
Transaction lock list (one per transaction)
YggLockControl.ConsTransHeader
YggLockControl.UpgradeLocks
Note: Proc is EXTERNAL to monitor, so that it can call Set like a normal client.
This form of enumeration, and the unmonitored access to r.mode below, are ok because client will make no concurrent lock calls for this transaction.
Find next granted request needing upgrade, return NIL if none.
Find the LockID of this request, and return.
Upgrade function: Upgrade[e] is the lock mode that a lock of mode e must be converted to by UpgradeLocks.  NeedsUpgrade[e] = (Upgrade[e] # e).

Downgrade function:  Downgrade[e] is the mode that a lock of mode e must be converted to by TransferLocks in the process of Commit and continue.
YggLockControl.ReleaseLocks
Called from Release.
YggLockControl.TransferLocks
Waiting request list (global)
list (linked through the transList field) of all waiting lock requests.
permanent header node starts list.
each request represents a suspended process, waiting in this monitor.
YggLockControl.AbortWaitingRequests
YggLockInternal.TimeoutWaitingRequest
Client-supplied parameters to hash package begin here:
Goal is to make "not equal" determinations run as fast as possible, while not slowing "equal" determinations.
Doubleword "b" contains the least significant bits of the sequence number plus part of the processor ID.  Doubleword "d" contains part of the lock sub ID.
Special procedure for YggLock application.
Client-supplied parameters to hash package end here.
Hash table package.
Explanation of client-supplied parameters:
The procedure ClientHashInit is called during hash table initialization, to allow the hash function to precompute values based on the range and to make any small adjustments to the range that are necessary.
HashHandle must:
be a REF type.
contain a field "next" of type HashHandle, under the exclusive control of the hash package.
Key is an arbitrary type.
SetKey sets the "key value" associated with a HashHandle.  The key value must not change between the time the handle is Inserted into the table and the time it is deleted from the table.
Hash must be a function of the key value of the parameter "hashHandle".
EqualKeys must be the equality relation on the key values of the parameters "hashHandle1" and "hashHandle2".
Interface description:
InitializeHashTable: INTERNAL PROCEDURE[numHashSlotsDesired: NAT, hashHandle: HashHandle];
errors: HashPkgCallerProgrammingError (numHashSlotsDesired = 0).
Insert: INTERNAL PROCEDURE[hashHandle: HashHandle];
errors: HashPkgDuplicateKey.
Lookup: INTERNAL PROCEDURE[key: Key] RETURNS [hashHandle: HashHandle];
returns hashHandle = NIL if not found.
Delete: INTERNAL PROCEDURE[hashHandle: HashHandle];
errors: HashPkgCallerProgrammingError (not found).
EnumerateNext: INTERNAL PROCEDURE[prevHashHandle: HashHandle] RETURNS
[hashHandle: HashHandle];
errors: none.
prevHashHandle = NIL starts the enumeration, returned hashHandle = NIL is the end of the enumeration.  This procedure guarantees that any hashHandle in existence throughout the entire enumeration will be seen.  Other handles may or not not be seen.  HashHandles may be seen more than once.
EnumerateWithProc: INTERNAL PROCEDURE[proc: PROCEDURE[hashHandle: HashHandle]
RETURNS[stop: BOOLEAN]];
errors: none.
start of invariant hash package code:
The INTERNAL procedures below expect to be called from a client procedure holding the module monitor lock, which protects the following data structures:
errors:
prevHashHandle = NIL starts the enumeration, returned hashHandle = NIL is the end of the enumeration.  This procedure guarantees that any hashHandle in existence throughout the entire enumeration will be seen.  Other handles may or not not be seen.  HashHandles may be seen more than once.
end of invariant hash package code.
Bug in Set: did not decrement nRequests when a waiting request was granted.
Bug in Set: when deleting a waiting request that is about to be granted, RemoveFromRequestList deleted the lock header if the requestList was empty.  but Set was holding on to the lock header.  Added deleteHeaderIfNoRequests parm to fix.
Edited on July 23, 1984 11:16:08 am PDT, by Kupfer
Converted to Tioga node structure with Mesa formatting.


�Êê˜Icodeš
œ™š
œB™BKš
œ*™*K™%K™-K™&—K˜K˜Kš
œ™Kš
ϫ
™´
Kš
œL™LKš
œ=™=K˜K˜š
Ïk	˜	K˜K˜K˜K˜
Kš
œ˜Kš
œ˜K˜K˜K˜Kš
œ˜K˜K˜K˜—šœ�
˜Kš
œA™Aš
�˜K˜K˜
Kš
œ˜Kš
œ˜Kš
œ˜K˜K˜K˜—š
�˜Kš
œ˜Kš
œ˜K˜K˜K˜—Kšœ�˜K˜Kš�œ�œ
�œ�œ˜šœ�œ
�œ�	œ
˜ K™Y—K˜K˜K˜Kšœ�œ˜K˜(Kšœ
�œ˜"Kšœ�œ˜4Kšœ�œ˜"Kšœ	�œ˜(Kšœ�œ˜&Kšœ	�œ˜(Kšœ�œ"˜6Kšœ�œ"˜6Kšœ�œ#˜8K˜K˜šœ�œ/˜QKš
œ™—šœ�œ
�œ%�œ
˜>Kš
œ™—šœ�œ
�œ�œ
˜/Kš
œ
™
—šœ�œ
�œ�œ
˜#Kš
œ™K˜K˜—šœ�œ
�œ
�œ
�œ
�œ
�œ
�œ˜BKš
œ™š	œ
�œ�œ
�œ	�œ
˜9Kšœ�œ�œ
˜.Kšœ�œ�œ�œ˜9—š	œ
�œ�œ
�œ	�œ
˜:Kšœ�œ�œ
˜/Kšœ�œ�œ�œ˜:—š	œ�œ�œ
�œ	�œ
˜=Kšœ�œ�œ
˜0Kšœ�œ�œ�œ˜;—š	œ�œ�œ
�œ	�œ
˜=Kšœ�œ�œ
˜0Kšœ�œ�œ�œ˜<—š	œ�œ�œ
�œ	�œ
˜GKšœ�œ�œ
˜0Kšœ�œ�œ�œ˜:—š	œ�œ�œ
�œ	�œ
˜GKšœ�œ�œ
˜0Kšœ�œ�œ�œ˜:—š	œ�œ�œ
�œ	�œ
˜@Kšœ�œ�œ
˜.Kšœ�œ�œ�œ˜9—š	œ�œ�œ
�œ	�œ
˜CKšœ�œ�œ
˜.Kšœ�œ�œ�œ˜9—š	œ�œ�œ
�œ	�œ
˜CKšœ�œ�œ
˜0Kšœ�œ�œ�œ˜:K˜——š
œ�œ
�œ
�œ
�œ
�œ
�œ
˜CKš
œ™˜<K˜EK˜N—˜<K˜EK˜P—˜BK˜2K˜?—˜>K˜0K˜<—˜*K˜5K˜EK˜=K˜—˜(K˜4K˜DK˜;K˜—˜HK˜EK˜N—˜K˜IK˜EK˜P—˜K˜GK˜DK˜O——K˜K˜˜Kš
œ£™£—šœ/�œ
˜3Kš
œB™BK˜—š
Ïn
œ�œ
�œ�œ�œ˜>J™)Jšœ:�œ+™hJ™.Jš
œA™AJšœ;Ïbœ–
™ß
J™Ä
Jš	œ�œ	�œ
�œ�œ˜/Jšœ�œ
˜Jšœ�œ
˜Jšœ�œ
˜Jš
œ*˜*Jš
œ˜Jš
œ&˜&š�œ!�œ
�œ˜1Jšœ�œ
˜
Jš
œ˜Jš
œ?˜?Jš	œ.�œ�œ�œ
�œ¡
˜ø
Jš�œ�œ
�œ
˜$J˜
—šœ
�œ˜Jšœ	�œ˜Jšœ
�œ˜š�œ�˜Jšœ	�œ
˜Jš
œ˜Jš
œ)˜)Jš�œ�œ
�œ
˜Jš
œ˜Jš
œ˜Jš�œ�œ
�œ
˜Jš�œ
˜—š�œ�œ˜Jš
œ
˜
š�œ�˜Jšœ	�œ
˜Jš
œ˜Jš
œ)˜)Jš�œ�œ
�œ
˜Jš	œ�œ�œ
�œ�œ˜bJš
œ˜Jš�œ�œ˜$Jš�œ
˜—J˜—J˜—J˜—J˜J˜šžœ�œ
�œ
�œ˜KšœD�œ
˜IKš�œ˜"Kš
œ™˜
Kš
œ‡
™‡
—šœ�œ
˜Kš
œD™D—š
œ(˜(Kš
œ¤
™¤
—K˜šœÏc5˜7K˜K˜š�œ:�œ˜BKš
œ=™=Kšœ�œ%˜:K˜.K˜Kš�œ˜K˜—Kš
œE™EKš
œ˜
™˜
Kš
œ�™�K˜š
�˜šœ $˜&šœ +˜-Kš
œG™GKš
œ5™5Kš
œ?™?Kšœ�œ
˜š�œ(�˜-š�œ�œ
�˜Kšœ
�œ˜$š
œ˜š�œ�œ
�˜š
œ˜Kš�œ�œ˜7Kš
�œ
�œ
�œ�œ
�œ
˜<K˜—š
œ˜š
�œ�œ
�œ
�œ
�œ
˜/Kš
œG™G—š�œ˜Kš
œ)™)—K˜—Kšœ�œ
˜Kš�œ
˜——Kš�œ
˜—Kš�œ
˜—š
�˜˜Kš�œ�œ
�œ
�œ˜@š�œ3�˜9Kš�œ˜—Kš�œ˜K˜—˜š�œ�œ
�˜$Kšœ2�˜6Kš�œ˜—Kš
œ™š�œ�œ
�œ˜K˜Kšœ7�œ˜>K˜K˜—Kš�œ�œ
�œ
�œ˜BK˜!Kš�œ˜K˜——Kšœ +˜-—š
�˜˜Kš
œ2™2Kš�œ
�œ�œ
�œ
�œ
�œ˜5š�œ�œ
�œ˜Kš
œ™K˜/K˜!K˜K˜&K˜—Kš�œ˜š�œ�œ˜K˜K˜š�œ�˜Kšœ	�œ
�œ
�œ˜)Kšœ�œ
�œ
�œ˜.Kš�œ�œ
˜—K˜—K˜K˜—˜Kš
œ?™?K˜2K˜——Kšœ $˜&—Kš�œ
˜—š
�˜Kš
ϥ
™•
˜Kš
œ<˜<šœ�œ˜3˜+K˜\——K˜K˜K˜K˜Kš�œ˜K˜—˜K˜'K˜BKš�œ˜K˜——Kšœ 5˜7—Kšœ ˜——˜
šžœ�œ
�œ
�œ/˜IKšœ�œ˜5Kš
œ™K˜
Kš�œ�œ
�œ
�œ
�œ
�œ˜Cš�œ(�˜-š�œ�œ
�˜Kšœ�œ
�œ
�œ˜0š
œ˜š�œ�œ
�˜š
œ˜š�œ�œ˜š�œ�˜!Kš�œ
�œ
�œ˜+—š�œ!�œ˜)K˜K˜K˜ Kš�œ˜K˜
—Kš�œ
�œ˜K˜——Kšœ�œ
�œ
�œ˜9Kšœ�œ
˜Kš�œ
˜——Kš�œ
˜—Kš�œ
˜—K˜K˜—šžœ�œ
�œ
�œW˜zKš
œ™Kš
œF˜FKš
œ˜š�œ,�˜1K˜š�œ�œ
�˜š
œ˜š�œ�˜$K˜;š�œ(�œ.�œ˜aK˜K˜K˜—K˜——Kšœ�œ
˜Kšœ�œ
˜Kš�œ
˜—Kš�œ
˜—K˜K˜—šžœ�œ
�œ˜&Kšœ&�œ�œ˜6Kš
œ–
™–
Kš
œ'™'K˜Kšœ�œ�œ
˜š�œ*�œ�˜Kš�œ�œ
�˜š
œ˜š�œ
�œ�œ˜Kš�œ˜Kšœ
�œ
˜K˜——Kš�œ
˜—Kš�œ
˜—š�œ�œ�œ˜<Kšœ�œ
˜Kšœ�œ	˜K˜K˜
—š�œ˜K˜"K˜—Kšœ�œ
˜K˜K˜K˜—šž
œ�œ
�œ
�œ�œ�œ˜PKš
œ™K˜˜K˜#Kšœ�œ&˜5—Kšœ�œ%˜:K˜.K˜AK˜——˜
Kš
œ'™'K˜Kš
œ¹™¹K˜šžœ�œ
�œ˜*Kš
œ"˜"Kš
œ5™5Kš
œ.™.K˜Kš�œ�œ�œ
�œ
˜<K˜K˜K˜K˜—šžœ�œ
�œ˜'K˜.Kš
œt™tKš
œ™K˜K˜—šžœ�œ
�œ˜&K˜.Kš
ϧ
™ß
Kš
œ™K˜——˜
Kš
œ+™+K˜šžœ�œ
�œ!˜=Kš�œ"˜)Kš
œ™šœ
�œ/˜?Kšœ�œ/˜K—K˜"Kš�œ˜K˜K˜—šžœ�œ
�œ%˜>Kš
œ™Kš
œP™PKš
œ”
™”
Kš
œ>˜>Kš
œ˜K˜š
�˜K˜.Kš�œ�œ
�œ
�œ
˜Kšœ)�œ˜/Kš�œ
˜—K˜K˜—šžœ�œ
�œ
˜5Kš�œ(˜/Kš
œ>™>š�œ$�˜)Kš
�œ
�œ�œ
�œ�œ˜?Kš�œ�œ
�œ
˜%Kš�œ
˜—Kš
œ,™,š�œ+�˜0š�œ�œ
�˜Kšœ�œ˜'Kš�œ
˜—Kš�œ
˜—K˜K˜—Kš
œŽ
™Ž
K˜šœ	�œ
�œ
˜'K˜4K˜DK˜MK˜—šœ�œ
�œ
�œ˜(Kš	œ�œ�œ
�œ	�œ
˜5Kšœ�œ�œ
˜/Kšœ�œ�œ�œ˜;—K™š
œ�
™�
K˜—šœ�œ
�œ
˜)K˜2K˜.K˜KK˜—šžœ�œ
�œ
�œ%˜DKš
œ™Kš
œF˜FKš
œ˜š�œ+�˜0K˜Kšœ�œ
˜Kšœ
�œ
˜š�œ�œ
�˜Kš
œ0˜0Kšœ�œ
˜Kšœ�œ
˜Kš�œ
˜—Kš�œ
˜—K˜K˜—šžœ�œ
�œ˜ Kš
œ7˜7Kš
œ™Kš
œF˜FKš
œ˜Kš�œ&�œ�œ
�œ
˜OK˜Kšœ�œ
˜Kšœ�œ
˜K˜,K˜K˜—šž
œ�œ
�œ
�œ(˜HKš
œ™Kš
œE˜Eš�œ1�˜6K˜
Kš
�œ
�œ(�œ�œ�œ˜tKš�œ�œ
�œ
˜Kš�œ
˜—K˜——˜
Kš
œ™K˜š
œ#˜#Kš
œG™GKš
œ"™"Kš
œE™EK˜—šžœ�œ
�œ˜,šœ�œ+˜CKšœ�œ
�œB˜\—K˜K˜—šžœ�œ
�œ˜'K˜?Kš�œ˜ šœ�œ˜$šœ
�œ˜!˜bK˜———K˜"Kš
œ@˜@K˜K˜—šžœ�œ
�œ˜@Kš
œ˜Kš�œ%�œ�œ
�œ
˜JK˜Kšœ�œ
˜Kšœ�œ
˜K˜K˜—šžœ�œ
�œ
�œ%˜LKš
œ#™#š�œ8�œ�œ
�˜Kš�œ�˜š�œ�œ
�˜š
œ˜Kšœ�œ
˜K˜Kš�œ˜K˜—Kš�œ�œ
˜——Kš�œ
˜—K˜K˜—šžœ�œ
�œ
�œ˜AKš
œ%™%Kšœ�œ
˜K˜Kš�œ˜K˜K˜—šžœ�œ
�œ˜)Kšœ�œ�œ�œ˜9š�œ8�œ�œ
�˜KKš�œ�œ
�œ
�œ
˜$Kš�œ
˜—K˜——˜
šžœ�œ
�œ
�œ˜K˜1K˜+K˜?K˜Dš�œ�œ
�˜K˜?—š�œ�œ
�˜K˜ —š�œ�œ
�˜$K˜1—š�œ�œ
�˜%K˜2—K˜——K˜
Kš
œ6™6˜Kšœ�œ
˜Kšœ�œ
˜K˜Kšœ�œ�œ
�œ'˜OKšœ�œ˜!K˜šžœ�œ�œ
˜/Kš�œ�œ˜&š�œ�œ�˜,Kš�œ&�œ
�œ˜DKš�œ
˜—Kš�œ�œ˜*K˜K˜—šž
œ�œ
�œ˜2Kš�œ� œ�œ˜-Kšœ�œ�œ�œ˜1š�œ	�œ
˜šœ�œ
˜Kš�œ�œ˜H—šœ�œ
˜Kš�œ�œ˜H—Kš�œ˜—K˜K˜—šžœ�œ
�œ'˜EKš�œ	�œ�œ˜ Kš
œm™mKš
œš
™š
Kšœ�œ�œ�œ˜1š�œ˜Kš�œ�œ�˜MKš�œ�œ�˜MKš�œ�œ�˜MKš�œ�œ�˜MKš�œ�œ�˜MKš�œ�œ˜J—K˜K˜—šžœ�œ
�œ&�œ˜IK˜K˜K˜——Kš
œ*™*K˜šžœ�œ
�œ˜7Kš�œ�œ˜Kšœ�œ˜$Kš�œA˜Dš�œ�œ
�˜š�œ+˜-Kš�œ
�œ˜—Kš�œ˜—K˜$K˜Kš�œ˜K˜K˜—Kš
œ4™4K˜Kš
œ™K˜Kš
œ*™*K˜Kš
œÎ
™Î
š
œ™Kš
œ™Kš
œ[™[—Kš
œ™Kš
ϼ
™º
Kš
œG™GKš
œl™lK˜K˜Kš
œ™K˜Kš
œZ™ZKš
œ@™@K˜Kš
œ3™3Kš
œ™K˜Kš
œF™FKš
œ&™&K˜Kš
œ3™3Kš
œ2™2K˜Kš
œE™EKš
œ™Kš
œ
™
Kš
œ¡™¡K˜Kš
œM™MKš
œ™Kš
œ
™
K˜K˜Kš
œ%™%K˜Kš
œ˜
™˜
K˜Kšœ�œ
�œ
˜Kšœ�œ�œ
�œ	�œ
�œ
˜=K˜Kšœ�œ ;˜SKšœ�œ  ˜DK˜Kš
œ™K˜Kšœ�œ�œ ˜IKšœ�œ�œ ˜2K˜K˜šžœ�œ
�	œ�œ˜[š�œ C˜JK˜3Kš�œ�œ
�œ˜=K˜Kšœ�œ˜)š�œ�œ
�œ˜#Kš�œ�œ�œ
˜#—Kš�œ
˜K˜K˜——šžœ�œ
�	œ�˜;Kš�œ ˜&Kšœ�œ˜$Kš�œA˜Dš�œ�˜Kš
�˜š�œ+˜-Kš�œ
�œ˜—Kš�œ˜—K˜$K˜Kš�œ
˜K˜K˜—š	žœ�œ
�	œ�œ�˜NKš�œ )˜0K˜$Kš�œF˜Iš�œ�˜Kš�œ
�œ/�œ
�œ
˜@Kš�œ˜—Kš�œ
�œ˜Kš�œ
˜K˜K˜—šžœ�œ
�	œ�˜;Kš�œ 5˜<Kšœ�œ˜$Kšœ�œ
˜!Kš�œA˜Dš�œ�˜Kš
�˜Kš�œ,�œ
�œ
˜8K˜Kš�œ
�œ�œ˜7Kš�œ
˜—š�œ�˜Kš�œ#˜'Kš�œ'˜+—Kšœ�œ
˜Kš�œ
˜K˜K˜—Kš
œ¡™¡K˜šž
œ�œ
�	œ�˜E˜Kš�œ ˜Kšœ�œ
˜š�œ�˜Kš�œ
˜š�œ
�œ$˜.Kš�œ/˜2š�œ�˜Kš
�˜Kš�œ-�œ
�œ˜?š
�˜šœ	�˜Kš�œ�œ
�œ
�œ˜6K˜Kš�œ
˜——Kš�œ
˜—Kš�œ
˜——š�œ˜Kš
�˜Kš�œ�œ
�œ
�œ˜8K˜Kš�œ
˜—Kš�œ
�œ˜Kš�œ
˜K˜K˜——šžœ�œ
�	œ�	œ˜Mš�œ�œ˜Kš�œ ˜š�œ�œ
�œ˜#Kš
�˜Kš�œ;˜>š�œ�˜Kš�œ
�œ�œ
�œ
˜#Kš�œ
˜—Kš�œ
˜—Kš�œ
˜K˜——Kš
œ#™#˜Kš�œ
 ˜K˜—Kš�œ
�˜
K˜˜-Kš
œK™K—˜-Kš
ϒ
™í
—™2Kš
œ7™7—K™K™—…—Vü–¸