Dynamic buffer library

[Dave Thompson]

Thanks to Michael Mair, Barry Schwartz, and Spiros Bousbouras for their
suggestions.

OT: It appears that Google's interface has indeed been fixed, and it's
actually very impressive now.

Here's my new version:

#include <stdlib.h>
#include <string.h>
#include "dynamic_buffer.h"

struct dbuffer_s {
size_t size;
size_t max;
size_t num;
void *content;

This is completely different from your earlier version. It is a
pointer to space allocated somewhere else, not adjacent.

};

void *create_buffer (size_t size, size_t max)
{
struct dbuffer_s *tmp = malloc (sizeof *tmp);

if (tmp != NULL)
{
tmp->size = size; /* Size of each item */
tmp->max = max; /* Maximum # of items */
tmp->num = 0; /* Actual # of items */

tmp->content = calloc (size * max);

That's wrong. Either malloc (size * max) or calloc (size, max) with
two separate arguments. Since your logic tries to ensure that each new
'item's worth of space is written before it can be read, the extra
work calloc (probably) does is wasted and malloc is better.

Oh, and either way should probably check for overflow:
if( max > SIZE_MAX / size ){ give up now }

if (tmp->content == NULL) {
free (tmp);
tmp = NULL;
}
}

return (tmp != NULL) ? tmp->content : NULL;
}

In nonerror case, this returns the value of the pointer tmp->content,
which is the address of space somewhere completely unrelated to the
address of the space for struct dbuffer_s that tmp points to.

/* This function will return three possible things:
* The new maximum on success
* The old maximum on failure (or itm == NULL)

How is the caller supposed to distinguish these? Is it required to
keep track of the current usage? If so, doesn't that reduce the
benefit you intended to provide by encapsulating this functionality?

* 0 on buf == NULL
*/

size_t append_item (void **buf, void *itm)
{
static struct dbuffer_s stmp; /* Used for length calculations. */
size_t distance_back = (size_t) &stmp.content - (size_t) &stmp;

struct dbuffer_s *tmp;

/* Initial error conditions */
if (buf == NULL)
return 0;

Personally I would make this an assert() or some similar but
project/environment-specific fatal error. If the caller is so screwed
up as to be trying to use an unallocated buffer, it is probably so
screwed up it won't handle an error return usefully.

tmp = (struct dbuffer_s *) ((unsigned char *) buf - distance_back);

Assuming tmp is the value returned from create_buffer, this won't work
at all. If you want to do this kind of kludge, and accept the issues
about ensuring alignment which <ObStd> can't be done for all cases
guaranteed portably but </> can be done for most common systems, you
need to allocate _one_ chunk of space big enough for the header plus
padding plus the data, give the caller the address to the data part,
and step backward from that to find the header -- leaving any excess
padding, unusually, _before_ the header.

And in that case you don't need to do it explicitly; assuming buf
actually points to the caller's void* pointer (NOT portably a data*
pointer, see my previous post) just use:
struct dbuffer_s * hdrp = (struct dbuffer_s *) *buf - 1;
Or you can (and when I did this I preferred to):
struct dbuffer_s * hdrp = /* (struct dbuffer_s *) */ *buf;
and then use hdrp[-1].field rather than hdrp->field .

if (itm == NULL)
return tmp->size;

/* Here's where the (attempted) reallocation starts: */
if (tmp->num == tmp->max)
{
size_t max = tmp->max * 2;

Should check for overflow: old tmp->max > SIZE_MAX/2 on the count, but
old tmp->max > SIZE_MAX/size/2 for the resulting allocation. Though on
most systems you will run out of available memory and realloc() will
fail sufficiently before you run out of bits in size_t.

void *ptmp = tmp->content; /* tmp->content is *buf. */

This initialization is useless; you immediately overwrite it.

ptmp = realloc (tmp->content, max * tmp->size);
while (ptmp == NULL)
{
ptmp = realloc (tmp->content, --max * tmp->size);

/* If we failed, we failed. */
if (max == tmp->max)
break;
}

There's no point (re)trying the old tmp->max; see my previous post.

/* If we pulled anything off, reflect it in tmp: */
if (max > tmp->max)
tmp->content = ptmp;
}

And update tmp->max, see my previous post.

/* Now the actual addition code: */
if (tmp->num < tmp->max)
memmove (itm, (unsigned char *) tmp->content + tmp->num++,
tmp->size);

That's backwards; the first argument is the destination, which should
be (anychar*)content + (num++) * size (note scaling by size), and the
second argument should be itm, the object you are adding.

