From -8958066293780809641
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,b83a4267f4ac775
X-Google-Attributes: gidf78e5,public
From: AllanW@my-dejanews.com
Subject: Re: string/cow/algorithm
Date: 1998/08/10
Message-ID: <6qnj99$h2l$1@nnrp1.dejanews.com>
X-Deja-AN: 379814108
X-NNTP-Posting-Host: 199.125.171.8
Approved: stephen.clamage@sun.com (comp.std.c++)
References: <6qfr41$oue$1@pigpen.csrlink.net> <6qg3ld$r7o$1@shell7.ba.best.com> <6qgs0r$92e$1@pigpen.csrlink.net> <35ccc2b4.832003@news3.ibm.net> <6qn19u$sb0$1@pigpen.csrlink.net>
X-Snookums: I love you
X-UID: 0000000001
X-Status: $$$T
X-Http-User-Agent: Mozilla/4.04 [en] (Win95; I)
Organization: Deja News - The Leader in Internet Discussion
X-Article-Creation-Date: Mon Aug 10 19:56:25 1998 GMT
Newsgroups: comp.std.c++
Originator: clamage@taumet


In article <6qn19u$sb0$1@pigpen.csrlink.net>,
  jpotter@falcon.lhup.edu (John Potter) wrote:
>
> snowball3@usa.net (Mark E.) wrote:
>
> : The program segment under discussion and whether the output is conforming:
> : >#include <iostream>
> : >#include <string>
> : >#include <algorithm>
> : >using namespace std;
> : >int main () {
> : >   string s("Hello world");
> : >   string c(s);
> : >   sort(c.begin(), c.end()); // undefined behavior?
> : >   cout << s << endl;
> : >   }

> : I have written my own string class using cow and my class produces the same
> : answer. As far as I'm concerned, s shouldn't also be sorted so my class
> : would be considered "non-conforming".

And even if that were understood, the class would also be non-intuitive
and error-prone. When you copy a string, logically you have two strings
with the same value; when you modify one it shouldn't affect the other.
The reference count/copy-on-write mechanism is a local optimization that
the programmer shouldn't have to be involved with.

> : In my class, I set a flag in the
> : non-const versions of begin() and end() so when you write a character, a
> : cow is performed.

The problem is how to detect a write. The phrase "set a flag" implies
that you aren't triggering the deep copy right away -- but if you
return a char*, then you won't get another chance, because modifying
the char isn't a class operation. On the other hand, if non-const
begin() and end() do trigger a deep write right away, then casual
(read: not careful) users, who may use begin() and end() on a
non-const string that they don't intend to modify, will take a big
performance hit.

> : begin() and end() return pointers to the internal
> : character array, so if you write:
>
> : string s("abc");
> : string c(s);
>
> : *(c.begin()) = 'd'; // Where do I fix this?

Exactly. The assignment has to trigger a copy somehow, but begin()
doesn't seem like the right place.

> I received some email responses to the original.  Not seeing any
> posts, I will pass on the information to you and others.  Here is
> another nasty problem:
>
>  string s("abc");
>  string::iterator i(s.begin());
>  string c(s);
>  *i = 'z';
>  // What is the value of c[0]?

A more vexing version of the same. The iterator is created before the
logical copy, so simply having the new iterator set a flag couldn't
possibly solve the problem. We have to detect the write itself somehow.

> A solution is for strings to have one of three states (shared, unique,
> unsharable).  You have the first two now.  Any function which returns
> a non-const reference to internals must take care of making the copy
> and marking it unsharable.  Any copy function which gets an unsharable
> to copy must do a deep copy.  In the above, s.begin() would do that
> for s and the copy constructor would be forced to do a deep copy in
> creating c.

But once a string is marked unsharable, can we ever change it back to
unique? When does an interator and/or address go out of scope?

