Ben C wrote:
[much snippage]
Or, comparably (but considerably more complicated):
String a = ((b + c) - "zog") * " ";
where string "addition" means "concatenate" (the usual definition
for string addition), "subtraction" means "remove the first copy
of the target string, if there is one", and string "multiplication"
means "repeatedly insert this string". Hence if b and c hold "xyz"
and "ogle" respectively, the "sum" is "xyzogle", subtracting "zog"
yields "xyle", and multiplying by " " yields "x y l e " (including
the final space).
Indeed. Suppose the String data structure is much like Paul Hsieh's
favorite, but perhaps with a few more bells and whistles (I have not
looked at his implementation):
struct StringBuffer;
struct String {
char *bytes; /* the bytes (if any) in the string */
size_t slen; /* the length of the string */
struct StringBuffer *buf; /* the underlying buffer (may be shared) */
struct String *next; /* linked list in case of shared references */
};
struct StringBuffer {
char *base; /* base address of buffer */
size_t bufsize; /* size of buffer */
size_t refcnt; /* number of references to this buffer */
struct String *firstref; /* head of reference chain */
};
This gives us functions that, in C, might look like:
/* "Copy" a string: return a new reference to an existing string */
struct String *String_copy(struct String *old) {
struct String *new = xmalloc(sizeof *new);
/* xmalloc is just malloc plus panic-if-out-of-space */
/* copy the underlying string's info */
new->bytes = old->bytes;
new->slen = old->slen;
new->buf = old->buf;
/* insert into list, remembering new ref */
new->next = old;
new->buf->refcnt++;
new->buf->firstref = new;
}
In this case, making a second copy of a very long string is
quite cheap. So is making a sub-string out of an existing
string:
/*
* Shrink a string by removing "frontoff" charcters from the
* front, and "backoff" characters from the back. The frontoff
* may be negative to extend the string back to its original length
* although typically exactly one will be zero (remove head or
* tail part of string). The backoff must be nonnegative
* (because tail parts of buffers are not necessarily valid).
*/
void String_shrink(struct String *s, int frontoff, int backoff) {
if (frontoff) {
if (frontoff < 0) {
size_t maxshrink = s->bytes - s->buf->base;
/* NB: this can be optimized to fall into the "else" */
frontoff = -frontoff;
if (frontoff > maxshrink)
frontoff = maxshrink;
s->len += frontoff;
s->bytes -= frontoff;
} else {
if (s->slen < frontoff)
frontoff = s->len;
s->len -= frontoff;
s->bytes += frontoff;
}
}
if (backoff) {
if (backoff < 0)
panic("bad call to String_shrink");
if (s->len < backoff)
backoff = s->len;
s->len -= backoff;
}
}
Now, of course, in order to *modify* the *contents* of a string,
we have to check whether the string is shared, and if so, "break"
the sharing:
/* inline */ struct String *String_preptomod(struct String *s) {
return (s->buf->refcnt == 1) ? s : String_private_copy(s);
}
[without complicated C++ style mechanisms,]
I still don't get your point.
OK: so write the "operator" functions for +, -, and * above and
tell us what happens to any intermediate copies of the String
structures that are created by each addition, subtraction, and
multiply.
Show us the code, and "we" (Ben C and I, perhaps) will show you
where you have re-invented the (detailed and hairy) C++ mechanisms
(or, contrariwise, have assumed that your underlying language has
garbage collection, so that temporary objects can be created and
then thrown away without calling "constructor" and "destructor"
functions on references, reference-copies, etc.; if you do have
constructors and destructors, you also have to decide whether such
functions can or must be "virtual" or not, and so on).