And as I previously posted, these should never overlap for a valid
caller, so you only need memcpy() not memmove(), but will screw up if
the caller gives you an element in the old pre-reallocated array.

return tmp->size;
}

- David.Thompson1 at worldnet.att.net

 

[Andrew Poelstra]

Thank you so much for your comments, Dave. I've decided to simply use
C99 for my code; that way I get SIZE_MAX and I get flexible array
members, which are very useful for my new (hopefully free of
non-trivial mistakes) version. I'm aware that there aren't any popular
C99 compilers, but this appears to compiler properly with the latest
version of gcc, and I can always make object files for people with
non-supported compilers. I've also deliberately not included functions
for checking the buffer size, etc: these are trivial additions that
would distract from the much more bug-conducive body.

Here's the code:

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>

#include "dynamic_buffer.h" /* This contains nothing but function
prototypes*/

/* Thanks to Dave Thompson for all his suggestions, fixes, and pointing
* out the things I overlooked. */

struct dbuffer_s {
size_t size;
size_t max;
size_t num;
unsigned char content[];
};

void *create_buffer (size_t size, size_t max)
{
struct dbuffer_s *tmp = NULL;

/* Check for overflow */
if (max > SIZE_MAX / size)
tmp = malloc (sizeof *tmp + size * max);

if (tmp != NULL)
{
tmp->size = size; /* Size of each item */
tmp->max = max; /* Maximum # of items */
tmp->num = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp->content : NULL;
}

void delete_buffer (void *buf)
{
free ((char *) buf - offsetof (struct dbuffer_s, content));
return;
}


/* This function will return three possible things:
* The new (potentially reallocated) buffer on success
* NULL on failure.
*/

void *append_item (void *buf, void *itm)
{
struct dbuffer_s *tmp;

assert (buf != NULL);
assert (itm != NULL);

tmp = (struct dbuffer_s *) ((char *) buf - offsetof (struct
dbuffer_s, content));

/* Here's where the (attempted) reallocation starts: */
if (tmp->num == tmp->max)
{
size_t max = tmp->max * 2;
void *ptmp = realloc (tmp->content, sizeof *tmp + max * tmp->size);

while (ptmp == NULL)
{
/* If we failed, we failed. */
if (max == tmp->max + 1)
return NULL;

ptmp = realloc (tmp->content, sizeof *tmp + --max * tmp->size);
}

tmp = ptmp;
/* Now the actual addition code: */
memmove ((char *) tmp->content + tmp->num++, itm, tmp->size);
}

return tmp->content;
}

 

[Andrew Poelstra]

Thank you so much for your comments, Dave. I've decided to simply use
C99 for my code; that way I get SIZE_MAX and I get flexible array
members, which are very useful for my new (hopefully free of
non-trivial mistakes) version. I'm aware that there aren't any popular
C99 compilers, but this appears to compiler properly with the latest
version of gcc, and I can always make object files for people with
non-supported compilers. I've also deliberately not included functions
for checking the buffer size, etc: these are trivial additions that
would distract from the much more bug-conducive body.

Here's the code:

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>

#include "dynamic_buffer.h" /* This contains nothing but function
prototypes*/

/* Thanks to Dave Thompson for all his suggestions, fixes, and pointing
* out the things I overlooked. */

struct dbuffer_s {
size_t size;
size_t max;
size_t num;
unsigned char content[];
};

void *create_buffer (size_t size, size_t max)
{
struct dbuffer_s *tmp = NULL;

/* Check for overflow */
if (max > SIZE_MAX / size)
tmp = malloc (sizeof *tmp + size * max);

if (tmp != NULL)
{
tmp->size = size; /* Size of each item */
tmp->max = max; /* Maximum # of items */
tmp->num = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp->content : NULL;
}

void delete_buffer (void *buf)
{
free ((char *) buf - offsetof (struct dbuffer_s, content));
return;
}


/* This function will return three possible things:
* The new (potentially reallocated) buffer on success
* NULL on failure.
*/

void *append_item (void *buf, void *itm)
{
struct dbuffer_s *tmp;

assert (buf != NULL);
assert (itm != NULL);

tmp = (struct dbuffer_s *) ((char *) buf - offsetof (struct
dbuffer_s, content));

/* Here's where the (attempted) reallocation starts: */
if (tmp->num == tmp->max)
{
size_t max = tmp->max * 2;
void *ptmp = realloc (tmp->content, sizeof *tmp + max * tmp->size);

while (ptmp == NULL)
{
/* If we failed, we failed. */
if (max == tmp->max + 1)
return NULL;

ptmp = realloc (tmp->content, sizeof *tmp + --max * tmp->size);
}

tmp = ptmp;
/* Now the actual addition code: */
memmove ((char *) tmp->content + tmp->num++, itm, tmp->size);
}

return tmp->content;
}

 

[Ben Pfaff]

I've decided to simply use C99 for my code; that way I get
SIZE_MAX and [...]

For what it's worth, in the absence of C99, SIZE_MAX is easy to
define:
#define SIZE_MAX ((size_t) -1)
(Unfortunately it's not suitable for use in preprocessing
directives, as SIZE_MAX is supposed to be.)

 

[Michael Mair]

It doesn't seem like it would be that hard to make
the tags be unique, even across the entire program.
What am I missing?

Background: Several different "sources" generating C code
without much of an interface to communicate things such as
struct types (because struct tags are generated, too, and
may depend on order).
However, with the additional "identical tag" stipulation of
C99, the people who wanted to tinker with the "no tag" trick
are out of luck. Good enough for me.

Sorry for taking longer to get back to you.

Cheers
Michael

 

[Andrew Poelstra]

Thank you so much for your comments, Dave. I've decided to simply use
C99 for my code; that way I get SIZE_MAX and I get flexible array
members, which are very useful for my new (hopefully free of
non-trivial mistakes) version. I'm aware that there aren't any popular
C99 compilers, but this appears to compiler properly with the latest
version of gcc, and I can always make object files for people with
non-supported compilers. I've also deliberately not included functions
for checking the buffer size, etc: these are trivial additions that
would distract from the much more bug-conducive body.

Here's the code:

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>

#include "dynamic_buffer.h" /* This contains nothing but function
prototypes*/

/* Thanks to Dave Thompson for all his suggestions, fixes, and pointing
* out the things I overlooked. */

struct dbuffer_s {
size_t size;
size_t max;
size_t num;
unsigned char content[];
};

void *create_buffer (size_t size, size_t max)
{
struct dbuffer_s *tmp = NULL;

/* Check for overflow */
if (max > SIZE_MAX / size)
tmp = malloc (sizeof *tmp + size * max);

if (tmp != NULL)
{
tmp->size = size; /* Size of each item */
tmp->max = max; /* Maximum # of items */
tmp->num = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp->content : NULL;
}

void delete_buffer (void *buf)
{
free ((char *) buf - offsetof (struct dbuffer_s, content));
return;
}


/* This function will return three possible things:
* The new (potentially reallocated) buffer on success
* NULL on failure.
*/

void *append_item (void *buf, void *itm)
{
struct dbuffer_s *tmp;

assert (buf != NULL);
assert (itm != NULL);

tmp = (struct dbuffer_s *) ((char *) buf - offsetof (struct
dbuffer_s, content));

/* Here's where the (attempted) reallocation starts: */
if (tmp->num == tmp->max)
{
size_t max = tmp->max * 2;
void *ptmp = realloc (tmp->content, sizeof *tmp + max * tmp->size);

while (ptmp == NULL)
{
/* If we failed, we failed. */
if (max == tmp->max + 1)
return NULL;

ptmp = realloc (tmp->content, sizeof *tmp + --max * tmp->size);
}

tmp = ptmp;
/* Now the actual addition code: */
memmove ((char *) tmp->content + tmp->num++, itm, tmp->size);

This should be moved down a block (so that it always runs), and changed
to:
memmove ((char *) tmp->content + tmp->num++ * tmp->size, itm,
tmp->size);

 

[Dave Thompson]

Thank you so much for your comments, Dave. I've decided to simply use
C99 for my code; that way I get SIZE_MAX and I get flexible array
members, which are very useful for my new (hopefully free of
non-trivial mistakes) version.

Almost; I see you already caught the one real error:
memmove /* but could be memcpy */
( (char*)content + num++ * size, itm, size )

But one minor disagreement:

I'm aware that there aren't any popular
C99 compilers, but this appears to compiler properly with the latest
version of gcc, and I can always make object files for people with
non-supported compilers.

Not necessarily; only if you have a compiler targetted to their
platform, and if that platform has more than one format of object file
(some do) to their object file. For instance, I do some work on
Tandem^WCompaq^WHP NonStop, who have only since about 1995 their own C
compiler but since about 1975 their own object format quite unlike
anything you have seen and AFAICT not supported by GCC/binutils.
More seriously, there are two popular but different object formats for
Windows: COFF used by M$, and ELF used by gcc.

OTOH, your code is easily enough modified to C89 or even earlier,
or, to be frank, just rewritten off the top of one's head in about 10
minutes, that I don't consider this a problem.


- David.Thompson1 at worldnet.att.net