[Mesa-dev] [PATCH 1/2] util: add stringbuf library
Thomas Helland
thomashelland90 at gmail.com
Sat Aug 26 19:18:52 UTC 2017
Plowed through it a couple times, and it looks solid to me.
After thinking through it a couple times it seems like this
should be more performant than my modification of Vladislav's
original implementation. Would be nice to see a performance
comparison though. I'll try to get some numbers up for it.
In the meantime, you can have my:
Reviewed-by: Thomas Helland<thomashelland90 at gmail.com>
2017-08-26 14:11 GMT+00:00 Nicolai Hähnle <nhaehnle at gmail.com>:
> From: Nicolai Hähnle <nicolai.haehnle at amd.com>
>
> For building long strings by successive append operations.
> ---
> src/util/Makefile.sources | 2 +
> src/util/stringbuf.c | 185 ++++++++++++++++++++++++++++++++++++++++++++++
> src/util/stringbuf.h | 97 ++++++++++++++++++++++++
> 3 files changed, 284 insertions(+)
> create mode 100644 src/util/stringbuf.c
> create mode 100644 src/util/stringbuf.h
>
> diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources
> index 3315285f05e..b7744fe8cb0 100644
> --- a/src/util/Makefile.sources
> +++ b/src/util/Makefile.sources
> @@ -32,20 +32,22 @@ MESA_UTIL_FILES := \
> rgtc.c \
> rgtc.h \
> rounding.h \
> set.c \
> set.h \
> simple_list.h \
> slab.c \
> slab.h \
> string_to_uint_map.cpp \
> string_to_uint_map.h \
> + stringbuf.c \
> + stringbuf.h \
> strndup.h \
> strtod.c \
> strtod.h \
> texcompress_rgtc_tmp.h \
> u_atomic.c \
> u_atomic.h \
> u_dynarray.h \
> u_endian.h \
> u_queue.c \
> u_queue.h \
> diff --git a/src/util/stringbuf.c b/src/util/stringbuf.c
> new file mode 100644
> index 00000000000..b9a2a624fb5
> --- /dev/null
> +++ b/src/util/stringbuf.c
> @@ -0,0 +1,185 @@
> +/*
> + * Copyright 2017 Advanced Micro Devices, Inc.
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * on the rights to use, copy, modify, merge, publish, distribute, sub
> + * license, and/or sell copies of the Software, and to permit persons to whom
> + * the Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
> + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
> + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
> + * USE OR OTHER DEALINGS IN THE SOFTWARE.
> + */
> +
> +#include "stringbuf.h"
> +
> +#include <limits.h>
> +#include <stdarg.h>
> +#include <stdio.h>
> +#include <string.h>
> +
> +#include "ralloc.h"
> +#include "u_string.h"
> +
> +struct stringbuf_chunk {
> + struct stringbuf_chunk *next;
> + unsigned len, max;
> + char buf[];
> +};
> +
> +struct stringbuf {
> + struct stringbuf_chunk *head;
> + struct stringbuf_chunk *tail;
> + unsigned size;
> + bool error;
> +};
> +
> +
> +struct stringbuf *
> +stringbuf_new(void *parent)
> +{
> + static const unsigned initial_max = 512;
> + struct stringbuf *sb = rzalloc_size(parent, sizeof(*sb));
> + if (!sb)
> + return NULL;
> +
> + sb->head = sb->tail = ralloc_size(sb, sizeof(*sb->head) + initial_max);
> + if (!sb->head) {
> + ralloc_free(sb);
> + return NULL;
> + }
> + sb->head->next = NULL;
> + sb->head->len = 0;
> + sb->head->max = initial_max;
> + return sb;
> +}
> +
> +char *
> +stringbuf_build(struct stringbuf *sb)
> +{
> + if (sb->error)
> + return NULL;
> +
> + char *result = ralloc_size(ralloc_parent(sb), sb->size + 1);
> + char *p = result;
> +
> + for (struct stringbuf_chunk *chunk = sb->head; chunk; chunk = chunk->next) {
> + memcpy(p, chunk->buf, chunk->len);
> + p += chunk->len;
> + }
> + assert(p - result == sb->size);
> + *p = 0;
> +
> + return result;
> +}
> +
> +bool
> +stringbuf_error(struct stringbuf *sb)
> +{
> + return sb->error;
> +}
> +
> +static struct stringbuf_chunk *
> +stringbuf_new_chunk(struct stringbuf *sb, size_t min_size)
> +{
> + size_t size = MAX3(min_size, sb->tail->max, sb->size / 4);
> + if (UINT_MAX - sb->size < size) {
> + sb->error = true;
> + return NULL;
> + }
> +
> + struct stringbuf_chunk *chunk = ralloc_size(sb, sizeof(*chunk) + size);
> + if (!chunk) {
> + sb->error = true;
> + return NULL;
> + }
> +
> + chunk->next = NULL;
> + chunk->len = 0;
> + chunk->max = size;
> +
> + sb->tail->next = chunk;
> + sb->tail = chunk;
> + return chunk;
> +}
> +
> +bool
> +stringbuf_append(struct stringbuf *sb, const char *str, size_t str_size)
> +{
> + struct stringbuf_chunk *chunk = sb->tail;
> +
> + if (chunk->max - chunk->len < str_size) {
> + chunk = stringbuf_new_chunk(sb, str_size);
> + if (!chunk)
> + return false;
> + }
> +
> + memcpy(chunk->buf + chunk->len, str, str_size);
> + chunk->len += str_size;
> + sb->size += str_size;
> + return true;
> +}
> +
> +bool
> +stringbuf_vprintf(struct stringbuf *sb, const char *fmt, va_list va)
> +{
> + struct stringbuf_chunk *chunk = sb->tail;
> + va_list va_copy;
> + int ret, ret_retry;
> +
> + va_copy(va_copy, va);
> +
> + ret = util_vsnprintf(chunk->buf + chunk->len, chunk->max - chunk->len, fmt, va);
> + if (ret < 0) {
> + sb->error = true;
> + return false;
> + }
> +
> + if (ret <= chunk->max - chunk->len) {
> + chunk->len += ret;
> + sb->size += ret;
> + return true;
> + }
> +
> + chunk = stringbuf_new_chunk(sb, ret + 1);
> + if (!chunk)
> + return false;
> +
> + assert(chunk->len == 0);
> + ret_retry = vsnprintf(chunk->buf, chunk->max, fmt, va_copy);
> + if (ret_retry < 0) {
> + sb->error = true;
> + return false;
> + }
> +
> + assert(ret_retry == ret);
> + assert(ret_retry < chunk->max);
> +
> + chunk->len = ret_retry;
> + sb->size += ret_retry;
> + return true;
> +}
> +
> +bool
> +stringbuf_printf(struct stringbuf *sb, const char *fmt, ...)
> +{
> + va_list va;
> + bool ret;
> +
> + va_start(va, fmt);
> + ret = stringbuf_vprintf(sb, fmt, va);
> + va_end(va);
> +
> + return ret;
> +}
> +
> diff --git a/src/util/stringbuf.h b/src/util/stringbuf.h
> new file mode 100644
> index 00000000000..ca11234d0ec
> --- /dev/null
> +++ b/src/util/stringbuf.h
> @@ -0,0 +1,97 @@
> +/*
> + * Copyright 2017 Advanced Micro Devices, Inc.
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * on the rights to use, copy, modify, merge, publish, distribute, sub
> + * license, and/or sell copies of the Software, and to permit persons to whom
> + * the Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
> + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
> + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
> + * USE OR OTHER DEALINGS IN THE SOFTWARE.
> + */
> +
> +#ifndef STRINGBUF_H
> +#define STRINGBUF_H
> +
> +#include <stdarg.h>
> +#include <stdbool.h>
> +#include <stddef.h>
> +
> +#include "macros.h"
> +
> +/**
> + * \file stringbuf.h
> + *
> + * ralloc-based sring buffer suitable for building large strings by appending.
> + */
> +
> +struct stringbuf;
> +
> +/**
> + * Create a new string buffer with the given ralloc parent.
> + *
> + * All internal allocations will be children of the main stringbuf object,
> + * so you can use \ref ralloc_free to free a stringbuf.
> + */
> +struct stringbuf *stringbuf_new(void *parent) MALLOCLIKE;
> +
> +/**
> + * Concatenate all the pieces that were appended to the string buffer into
> + * one big string.
> + *
> + * This will fail if a memory allocation error occurred during any append
> + * operation on \p sb. On the other hand, if memory allocation fails during
> + * the concatenation, the error flag of \p sb is \em not set.
> + *
> + * \return A NUL-terminated, newly allocated copy of the final string. Its
> + * ralloc parent will be the parent of \p sb.
> + */
> +char *stringbuf_build(struct stringbuf *sb) MALLOCLIKE;
> +
> +/**
> + * Check whether a memory allocation error occurred during any operation on
> + * \p sb (except for \ref stringbuf_build).
> + *
> + * Basically, this yields one summary error flag that can be checked after all
> + * append operations instead of checking the return value of each individual
> + * append operation.
> + *
> + * \return True if any memory allocation failed during appending to \p sb.
> + */
> +bool stringbuf_error(struct stringbuf *sb);
> +
> +/**
> + * Append \p str_size bytes of \p str to \p sb.
> + *
> + * No strlen calls are made.
> + *
> + * \return True unless memory allocation failed.
> + */
> +bool stringbuf_append(struct stringbuf *sb, const char *str, size_t str_size);
> +
> +/**
> + * Append a formatted string to \p sb.
> + *
> + * \return True unless memory allocation failed.
> + */
> +bool stringbuf_vprintf(struct stringbuf *sb, const char *fmt, va_list va);
> +
> +/**
> + * Append a formatted string to \p sb.
> + *
> + * \return True unless memory allocation failed.
> + */
> +bool stringbuf_printf(struct stringbuf *sb, const char *fmt, ...) PRINTFLIKE(2, 3);
> +
> +#endif /* STRINGBUF_H */
> --
> 2.11.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list