[01/11] Add append method to qstring and empty constructor

This allows qstring to be used for dynamic string construction.

Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
---
 qstring.c |   37 ++++++++++++++++++++++++++++++++++++-
 qstring.h |    4 ++++
 2 files changed, 40 insertions(+), 1 deletions(-)

On Sat, 17 Oct 2009 08:36:01 -0500
Anthony Liguori <aliguori@us.ibm.com> wrote:

> This allows qstring to be used for dynamic string construction.
> 
> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
> ---
>  qstring.c |   37 ++++++++++++++++++++++++++++++++++++-
>  qstring.h |    4 ++++
>  2 files changed, 40 insertions(+), 1 deletions(-)
> 
> diff --git a/qstring.c b/qstring.c
> index 6d411da..441a9e6 100644
> --- a/qstring.c
> +++ b/qstring.c
> @@ -21,6 +21,16 @@ static const QType qstring_type = {
>  };
>  
>  /**
> + * qstring_new(): Create a new empty QString
> + *
> + * Return strong reference.
> + */
> +QString *qstring_new(void)
> +{
> +    return qstring_from_str("");
> +}
> +
> +/**
>   * qstring_from_str(): Create a new QString from a regular C string
>   *
>   * Return strong reference.
> @@ -30,12 +40,37 @@ QString *qstring_from_str(const char *str)
>      QString *qstring;
>  
>      qstring = qemu_malloc(sizeof(*qstring));
> -    qstring->string = qemu_strdup(str);
> +
> +    qstring->length = strlen(str);
> +    qstring->capacity = qstring->length;
> +
> +    qstring->string = qemu_malloc(qstring->capacity + 1);
> +    memcpy(qstring->string, str, qstring->length);
> +    qstring->string[qstring->length] = 0;

 Couldn't this be:

qstring->string = qemu_strdup(str);
qstring->length = qstring->capacity = strlen(str);

> +
>      QOBJECT_INIT(qstring, &qstring_type);
>  
>      return qstring;
>  }
>  
> +/* qstring_append(): Append a C string to a QString
> + */

 Forgot the 'little roof' in the comment style. :-)

> +void qstring_append(QString *qstring, const char *str)
> +{
> +    size_t len = strlen(str);
> +
> +    if (qstring->capacity < (qstring->length + len)) {
> +        qstring->capacity += len;
> +        qstring->capacity *= 2; /* use exponential growth */
> +
> +        qstring->string = qemu_realloc(qstring->string, qstring->capacity + 1);
> +    }

 Why do we need to double it? Wouldn't be enough to only keep track
of the current string length and add 'len' to it? We could drop
'capacity' then.

> +
> +    memcpy(qstring->string + qstring->length, str, len);
> +    qstring->length += len;
> +    qstring->string[qstring->length] = 0;

 I would use strcat().

> +}
> +
>  /**
>   * qobject_to_qstring(): Convert a QObject to a QString
>   */
> diff --git a/qstring.h b/qstring.h
> index e012cb7..65905d4 100644
> --- a/qstring.h
> +++ b/qstring.h
> @@ -6,10 +6,14 @@
>  typedef struct QString {
>      QObject_HEAD;
>      char *string;
> +    size_t length;
> +    size_t capacity;
>  } QString;
>  
> +QString *qstring_new(void);
>  QString *qstring_from_str(const char *str);
>  const char *qstring_get_str(const QString *qstring);
> +void qstring_append(QString *qstring, const char *str);
>  QString *qobject_to_qstring(const QObject *obj);
>  
>  #endif /* QSTRING_H */

Luiz Capitulino wrote:
> >      qstring = qemu_malloc(sizeof(*qstring));
> > -    qstring->string = qemu_strdup(str);
> > +
> > +    qstring->length = strlen(str);
> > +    qstring->capacity = qstring->length;
> > +
> > +    qstring->string = qemu_malloc(qstring->capacity + 1);
> > +    memcpy(qstring->string, str, qstring->length);
> > +    qstring->string[qstring->length] = 0;
> 
>  Couldn't this be:
> 
> qstring->string = qemu_strdup(str);
> qstring->length = qstring->capacity = strlen(str);

Probably to have one call to strlen() instead of two (one inside
qemu_strdup()).

> > +void qstring_append(QString *qstring, const char *str)
> > +{
> > +    size_t len = strlen(str);
> > +
> > +    if (qstring->capacity < (qstring->length + len)) {
> > +        qstring->capacity += len;
> > +        qstring->capacity *= 2; /* use exponential growth */
> > +
> > +        qstring->string = qemu_realloc(qstring->string, qstring->capacity + 1);
> > +    }
> 
>  Why do we need to double it? Wouldn't be enough to only keep track
> of the current string length and add 'len' to it? We could drop
> 'capacity' then.

You need exponential growth if large stringes are to be grown in O(n)
time where n is the number of characters, appended in small pieces.

Think about the time spent copying bytes every time qemu_realloc() is called.

If you just add 'len' each time, think about appending 1 byte 10^4
times.  It will copy approximately 10^8/2 bytes, which is a lot just to
make a string 10^4 bytes long.

But += len; *= 2 is not necessary.  *= 2 is enough, provided the
result is large enough.

> > +    memcpy(qstring->string + qstring->length, str, len);
> > +    qstring->length += len;
> > +    qstring->string[qstring->length] = 0;
> 
>  I would use strcat().

Again, that's an extra call to strlen(), traversing the string twice instead of once.
Doesn't make much different for small strings, only large ones.

-- Jamie