What we really should do is detect changes to the strings that are
shared, triggering a deep copy but somehow not invalidating any
iterators. (Changing the string length would continue to invalidate
iterators, but that's not part of this problem.)  I think that using
a proxy class should handle this fairly well; below is my (UNTESTED)
example, although I'm sure many of the usual contributors to this
group could do better.

    class string {
        // Class Data holds the actual array, and a ref count
        struct Data {
            char *data;
            int len;
            mutable int ref;

            Data(int i) : data(new char[1+i]), len(i), ref(1) {}
            Data(const char*c) : len(c?strlen(c):0), ref(1) {
                data = new char[1+len];
                if (c) strcpy(data, c);
            }
            Data(const Data&d) : data(new char[1+d.len]), len(d.len), ref(1)
                { memcpy(data, d.data, len+1); --d.ref; } // Deep copy
            void addRef() { ++ref; }
            void removeRef() { if (!--ref) delete this; }
            bool needCow() { return ref>1; }
        } *data;

        // Class Proxy reads or writes the string,
        // returned by Iterator::operator*
        struct Proxy {
            string *object;
            int     pos;
            Proxy(string*o, int p) : object(o), pos(p) {}
            operator char() const { return object->data->data[pos]; }
            char operator=(char c) {
                if (object->data->needCow())
                    object->data = new Data(object->data); // Deep copy
                return object->data->data[pos] = c;
            }
            char* operator&() {
                if (object->data->needCow())
                    object->data = new Data(object->data); // Deep copy
                return object->data->data + pos;
            }
            // ... more ...
        };

        // class Iterator is the iterator returned by
        // non-const begin() and end()
        struct Iterator {
            string *object;
            int     pos;
            Iterator(string*o, int p) : object(o), pos(p) {}
            Iterator operator ++() { ++pos; return *this; }
            Iterator operator ++(int)
                { Iterator i(object,pos); ++pos; return i; }
            Iterator operator --() { --pos; return *this; }
            Iterator operator --(int)
                { Iterator i(object,pos); --pos; return i; }
            Proxy operator*() const { return Proxy(object, pos); }
            Proxy operator[](int i) { return Proxy(object, pos+i); }
            // ... more ...
        };
        class ReverseIterator { /* Extremely similar */ };
        class ConstIterator { /* Similar to Iterator but simpler */ };
        class ConstReverseIterator { /* Extremely similar */ };

    public:
        string(const char*c) : data(new Data(c)) {}
        string(const string&d) : data(d.data) { data->addRef(); }
        ~string() { data->removeRef(); }
        string operator=(const char*c) {
            data->removeRef();
            data = new Data(c);
            return *this;
        }
        string operator=(const string&d) {
            d.data->addRef(); // Add ref before removing old ref
            data->removeRef(); // (in case d.data == data)
            data = d.data;
            return *this;
        }
        Proxy operator[](int i) { return Proxy(this,i); }
        char operator[](int i) char { return data->data[i]; }
        Iterator begin() { return Iterator(this, 0); }
        ConstIterator begin() const { return ConstIterator(this,0); }
        Iterator end() { return Iterator(this,data->len); }
        ConstIterator end() const { return ConstIterator(this,data->len); }
        ReverseIterator rbegin() { return ReverseIterator(this,data->len); }
        ConstReverseIterator rbegin() {
            return ConstReverseIterator(this,data->len); }
        ReverseIterator rend() { return ReverseIterator(this,0); }
        ConstReverseIterator rend() const {
            return ConstReverseIterator(this,0); }
        // ... much more ...
    };

As you can see, class string::Data implements the reference counting
and enables copy-on-write. Copying a string adds a reference to the
new Data and removes one from the old Data (possibly triggering a
delete).

We also have the usual [Const][Reverse]Iterator classes with the usual
++/--/[] operators. But when the user dereferecnes an iterator, instead
of returning a char reference we return a Proxy. If the user uses this
like a character, operator char() automatically returns the correct
character from the correct string (valid as long as the string length
hasn't changed -- even if it's been relocated in memory). If the user
tries to modify the character, operator=() triggers Copy-On-Write, if
neccesary, and then does the assignment.

This solves code of this form:
    string a("Hello string!");
    string::Iterator p = a.begin(); // Fine.
    string b(a);
    *p = 'x'; // Modifies a, but not b
but it still doesn't fix code of this form:
    string a("Hello string!");
    char *c = &*a.begin(); // No!
    string b(a);
    *c = 'x'; // Modifies both strings
But really, this last case is insolvable. Rather than using an
iterator to point to a contained character, the user literally takes
the address. In general, copy-on-write means that at some times the
implementation must move the string to a new address. Retaining an
actual address of a particular character is incompatible with the
entire mechanism, but the user can do something conceptually
identical by using an Iterator.

SGI considered all of the above issues, but also considered
multi-threaded issues. You can see their excellent analysis and
some interesting conclusions (they decided not to do reference
counting at all!) by looking at
  http://www.sgi.com/Technology/STL/string_discussion.html
(and no, they don't pay me a commission for sending you there...)

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]