DIRECTORY Basics USING [ Comparison], BasicTime USING [ GMT, Period, earliestGMT, latestGMT], DB USING [ AttributeValue, AttributeValueList, Relship, RelshipSet, Entity, DeclareEntity, RelationSubset, NextRelship, ReleaseRelshipSet, T2V, V2T, GetF, MarkTransaction, TransactionOf, SetF, DeclareRelship, I2V, V2E, NameOf, DestroyRelship, Aborted], Hickory USING [ Event, RepetitionType, Error, EventTuple, EventList, SameEventTuple, OrderEventList], HickoryCache, HickoryStorage USING [ protData], HickorySupport USING [ StartTransaction, RestartTransaction, ComputeOccurrence, R2I], Random USING [ Choose], Rope USING [ ROPE, Equal, Compare] ; HickoryCacheImpl: CEDAR MONITOR LOCKS HickoryStorage.protData IMPORTS BasicTime, HickorySupport, DB, HickoryStorage, Random, Rope, Hickory EXPORTS HickoryCache SHARES HickorySupport = BEGIN OPEN HickoryStorage.protData, DB; CacheSize: CARDINAL = 128; MaxCost: PUBLIC CARDINAL _ 10; CacheIndex: TYPE = [ 0..CacheSize]; CacheRec: TYPE = RECORD [ Key: Hickory.Event, TimeTable: ARRAY [1..CacheSize] OF BasicTime.GMT, -- increasingly ordered Top: CacheIndex _ 0 ]; Cache: TYPE = REF CacheRec; CacheList: TYPE = LIST OF Cache; caches: CacheList _ NIL; LoadCache: INTERNAL PROCEDURE [ cache: Cache] = BEGIN OPEN cacheRel; av: AttributeValue; avl: AttributeValueList _ NIL; relSet: RelshipSet; tuple: Relship; keyEnt: Entity; oldTime, newTime: BasicTime.GMT; keyEnt _ DeclareEntity[ d: eventDomain, name: cache.Key, version: OldOnly]; av _ [ attribute: Event, lo: keyEnt, hi: keyEnt]; avl _ CONS[ av, avl]; av _ [ attribute: Time, lo: T2V[ LOOPHOLE[ BasicTime.earliestGMT]], hi: T2V[ LOOPHOLE[ BasicTime.latestGMT]]]; -- for ordering avl _ CONS[ av, avl]; relSet _ RelationSubset[ Rel, avl]; cache.Top _ 0; -- purge cache! oldTime _ BasicTime.earliestGMT; WHILE ( tuple _ NextRelship[ relSet]) # NIL DO newTime _ LOOPHOLE[ V2T[ GetF[ tuple, Time]]]; IF BasicTime.Period[ newTime, oldTime] <= 0 THEN ERROR; InsertToCache[ cache, newTime, cache.Top]; oldTime _ newTime; ENDLOOP; ReleaseRelshipSet[ relSet]; END; -- LoadCache StoreCache: INTERNAL PROCEDURE [ cache: Cache] = BEGIN OPEN cacheRel; av: AttributeValue; relSet: RelshipSet; tuple: Relship; count: CARDINAL _ 1; keyEnt: Entity; HickorySupport.StartTransaction[]; keyEnt _ DeclareEntity[ d: eventDomain, name: cache.Key, version: OldOnly]; av _ [ attribute: Event, lo: keyEnt, hi: keyEnt]; relSet _ RelationSubset[ Rel, LIST[ av]]; WHILE ( tuple _ NextRelship[ relSet]) # NIL AND count <= cache.Top DO SetF[ tuple, Event, keyEnt]; SetF[ tuple, Time, T2V[ LOOPHOLE[ cache.TimeTable[ count]]]]; count _ count + 1; ENDLOOP; ReleaseRelshipSet[ relSet]; WHILE count <= cache.Top DO tuple _ DeclareRelship[ Rel, NIL, NewOnly]; SetF[ tuple, Event, keyEnt]; SetF[ tuple, Time, T2V[ LOOPHOLE[ cache.TimeTable[ count]]]]; count _ count + 1; ENDLOOP; MarkTransaction[ TransactionOf[ $Hickory]]; END; -- StoreCache LoadCaches: PUBLIC INTERNAL PROCEDURE = BEGIN OPEN eventRel, HickorySupport; ENABLE BEGIN UNWIND => NULL; END; -- Enable av: AttributeValue; relSet: RelshipSet; tuple: Relship; success: BOOLEAN _ FALSE; WHILE NOT success DO ENABLE Aborted => { HickorySupport.RestartTransaction; success _ FALSE; LOOP}; HickorySupport.StartTransaction[]; av _ [ attribute: RepeatType, lo: I2V[ R2I[ Hourly]], hi: I2V[ R2I[ Yearly]]]; relSet _ RelationSubset[ Rel, LIST[ av]]; -- everything that is repeated WHILE ( tuple _ NextRelship[ relSet]) # NIL DO ev: Hickory.Event _ NameOf[ V2E[GetF[ tuple, Key]]]; cache: Cache _ FindCache[ ev]; LoadCache[ cache]; ENDLOOP; ReleaseRelshipSet[ relSet]; MarkTransaction[ TransactionOf[ $Hickory]]; success _ TRUE; ENDLOOP; -- Transaction END; -- LoadCaches StoreCaches: PUBLIC INTERNAL PROCEDURE = BEGIN success: BOOLEAN _ FALSE; WHILE NOT success DO ENABLE Aborted => { HickorySupport.RestartTransaction; success _ FALSE; LOOP}; HickorySupport.StartTransaction[]; FOR l: CacheList _ caches, l.rest UNTIL l = NIL DO StoreCache[ l.first]; ENDLOOP; MarkTransaction[ TransactionOf[ $Hickory]]; success _ TRUE; ENDLOOP; -- Transaction END; -- StoreCaches FindCache: INTERNAL PROCEDURE [ ev: Hickory.Event] RETURNS [ cache: Cache] = BEGIN IF caches = NIL THEN BEGIN cache _ NEW[ CacheRec]; cache.Key _ ev; caches _ LIST[ cache]; RETURN[ cache]; END ELSE BEGIN -- at least on el in list cur: CacheList _ caches; prev: CacheList _ NIL; new: CacheList; WHILE cur # NIL AND Rope.Compare[ cur.first.Key, ev] = greater DO prev _ cur; cur _ cur.rest; ENDLOOP; IF cur # NIL AND Rope.Equal[ cur.first.Key, ev] THEN RETURN[ cur.first]; IF cur = NIL THEN BEGIN -- at end, not found prev.rest _ LIST[ NEW[ CacheRec]]; cur _ prev.rest; END ELSE IF prev = NIL THEN BEGIN-- insert at head new _ LIST[ NEW[ CacheRec]]; new.rest _ caches; caches _ new; cur _ new; END ELSE BEGIN -- insert in middle new _ LIST[ NEW[ CacheRec]]; new.rest _ cur; prev.rest _ new; cur _ new; END; cur.first.Key _ ev; RETURN[ cur.first]; END; END; -- FindCache FindNextOccurrence: PUBLIC INTERNAL PROCEDURE [ ev: Hickory.Event, firstTime, lastOccurred, after: BasicTime.GMT, repType: Hickory.RepetitionType, repTime: Rope.ROPE] RETURNS [ nextTime: BasicTime.GMT] = BEGIN index: CacheIndex; cost: CARDINAL; cache: Cache; IF BasicTime.Period[ after, firstTime] >= 0 THEN RETURN[ firstTime]; IF after = lastOccurred THEN RETURN[ lastOccurred]; cache _ FindCache[ ev]; IF cache.Top = 0 THEN BEGIN -- empty cache, load it with firstTime and lastOccurred InsertToCache[ cache, firstTime, cache.Top]; IF firstTime # lastOccurred THEN InsertToCache[ cache, lastOccurred, cache.Top]; END; index _ FindCacheEntry[ cache, after]; -- TimeTable[ index] <= after or index = 0 IF index = 0 THEN -- no suitable time in cache, firstTime ( ie. the minimal value IF BasicTime.Period[ lastOccurred, after] > 0 THEN [ nextTime, cost] _ HickorySupport.ComputeOccurrence[ lastOccurred, repType, repTime, after, TRUE] ELSE [ nextTime, cost] _ HickorySupport.ComputeOccurrence[ firstTime, repType, repTime, after, TRUE] ELSE IF cache.TimeTable[ index] = after THEN RETURN[ after] -- full hit ELSE [ nextTime, cost] _ HickorySupport.ComputeOccurrence[ cache.TimeTable[ index], repType, repTime, after, TRUE]; IF cost > MaxCost THEN InsertToCache[ cache, nextTime, index]; RETURN[ nextTime]; END; -- FindNextOccurrence FindCacheEntry: INTERNAL PROCEDURE [ cache: Cache, after: BasicTime.GMT] RETURNS [ index: CacheIndex] = BEGIN OPEN cache^; lo, hi, mid: CacheIndex; IF Top = 0 THEN RETURN [ 0]; IF BasicTime.Period[ after, TimeTable[ 1]] > 0 THEN RETURN[ 0]; IF BasicTime.Period[ TimeTable[ Top], after] > 0 THEN RETURN[ Top]; lo _ 1; hi _ Top; mid _ hi; WHILE lo # mid DO IF TimeTable[ lo] = after THEN RETURN[ lo]; IF TimeTable[ hi] = after THEN RETURN[ hi]; mid _ ( hi + lo)/2; IF BasicTime.Period[ after, TimeTable[ mid]] > 0 THEN hi _ mid ELSE lo _ mid; ENDLOOP; RETURN[ lo]; END; -- FindCacheEntry InsertToCache: INTERNAL PROCEDURE [ cache: Cache, time: BasicTime.GMT, index: CacheIndex] = BEGIN OPEN cache; ShiftByOneUp: INTERNAL PROCEDURE[ from, to: CacheIndex] = BEGIN i: CacheIndex _ to; WHILE i > from DO cache.TimeTable[ i] _ cache.TimeTable[ i-1]; i _ i - 1; ENDLOOP; END; -- ShiftByOneUp ShiftByOneDown: INTERNAL PROCEDURE [ from, to: CacheIndex] = BEGIN i: CacheIndex _ from; WHILE i < to DO cache.TimeTable[ i] _ cache.TimeTable[ i+1]; i _ i + 1; ENDLOOP; END; -- ShiftByOneDown IF index < Top AND TimeTable[ index+1] = time THEN RETURN; IF Top < CacheSize THEN IF index = Top THEN BEGIN -- insert after Top Top _ Top + 1; TimeTable[ Top] _ time; END ELSE BEGIN Top _ Top + 1; ShiftByOneUp[ index+1, Top]; TimeTable[ index+1] _ time; END ELSE IF index = 0 THEN BEGIN -- insert as first ( i.e. smallest) element TimeTable[ 1] _ time; END ELSE IF index = Top THEN BEGIN -- insert as last ( i.e. biggest) element TimeTable[ Top] _ time; END ELSE BEGIN -- delete an entry at random since insertion in middle... victim: CacheIndex _ Random.Choose[ 1, CacheSize]; IF victim = index + 1 THEN TimeTable[ index+1] _ time ELSE IF victim = index THEN TimeTable[ index] _ time ELSE IF victim < index THEN BEGIN ShiftByOneDown[ victim, index]; TimeTable[ index] _ time; END ELSE BEGIN ShiftByOneUp[ index+1, victim]; TimeTable[ index+1] _ time; END; END; END; -- InsertToCache InvalidateCaches: PUBLIC INTERNAL PROCEDURE = BEGIN caches _ NIL; END; InvalidateOneCache: PUBLIC INTERNAL PROCEDURE [ ev: Hickory.Event, erase: BOOLEAN _ FALSE] = BEGIN cur, prev: CacheList; IF caches = NIL THEN RETURN; cur _ caches; prev _ NIL; WHILE cur # NIL AND Rope.Compare[ cur.first.Key, ev] = greater DO prev _ cur; cur _ cur.rest; ENDLOOP; IF cur = NIL THEN RETURN; IF Rope.Equal[ cur.first.Key, ev] THEN BEGIN -- found it IF prev = NIL THEN caches _ caches.rest ELSE prev.rest _ cur.rest; IF erase THEN CleanCacheRel[ ev]; END; END; -- InvalidateOneCache CleanCacheRel: INTERNAL PROCEDURE [ ev: Hickory.Event] = BEGIN OPEN repeatRel; tuple: Relship; evEnt: Entity; relSet: RelshipSet; av: AttributeValue; evEnt _ DeclareEntity[ eventDomain, ev, OldOnly]; IF evEnt = NIL THEN ERROR Hickory.Error[ NoSuchEvent, ev]; av _ [ attribute: Event, hi: evEnt, lo: evEnt]; relSet _ RelationSubset[ Rel, LIST[ av]]; WHILE ( tuple _ NextRelship[ relSet]) # NIL DO DestroyRelship[ tuple]; ENDLOOP; ReleaseRelshipSet[ relSet]; END; -- CleanCacheRel MaintainCache: PUBLIC INTERNAL PROCEDURE [ ev: Hickory.Event, lastOccurred: BasicTime.GMT] = BEGIN index: CARDINAL; cache: Cache _ FindCache[ ev]; index_ FindCacheEntry[ cache, lastOccurred]; IF index > 0 AND cache.TimeTable[ index] = lastOccurred THEN RETURN; InsertToCache[ cache, lastOccurred, index]; END; -- MaintainCache -- the cache of entered events ( internal to monitor) enteredEvents: Hickory.EventList _ NIL; IsInEnteredEvents: PUBLIC INTERNAL PROCEDURE [ ev: Hickory.EventTuple] RETURNS [ duplicate: BOOLEAN, key: Hickory.Event] = BEGIN FOR l: Hickory.EventList _ enteredEvents, l.rest UNTIL l = NIL OR BasicTime.Period[ l.first.EventTime, ev.EventTime] < 0 DO IF l.first.EventTime = ev.EventTime THEN IF Hickory.SameEventTuple[ ev, l.first] THEN RETURN[ TRUE, l.first.Key]; ENDLOOP; RETURN[ FALSE, NIL]; END; -- IsInEnteredEvents DeleteFromEnteredEvents: PUBLIC INTERNAL PROCEDURE [ key: Hickory.Event] = BEGIN prev, cur: Hickory.EventList; prev _ NIL; cur _ enteredEvents; WHILE cur # NIL AND NOT Rope.Equal[ key, cur.first.Key] DO prev _ cur; cur _ cur.rest; ENDLOOP; IF cur = NIL THEN RETURN; -- not found IF prev = NIL THEN BEGIN enteredEvents _ cur.rest; cur.rest _ NIL; END ELSE BEGIN prev.rest _ cur.rest; cur.rest _ NIL; END; END; -- IsInEnteredEvents InsertEvent: PUBLIC INTERNAL PROC [ evt: Hickory.EventTuple] = BEGIN enteredEvents _ Hickory.OrderEventList[ CONS[ evt, enteredEvents]]; END; -- InsertEvent FindCachedEvent: PUBLIC INTERNAL PROC [ ev: Hickory.Event] RETURNS [ evl: Hickory.EventList] = BEGIN cur: Hickory.EventList _ enteredEvents; WHILE cur # NIL AND NOT Rope.Equal[ ev, cur.first.Key] DO cur _ cur.rest; ENDLOOP; IF cur = NIL THEN RETURN[ NIL]; -- not found evl _ CONS[ cur.first, NIL]; RETURN[ evl]; END; -- FindCachedEvent ForgetCachedEvent: PUBLIC INTERNAL PROC [ ev: Hickory.Event, on: BOOLEAN] = BEGIN cur: Hickory.EventList _ enteredEvents; WHILE cur # NIL AND NOT Rope.Equal[ ev, cur.first.Key] DO cur _ cur.rest; ENDLOOP; IF cur = NIL THEN RETURN; -- not found cur.first.Forgotten _ on; END; -- ForgetCachedEvent InvalidateEventCache: PUBLIC INTERNAL PROC = BEGIN enteredEvents _ NIL; END; -- InvalidateEventCache END. Î/ivy/binding/hickory/hickoryCacheImpl.mesa Implements the cache of repetition times for repeated events. Last edited by: Binding, July 31, 1984 3:11:26 pm PDT Data types and structures Global variables Support stuff Loading and storing the caches to load the cache for one event assume relSet ordered because of TimeIndex Notice if this does not hold, we are in big trouble...: basically the cache contents is unordered and chaos will result.. to store the cache for an event. load all the caches for all the repeated events. to store all caches to find the cache for the given event, creating one if needed. Finding the next occurrence of a repeated event here we go and try to find the next occurrence of a repeated event that will happen after 'after'. to ever be present in cache) in cache can be destroyed by deletion.. return index s.t. TimeTable[ index] <= after, binary search. Returns 0 if the smallest value contained in TimeTable is > then after! we insert the 'time' after the 'index'ed element. In case the cache is full, we simply pick a random victim that is deleted. shift element in [ from ..to) one up, overwriting element [to] and freeing elem. [ from] shift elements in ( from..to] one down, overwriting [ from] and freeing [to]. check if we regenerated an existing time table entry Invalidating caches to destroy just one cache... If erase, also clean out the data base... to delete all tuples for this event from cacheRel Maintaining the cache once a "lastOccurrence" has been recomputed to insert the newly computed last occurrence into the cache TimeTable[ index] <= lastOccurred or index = 0 to find out FAST if event already registered with hickory. to delete the entry in list if it's in there initially Ê ˜Jšœ*™*Jšœ=™=Jšœ5™5J˜šÏk ˜ Jšœœ˜Jšœ œœ"˜7Jšœœô˜üJšœœY˜fJ˜ Jšœœ ˜!JšœœA˜UJšœœ ˜Jšœœœ˜"J˜—J˜šœœ˜Jšœ˜Jšœœ'˜LJšœ ˜Jšœ˜J˜—šœœœœ˜)J˜—šœ™J˜Jšœ œ˜Jšœ œ˜J˜Jšœ œ˜#J˜šœ œœ˜J˜Jšœ œœ œÏc˜KJ˜J˜J˜—Jšœœœ ˜Jšœ œœœ˜ J˜—šœ™J˜Jšœœ˜J˜—šœ ™ J˜—šœ™J˜šÏn œœ œœ˜6Jšœ™Jšœ ˜J˜J˜Jšœœ˜J˜J˜J˜J˜ J˜J˜KJ˜1Jšœœ ˜Jšœ!œ$œž˜~Jšœœ ˜Jšœ#˜#Jšœ¤™¤Jšœž˜J˜ šœ#œœ˜/Jšœ œ˜.Jšœ*œœ˜7Jšœ*˜*J˜Jšœ˜—J˜Jšœž ˜J˜—šŸ œœ œ˜6Jšœ ™ Jšœ ˜J˜J˜J˜Jšœœ˜J˜J˜J˜"J˜KJ˜1Jšœœ˜)šœ#œœ˜EJ˜Jšœœ˜=J˜Jšœ˜—J˜šœ˜Jšœœ ˜+J˜Jšœœ˜=J˜Jšœ˜—J˜+Jšœž ˜J˜—š Ÿ œœœ œ˜-Jšœ0™0Jšœ˜šœ˜ Jšœœ˜Jšœž ˜—J˜J˜J˜Jšœ œœ˜J˜šœœ ˜Jšœ;œœ˜NJ˜J˜"J˜NJšœœž˜Hšœ#œ˜.J˜4J˜J˜Jšœ˜—J˜J˜+Jšœ œ˜Jšœž˜—Jšœž ˜J˜—š Ÿ œœœ œ˜.Jšœ™Jšœ œœ˜J˜šœœ ˜Jšœ;œœ˜NJ˜J˜"šœœœœ˜3J˜Jšœ˜—J˜+J˜Jšœž˜—Jšœž˜J˜—š Ÿ œœ œœ˜RJšœ>™>šœ œœ˜Jšœœ ˜J˜Jšœ œ ˜Jšœ ˜Jš˜—šœœž˜$J˜Jšœœ˜J˜šœœœ-˜BJ˜ J˜Jšœ˜—Jš œœœ œœ ˜Hš œœœœž˜-Jšœ œœ ˜"J˜Jš˜—š œœœœž˜.Jšœœœ ˜J˜J˜ J˜ Jš˜—šœœž˜Jšœœœ ˜J˜J˜J˜ Jšœ˜—J˜Jšœ ˜Jšœ˜—Jšœž ˜—J˜—šœ/™/J˜šŸœœœ œ@œ1œœœ˜ÑJšœS™SJšœ™J˜Jšœœ˜J˜J˜Jšœ*œœ ˜DJšœœœ˜3J˜šœœœž7˜SJ˜,Jšœœ0˜PJšœ˜—Jšœ'ž*˜Qšœ œž@˜RJšœD™Dšœ,œ˜3Jšœ^œ˜c—š˜JšœZœ˜_——Jš œœ!œœž ˜GJšœiœ˜sJšœœ(˜>Jšœ ˜Jšœž˜J˜—š Ÿœœ œ"œœ˜mJšœ\™\J™'Jšœ˜ J˜J˜Jšœ œœ˜Jšœ-œœ˜?Jšœ/œœ˜CJ˜šœ ˜Jšœœœ˜+Jšœœœ˜+J˜Jšœ/œ ˜>Jšœ ˜Jšœ˜—Jšœ˜ šœž˜J˜——š Ÿ œœ œ!œ˜aJšœW™WJ™%Jšœ˜ J˜šŸ œœ œ˜?JšœJ™JJšœ ™ J˜šœ ˜J˜,J˜ Jšœ˜—Jšœž˜J˜—šŸœœ œ˜BJšœN™NJ˜šœ˜J˜,J˜ Jšœ˜—Jšœž˜—J˜Jšœ5™5Jšœ œœœ˜:šœ˜šœ œœž˜-J˜J˜Jš˜—šœ˜ J˜J˜J˜Jš˜——š œœ œœž+˜HJ˜Jš˜—š œœ œœž)˜HJ˜Jš˜—šœœž9˜DJ˜2Jšœœ˜5Jšœœœ˜4šœœœ˜!J˜J˜Jš˜—šœ˜ J˜J˜Jšœ˜—Jšœ˜—Jšœž˜J˜J˜——šœ™J˜š Ÿœœœ œ˜3Jšœ œ˜ Jšœ˜J˜—š Ÿœœœ œœœ˜bJšœF™FJ˜Jšœ œœœ˜J˜ Jšœœ˜ šœœœ,˜AJ˜ J˜Jšœ˜—Jšœœœœ˜šœ œž ˜8Jšœœœ˜'Jšœ˜Jšœœ˜!Jšœ˜—Jšœž˜J˜—šŸ œœ œ˜>Jšœ1™1Jšœ ˜Jšœ˜J˜J˜J˜J˜Jšœ2˜2Jšœ œœœ!˜:J˜/Jšœœ˜)šœ#œ˜.J˜Jšœ˜—J˜Jšœž˜J˜——šœA™AJ˜š Ÿ œœœ œ.œ˜bJšœ;™;Jšœœ˜J˜J˜J˜,Jšœ/™/Jšœ œ(œœ˜DJ˜+Jšœž˜—J˜—˜5J˜J˜'J˜š Ÿœœ œœœ˜Jšœ:™:š œ.œœœ8˜{šœ"œ˜)Jšœ&œœœ˜H—Jšœ˜—Jšœœœ˜Jšœž˜J˜—šŸœœ œ˜PJšœ,™,J˜J˜Jšœœ˜ š œœœœ!˜:J˜Jšœ˜—Jš œœœœž ˜&šœœœ˜J˜Jšœ œ˜Jš˜—šœ˜ J˜Jšœ œ˜Jšœ˜—Jšœž˜J˜—š Ÿ œœœœ˜DJšœ(œ˜DJšœž˜J˜—š Ÿœœœœœ˜eJ˜'J˜š œœœœ ˜9J˜Jšœ˜—Jš œœœœœž ˜,Jšœœ œ˜Jšœ˜ Jšœž˜J˜J˜—š Ÿœœœœœ˜RJ˜'J˜š œœœœ ˜9J˜Jšœ˜—Jš œœœœž ˜&J˜Jšœž˜J˜—š Ÿœœœœ˜2Jšœ˜Jšœž˜J˜——Jšœ ™ ™Jšœ˜J˜——…—-Bô