88
TheseensurethateachaddresscorrespondstonomoreasingleelementfromVandthat
zero-ornegative-lengthaddressrangescontainonlythenullstring.Theydonotensure
thateveryrangeofaddresseshasanycontent,becauseanA-sequencecancontainaddresses
fordeleteddatathatdoesnotappearinthefinalsequence.Wewillomitthesubscriptiden-
tifyingtheparticularA-sequencewhenonlyonesequenceisunderdiscussion.
4.3.1 P-sequences
P-sequencesformalizehowchangesareassembledintoasetoforderedaddressesrelated
toparticularsequencesofvalues.ThePalimpsestaddressingschemeassignsaddressesina
waythatadmitsofotheruses,aswell.Thestructureoftheaddressspaceenablesthedeter-
minationofwhatdataiscommontotwoP-sequences.GiventwoP-sequencesitispossibleto
determine,byinspection,whatdatawasduplicatedbycopyoperationsormovedbymove
operations,andwhatoriginalinsertionoperationinitiallyaddedanyparticularvaluetothe
sequence.P-sequencesaredefinedforminimallyconsistentchangesets,butIshallnotewe
dependenciesonminimalconsistency,andtowhatextentthatrestrictioncanberelaxed.
TheP-sequenceP
S hasthreecomponents:
1. Atotalorderingrelation,<
SA ,onA’(S) .
2. ThesetofaddressesA’(S)determinedbyasetofchangesS.
3. AfunctionC
S (a
1 , a
2 )thatreturnsasubsequenceforaP-sequencerangeindicatedby
2addressesinA’(S) .
TheP-sequenceP
S isanA-sequencewithaddressesA’(S), contentsfunctionC
S ,andad-
dressordering<
SA .TheorderingofaP-sequenceiswhatdeterminesthefinallinearstructure
oftheaddressesinthesequence,andallowstheenumerationofitscontents.Itis<
SA that
orderstheaddressescreatedbyaminimallyconsistentchangeset.
4.3.2 TheP-sequenceaddressordering
Inthissectiontheaddressordering,<
sa isdefined.Thisdefinitionandthefollowingones
areabittricky,sincetheactualaddressesinaP-sequencearethechangesinA’(S) .Theef-
89
fectofthosechanges,andthusthecontentofA’(S) issignificantlymodifiedbytheordering
oftheaddresses,sincemove,copyanddeleteallspecifytheirregionsofeffectintermsof
theendpointsofrangesofaddresses.Becauseofthis,itisnecessarytobecarefultoavoid
circulardefinitions.Thisisachievedbydefininganorderingoverallsyntacticallylegalad-
dressesthatcanbecreatedfromachangeset.Theeffectsofthosechangesarethendefined
intermsoftheorderingofthelargerset.Theeffectsinquestion,inthiscase,arethesetof
legaladdressesinthesequence,andthecontentsoftherangesbetweenthelegaladdresses.
Onlywiththesedefinitionsinplacecanaconsistentdefinitionbegivenofwhichmembers
ofA(S)arenotincludedinA’(S) .
A(S),whereSisaminimallyconsistentchangeset,isthesetofalladdressessatisfying
Definition4.1andconstructedusingonlytheIDsofchangesinS.Wewilldefinetheorder-
ingrelation<
SA onthesetA(S),andwilllaterrestrictittothesetA’(S) ˝ A(S).Indefining
<
SA ,wewillneedtodefineanotherrelationshipbetweenaddresses.Therefersrelationallows
ustoorderchangeswithrespecttotheotherchangesreferredtobythedestinationofthe
initialchangeintheirchangepaths.
Definition4.6:Thedestinationrelation<
d isdefinedonaddressesasfollows:
1. Fora = (I
1 …I
n ,i),b = (I’
1 …I’
n ,j),a <
d biffI
1 e Ids(Dest(I’
1 ))
2. Ifa <
d b,andb <
d c,thena <
d c.
Lemma4.1:Fora = (I
1 …I
n ,i),b = (I’
1 …I’
n ,j),a <
d biffI
1 <
r I’
1 .
Proof:Toshowtheforwarddirection(a <
d bimpliesthatI
1 <
r I’
1 )weonlyneedtoobserve
thatI
1 e Ids(Dest(I’
1 ))impliesthatChange(I
1 ) e Refs(I’
1 ),andthusI
1 <
r I’
1 byDefinition4.3.
Intheotherdirection,assumethatI
1 <
r I’
1 anditisnottruethata <
d b.Thenmustbea
counterexample,anaddressx = (I’’
1 …I’’
n , k)suchthatI
1 £
r I’’
1 <
r I’
1 ,andforwhicha £
d xor
x <
d bisfalse.Thismeanseitherthatx aandI
1 ˇ Ids(Dest(x))orI’’
1 ˇ Ids(Dest(b)).But
Previous Page Next Page