Boost logo

Boost :

Subject: Re: [boost] [string] proposal
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2011-01-29 18:39:32


On Sun, Jan 30, 2011 at 7:22 AM, Patrick Horgan <phorgan1_at_[hidden]> wrote:
> On 01/29/2011 02:41 AM, Ivan Le Lann wrote:
>>
>> I don't think so. Isn't the easiest way towards proper composition to
>> consider
>> that the whole is the same as the part?
>> I see the "chain" (I voted for that one!) as an immutable tree of
>> immutable leafs.
>> I think this can be naïvely seen as the following recursive
>> boost::variant:
>
> But if everything is immutable, what if you add a phrase in the middle of a
> line.
>

You're doing string manipulation. What you should be doing is building a string.

> chain thesentence=chain("I like bananas.  Yes I do.")
>
> becomes:
>
> thesentence=thesentence.insert(atpos15, " all the time");
>

Nope.

chain thesentence = "I like bananas. Yes I do.";
thesentence =
  substr(thesentence, 0, 15)
  ^ " all the time"
  ^ substr(thesentence, length(thesentence) - 10, 10);

> To create a sentence, "I like bananas all the time.  Yes I do."
>
> Originally the tree would have one element demarcating the beginning and end
> of the original string.  After the addition, you could have a tree with
> three elements two pointing into the original string, "I like bananas" and
> ".  Yes I do."  and a middle one pointing at the beginning and end of " all
> the time".  To insert that something had to change.  A list or chain of 1
> element became a list or chain of 3 elements.  Whatever changed has to be
> thread safe.  Of course you say leafs are immutable, so the original leaf
> that pointed at the beginning and end of the original string would still
> exist, but now be unused, right?  Am I understanding this correctly?
>

I think you're still thinking of string manipulation when you should
have been thinking about string building. ;)

So since because the original chain is still referenced in the new
chain the data in the block from the original chain will still
reference that same block -- you just have concatenation nodes that
point to different segments of the same block that is re-used. Then
you can actually write the contents for the temporary chain built from
" all the time" into that same block (maybe after the original
sentence), and then you still just fit everything into as little
memory as you possibly require and get the immutability guarantee.
It's still thread-safe because you're not modifying anything that's
already built because you're building something new. ;)

At the end of the assignment though, the original structure for the
original string is actually freed -- that means the concatenation tree
that used to be a single node, will have a reference count that drops
to 0 and is actually returned to the allocator used to allocate the
node in the first place. Note that chain is designed to act like a
shared_ptr in this regard.

HTH

PS. I really should just drop this, but the question was really interesting.

-- 
Dean Michael Berris
about.me/deanberris

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk