conservative static region allocator...

[Chris M. Thomasson]

Here is the code:

http://pastebin.com/f71ae5385


This region allocator does not force all allocations to be aligned up to a
so-called maximum alignment like `malloc' and friends are required to do.
For instance, allocations for a single char will not be forced to waste the
extra alignment space. This can have benefits in space constrained
environments (e.g., embedded devices). Also, its static in nature and can be
fed with a buffer residing on the stack. There are no underlying calls to
`malloc'. This can be useful in free standing environments that do not
support heap allocation. One other thing. Its a pure region allocator which
means you do not need to free individual objects. You can free the entire
region. This is more efficient than calling `malloc()/free()' for each
object. For instance, you can destroy all the nodes in a linked list just by
freeing the region(s) in which the nodes were allocated from. There is no
need to traverse the list to free its nodes. Its a sort of "manual" garbage
collection... ;^)

Anyway, do you have any suggestions on how to improve the code?



Thanks, and I hope somebody might find this useful...

;^o

 

[Keith Thompson]

You very cleverly fight the C language to get alignments out of a buffer.

One suggestion I would make is to change the interface so that
region_alloc_type() takes a count as well as a type. In practise
people are going to want to allocate short arrays with this, most of
the time.

I'd also consider changing the name to rgalloc_type(). The rule of two.

[...]

Where does this "rule of two" come from? Personally, I think that
abbreviating "region_" to "rg" just makes the name harder to
understand; do you see some overriding benefit?

 

[Flash Gordon]

You very cleverly fight the C language to get alignments out of a buffer.

One suggestion I would make is to change the interface so that
region_alloc_type() takes a count as well as a type. In practise
people are going to want to allocate short arrays with this, most of
the time.

I'd also consider changing the name to rgalloc_type(). The rule of two.

[...]

Where does this "rule of two" come from? Personally, I think that
abbreviating "region_" to "rg" just makes the name harder to
understand; do you see some overriding benefit?

All of the rules Malcolm quotes are ones he has invented with, as far as
I can see, no supporting evidence. I agree that the abbreviation would
make it harder to read.

 

[Guest]

I'd also consider changing the name [of region_alloc_type()] to
rgalloc_type(). The rule of two.

what is the Rule Of Two?

<snip>

 

[Richard Bos]

I'd also consider changing the name [of region_alloc_type()] to
rgalloc_type(). The rule of two.

what is the Rule Of Two?

There is no such thing, but there _is_ a Double Rule of Three. Ask the
gardener if you don't believe me.

Richard

 

[Ben Bacarisse]

(e-mail address removed) said:

On 8 Mar, 15:09, "Malcolm McLean" <[email protected]>
wrote:

I'd also consider changing the name [of region_alloc_type()] to
rgalloc_type(). The rule of two.

what is the Rule Of Two?

If there is such a rule, it is unreasonable, relying as it does on
an unreasonable number.

When a programming language designer allows you to do something a
small number of times (but more than once), that's unreasonable. In
C's case, the obvious candidate is the six-unique-characters
limitation in C90 linkers, and this is a flaw not so much of C as
of ISO. As far as I'm aware, K&R C imposed no such limit.

If anything K&R C is worse (as might be expected given the era) in
that is states that not more than 8 are significant for internal names
and external names "may be less". The effect being that no minimum
length is assured, though some example systems are given with the
least generous being 6 characters ignoring case (i.e. Strcpy ==
strcpy).

Of
course, even C90 didn't exactly "impose" it - it just gave you no
recourse if breaching the limit broke things.

Ditto K&R.

 

[Walter Banks]

When a programming language designer allows you to do something a
small number of times (but more than once), that's unreasonable. In
C's case, the obvious candidate is the six-unique-characters
limitation in C90 linkers, and this is a flaw not so much of C as
of ISO.

Its origins go back to early tool sets. The Honeywell 6000 stored
6 characters in a 36 bit word later 4 9 bit chars in the same word.
PDP 8's stored two characters in 12 bit words and some PDP11
linkers which had a 6 character limit in external symbols. The linker
had 40 symbols in the supported character set and could encode
6 characters in 2 16 bit numbers.

As far as I'm aware, K&R C imposed no such limit. Of
course, even C90 didn't exactly "impose" it - it just gave you no
recourse if breaching the limit broke things.

K&R (pp179) defines first 8 at most significant characters in
identifiers and notes some of the processor exceptions.

Regards,

 

[Bartc]

Its origins go back to early tool sets. The Honeywell 6000 stored
6 characters in a 36 bit word later 4 9 bit chars in the same word.
PDP 8's stored two characters in 12 bit words and some PDP11
linkers which had a 6 character limit in external symbols. The linker
had 40 symbols in the supported character set and could encode
6 characters in 2 16 bit numbers.

I remember the use of 'sixbit' on the 36-bit pdp10, giving 6 upper-case
characters per word. And this seemed to pervade everything including
filenames and program variables.

Far from being a limitation, it made some text processing (and compiler work
in my case) easy and very efficient. Made easier by the users at the time
accepting the six-character limit on names.

 

[Chris M. Thomasson]

You very cleverly fight the C language to get alignments out of a buffer.

;^)

Yeah, it does seem as if it will work pretty darn good as long as
`sizeof(size_t) == sizeof(void*)'. Humm... Perhaps I should add a macro that
the user can pre-define in order to setup a custom integral type that can be
freely converted to a void* in the cast that `sizeof(size_t) !=
sizeof(void*)'. Something simple like this:
___________________________________________________________
#if ! defined (CUSTOM_UINTPTR_TYPE)
typedef size_t uintptr_type;
#else
typedef CUSTOM_UINTPTR_TYPE uintptr_type;
#endif


typedef char static_assert[
sizeof(uintptr_type) == sizeof(void*) ? 1 : -1
];
___________________________________________________________




That way, if the user knows that size_t is not sufficient, they can simply
define `CUSTOM_UINTPTR_TYPE' to a type that is sufficient. Also, I should
probably try to detect if the user is compiling on a C99 compiler, and just
use the types from <stdint.h> (e.g., uintptr_t). However, I would have to
check to see if its under a XSI conformant system. AFAICT, the types
`intptr_t/uintptr_t' are optional. Well, I guess I could just see if the
`UINTPTR_MAX' macro is defined.

One suggestion I would make is to change the interface so that
region_alloc_type() takes a count as well as a type. In practise people
are going to want to allocate short arrays with this, most of the time.

Completely agreed; here is the mutated code:

http://pastebin.com/f207f6232

I'd also consider changing the name to rgalloc_type(). The rule of two.

I defined an alternative "condensed" API as follows:
______________________________________________________
#define rinit region_init
#define ralloc region_alloc
#define ralloct region_alloc_type
#define rallocex region_alloc_ex
#define rflush region_flush
______________________________________________________


It certainly reduces the amount of typing...

;^)

I'd strip out all the debugging code, for the release version. People
don't want clutter in code they're trying to read.

You mean remove it completely from the posted code? The preprocessor already
removes it when `NDEBUG' is defined. I must be totally misunderstanding you.

The strategy of assert failing on out of memory I'm not happy about. I
think maybe have two constructors, the default one which assert fails on
out of meory conditions, another one which returns NULL. This is easily
implemented by having a flag in region.

Where are you seeing this condition? Humm... Well, if the current state of a
region cannot satisfy the requested allocation, it does indeed return NULL,
and no assertion is tripped. For instance, the following program with the
current region code as-is does not barf up an assertion failure:
______________________________________________________
int main(void) {
struct region region;
unsigned char buffer[128] = { '\0' };
rinit(&region, buffer, sizeof(buffer));
ralloc(&region, 10000);
return 0;
}
______________________________________________________




What am I missing?