Dynamic buffer library

[Andrew Poelstra]

I hacked this together this morning so that I could shift my out-of-
space code away from the rest of my logic. I wanted to allow array
syntax on my dynamic buffers, so I manually created a struct with
malloc() and judicious use of void* pointers.

I decided to post it because stuff like this is breeding ground for
UB, and this group is good at finding it. (I had a dentist analogy
for that, but it didn't work out.)

Here's my code:

/* Start. */
#include <stdlib.h>
#include <string.h>

void *create_buffer (size_t size, size_t max)
{
/* We need to allocate three size_t before the actual buffer to hold
* the size of each item, the maximum number of items, and the actual
* number of items. We do it this way instead of using a struct so that
* array syntax can still be used on the returned structure. */
size_t *tmp = malloc ( (3 * sizeof *tmp) + (size * max) );

if (tmp != NULL)
{
tmp[0] = size; /* Size of each item */
tmp[1] = max; /* Maximum # of items */
tmp[2] = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp + 3 : NULL;
}

/* This function will return three possible things:
* 1. On ordinary usage, it will return the new maximum size of the buffer.
* 2. If it runs out of memory, it will return 0.
* 3. If passed NULL, it will do nothing but return maximum size of buf.
* The third case is used after the second case to recover lost size info.
* If buf is NULL, Bad Things will happen. */
size_t append_item (void *buf, void *itm)
{
size_t *tmp = (size_t *) buf - 3;
size_t size = tmp[0];
size_t max = tmp[1];
size_t num = ++tmp[2];

/* Early return on special case. */
if (itm == NULL)
return num;

/* If we don't have enough space, try and get some more. */
if (num == max) {
size_t *rtmp;
max *= 2;
while (!(rtmp = realloc (tmp, max)) && (max tmp[1]))
--max;
}

/* If we now have enough space, we're good. Otherwise, we're cooked. */
if (max num) {
memmove (buf, itm, size);
return num;
} else return 0;
}
/* End. */

It compiles in gcc with all warnings set.

--
Andrew Poelstra <http://www.wpsoftware. net/projects>
To reach me by email, use `apoelstra' at the above domain.
"Do BOTH ends of the cable need to be plugged in?" -Anon.

[Spiros Bousbouras]

Andrew Poelstra wrote:

I hacked this together this morning so that I could shift my out-of-
space code away from the rest of my logic. I wanted to allow array
syntax on my dynamic buffers, so I manually created a struct with
malloc() and judicious use of void* pointers.

I decided to post it because stuff like this is breeding ground for
UB, and this group is good at finding it. (I had a dentist analogy
for that, but it didn't work out.)

Here's my code:

/* Start. */
#include <stdlib.h>
#include <string.h>

void *create_buffer (size_t size, size_t max)
{
/* We need to allocate three size_t before the actual buffer to hold
* the size of each item, the maximum number of items, and the actual
* number of items. We do it this way instead of using a struct so that
* array syntax can still be used on the returned structure. */
size_t *tmp = malloc ( (3 * sizeof *tmp) + (size * max) );

if (tmp != NULL)
{
tmp[0] = size; /* Size of each item */
tmp[1] = max; /* Maximum # of items */
tmp[2] = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp + 3 : NULL;
}

/* This function will return three possible things:
* 1. On ordinary usage, it will return the new maximum size of the buffer.
* 2. If it runs out of memory, it will return 0.
* 3. If passed NULL, it will do nothing but return maximum size of buf.
* The third case is used after the second case to recover lost size info.
* If buf is NULL, Bad Things will happen. */
size_t append_item (void *buf, void *itm)
{
size_t *tmp = (size_t *) buf - 3;
size_t size = tmp[0];
size_t max = tmp[1];
size_t num = ++tmp[2];

/* Early return on special case. */
if (itm == NULL)
return num;

This doesn't return the maximum size of buffer.

>
/* If we don't have enough space, try and get some more. */
if (num == max) {
size_t *rtmp;
max *= 2;
while (!(rtmp = realloc (tmp, max)) && (max tmp[1]))
--max;
}

/* If we now have enough space, we're good. Otherwise, we're cooked. */
if (max num) {
memmove (buf, itm, size);

buf still points to the old memory block.
And in any case you want the new item to
be placed after the already existing ones , right ?

return num;
} else return 0;
}
/* End. */

It compiles in gcc with all warnings set.

>From the code it seems that your intention is to store

the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

[Spiros Bousbouras]

Spiros Bousbouras wrote:

Andrew Poelstra wrote:

It compiles in gcc with all warnings set.

From the code it seems that your intention is to store

the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

Ok , Google's interface is indeed broken. The line reading
"From the code it seems that your intention is to store" was
written by me but Google added a right before "From" !
It thinks it's a mail file !

I'll now start searching for a different web based interface
to usenet.

[Andrew Poelstra]

"Spiros Bousbouras" <sp****@gmail.c omwrites:

>>From the code it seems that your intention is to store

the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

The items may not be of size_t. I don't know that they're properly
aligned (this is an example of the UB I knew that I missed). What
would be the best way for me to guarantee alignment? Am I going to
need to use a union?

Thanks for your comments: I've corrected my append_item function
below (most of it was just typos and missed lines):

/* We now need to get the address of the buffer, because realloc()
* may change the value of the pointer. */
size_t append_item (void **buf, void *itm)
{
size_t *tmp = (size_t *) *buf - 3;
size_t size = tmp[0];
size_t max = tmp[1];
size_t num = ++tmp[2];

/* Early return on special case. */
if (itm == NULL)
return max;

/* If we don't have enough space, try and get some more. */
if (num == max) {
size_t *rtmp;
max *= 2;

rtmp = realloc (tmp, max);
while ((rtmp == NULL) && (max tmp[1]))
rtmp = realloc (tmp, --max);
}

/* If we now have enough space, we're good. Otherwise, we're cooked. */
if (max num) {
*buf = rtmp;
memmove (buf, itm, size);
return num;
} else return 0;
}

--
Andrew Poelstra <http://www.wpsoftware. net/projects>
To reach me by email, use `apoelstra' at the above domain.
"Do BOTH ends of the cable need to be plugged in?" -Anon.

[CBFalconer]

Spiros Bousbouras wrote:

Spiros Bousbouras wrote:

.... snip ...

>>

>From the code it seems that your intention is to store

the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

Ok , Google's interface is indeed broken. The line reading
"From the code it seems that your intention is to store" was
written by me but Google added a right before "From" !
It thinks it's a mail file !

I'll now start searching for a different web based interface
to usenet.

Now this is one area where Google is NOT broken. A blank line,
followed by the word 'From', signals the start of a mail/news
message. Adding the '>' prevents that, and will be done by all
good newsreaders.

Just get yourself a proper newsreader. Thunderbird comes to mind.

--
Some informative links:
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

[Barry Schwarz]

On Wed, 30 Aug 2006 21:48:37 GMT, Andrew Poelstra
<ap*******@fals e.sitewrote:

>
I hacked this together this morning so that I could shift my out-of-
space code away from the rest of my logic. I wanted to allow array
syntax on my dynamic buffers, so I manually created a struct with
malloc() and judicious use of void* pointers.

I decided to post it because stuff like this is breeding ground for
UB, and this group is good at finding it. (I had a dentist analogy
for that, but it didn't work out.)

Here's my code:

/* Start. */
#include <stdlib.h>
#include <string.h>

void *create_buffer (size_t size, size_t max)
{
/* We need to allocate three size_t before the actual buffer to hold
* the size of each item, the maximum number of items, and the actual
* number of items. We do it this way instead of using a struct so that
* array syntax can still be used on the returned structure. */
size_t *tmp = malloc ( (3 * sizeof *tmp) + (size * max) );

if (tmp != NULL)
{
tmp[0] = size; /* Size of each item */
tmp[1] = max; /* Maximum # of items */
tmp[2] = 0; /* Actual # of items */
}

return (tmp != NULL) ? tmp + 3 : NULL;
}

/* This function will return three possible things:
* 1. On ordinary usage, it will return the new maximum size of the buffer.
* 2. If it runs out of memory, it will return 0.
* 3. If passed NULL, it will do nothing but return maximum size of buf.
* The third case is used after the second case to recover lost size info.
* If buf is NULL, Bad Things will happen. */
size_t append_item (void *buf, void *itm)
{
size_t *tmp = (size_t *) buf - 3;
size_t size = tmp[0];
size_t max = tmp[1];
size_t num = ++tmp[2];

/* Early return on special case. */
if (itm == NULL)
return num;

/* If we don't have enough space, try and get some more. */
if (num == max) {
size_t *rtmp;
max *= 2;
while (!(rtmp = realloc (tmp, max)) && (max tmp[1]))

You forgot the 3*sizeof(size_t ) in the second parameter to realloc. If
create_buffer is called with a small value of max, your realloc could
actually reduce the amount of allocated space.

After you have reallocated the space, how does your caller know where
it is?

--max;
}

/* If we now have enough space, we're good. Otherwise, we're cooked. */
if (max num) {
memmove (buf, itm, size);

If you reallocated the space, buf need not be a valid address.

return num;
} else return 0;
}
/* End. */

It compiles in gcc with all warnings set.

Syntax is only one of many contributors to effectiveness. Necessary
but not sufficient.
Remove del for email

[Michael Mair]

Andrew Poelstra schrieb:

"Spiros Bousbouras" <sp****@gmail.c omwrites:

>>>From the code it seems that your intention is to store

the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

The items may not be of size_t. I don't know that they're properly
aligned (this is an example of the UB I knew that I missed). What
would be the best way for me to guarantee alignment? Am I going to
need to use a union?

There is no portable way that does all the work; some time ago,
I wrote a "memsize" solution that does store the size in a standard
conforming albeit ugly and wasteful way. I asked for a code review
back then but did not receive any response; you are welcome to take
out the useful part of the ideas:
<36************ *@individual.ne t>
Download seems still possible.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Andrew Poelstra]

Michael Mair <Mi**********@i nvalid.invalidw rites:

Andrew Poelstra schrieb:

>"Spiros Bousbouras" <sp****@gmail.c omwrites:

>>>>From the code it seems that your intention is to store
the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

The items may not be of size_t. I don't know that they're properly
aligned (this is an example of the UB I knew that I missed). What
would be the best way for me to guarantee alignment? Am I going to
need to use a union?

There is no portable way that does all the work; some time ago,
I wrote a "memsize" solution that does store the size in a standard
conforming albeit ugly and wasteful way. I asked for a code review
back then but did not receive any response; you are welcome to take
out the useful part of the ideas:
<36************ *@individual.ne t>
Download seems still possible.

Thanks! That'll be useful, and probably end up being my solution.
A quick question, though, is struct padding consistant?

That is, for every struct { int x, size_t y, float z }, will (&z - &x)
always be the same number? Because if so, a more efficient solution
could be found.

--
Andrew Poelstra <http://www.wpsoftware. net/projects>
To reach me by email, use `apoelstra' at the above domain.
"Do BOTH ends of the cable need to be plugged in?" -Anon.

[Michael Mair]

Andrew Poelstra schrieb:

Michael Mair <Mi**********@i nvalid.invalidw rites:

>>Andrew Poelstra schrieb:

>>>"Spiros Bousbouras" <sp****@gmail.c omwrites:
>From the code it seems that your intention is to store
the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

The items may not be of size_t. I don't know that they're properly
aligned (this is an example of the UB I knew that I missed). What
would be the best way for me to guarantee alignment? Am I going to
need to use a union?

There is no portable way that does all the work; some time ago,
I wrote a "memsize" solution that does store the size in a standard
conforming albeit ugly and wasteful way. I asked for a code review
back then but did not receive any response; you are welcome to take
out the useful part of the ideas:
<36************ *@individual.ne t>
Download seems still possible.

Thanks! That'll be useful, and probably end up being my solution.

A quick question, though, is struct padding consistant?

That is, for every struct { int x, size_t y, float z }, will (&z - &x)
always be the same number? Because if so, a more efficient solution
could be found.

If you always use the same identifiers for members of structs
with this layout and this sequence of types in your source: Yes
(see "compatible type" in the standard).
If not: The standard does not guarantee it but in every
implementation worth its salt, yes.
Read the bits about compatible types w.r.t. structure types and
about the "common initial sequence" for unions in the standard
to get a feeling about what is guaranteed (C90 or C99).
The DS900x series probably uses a member name based struct layout
for struct types not used in a union...

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Spiros Bousbouras]

Michael Mair wrote:

Andrew Poelstra schrieb:

"Spiros Bousbouras" <sp****@gmail.c omwrites:

>>From the code it seems that your intention is to store
the "items" starting at buf[3]. Are the items of type
size_t ? If not how do you know that buf[3] is properly
aligned ?

The items may not be of size_t. I don't know that they're properly
aligned (this is an example of the UB I knew that I missed). What
would be the best way for me to guarantee alignment? Am I going to
need to use a union?

There is no portable way that does all the work; some time ago,
I wrote a "memsize" solution that does store the size in a standard
conforming albeit ugly and wasteful way. I asked for a code review
back then but did not receive any response; you are welcome to take
out the useful part of the ideas:
<36************ *@individual.ne t>
Download seems still possible.

This may be interesting as an academic exercise but
personally I don't see the point of storing the size of
the buffer in the buffer. Whoever needs to use the buffer
will need to know the location of it so if they can remember
the location then why not also the size ?

The way I'd do it would be to have a structure
struct buffer{size_t size ; size_t max ; size_t num ;
void * beg_of_bf ;}
and pass pointers to buffer to the functions
create_buffer and append_item

In the case of create_buffer the caller would
initialize fields size and max and the function
the fields num (set to 0) and beg_of_bf

In the case of append_item the return value
will determine if the appending was done
succesfully and if yes it will update num and
possibly also max and beg_of_bf if reallocation
was required.