Discussion:
Approach to create/use containers in C
Add Reply
Thiago Adams
2017-05-04 13:13:59 UTC
Reply
Permalink
Raw Message
I need to create many dynamic arrays and some maps in C for different types.

How do you deal with this problem?


1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?


2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE

3) Use a void* version of each container?

4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?

5) Define only DECLARE_ARRAY with inline functions

6) Create preprocessor to instantiate types/functions?

8) Create individual macros for each function (eg. ARRAY_PUSH)

9) Create individual macros using the generator?

10) Other?
Stefan Ram
2017-05-04 13:26:22 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Create preprocessor to instantiate types/functions?
It's called "Cfront". Release 3.0 includes templates.
Jerry Stuckle
2017-05-04 13:27:43 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
It depends on a lot of things. I've used void * and I've modified
generic code to create specific functions by hand.

I don't generally use the preprocessor to generate code because it can
be hard for others to understand. Unlike C++, which can have the same
function name with different parameter lists, C has to have unique
function names and the preprocessor can hide the functions. I also
haven't found a code generator which does well enough to satisfy me.

But nowadays if I need a lot of containers for different types, I'm more
likely to be writing C++ code and using the container template libraries.
--
==================
Remove the "x" from my email address
Jerry Stuckle
***@attglobal.net
==================
GOTHIER Nathan
2017-05-04 13:26:45 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:13:59 -0700 (PDT)
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Please give us more details about your problem because the devil is in the
details.

What kind of data are trying to map? Why do think you need dynamic arrays
to process them?
GOTHIER Nathan
2017-05-04 13:29:24 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:13:59 -0700 (PDT)
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Please give us more details about your problem because the devil is in the
details.

What kind of data are you trying to map? Why do you think you need dynamic arrays
to process them?
Thiago Adams
2017-05-04 13:40:32 UTC
Reply
Permalink
Raw Message
Post by GOTHIER Nathan
On Thu, 4 May 2017 06:13:59 -0700 (PDT)
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Please give us more details about your problem because the devil is in the
details.
What kind of data are you trying to map? Why do you think you need dynamic arrays
to process them?
In my C AST I need many dynamic arrays of different types.
Dynamic array of arguments, statements, declarations, declarators etc etc..
Maps of enum values , declarations etc..
GOTHIER Nathan
2017-05-04 13:49:26 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:40:32 -0700 (PDT)
Post by Thiago Adams
In my C AST I need many dynamic arrays of different types.
Dynamic array of arguments, statements, declarations, declarators etc etc..
Maps of enum values , declarations etc..
How would you resolve the problem without a computer? A basic approach is to
make a table to classify each kind of data.

Programming only automate human processes.
Stefan Ram
2017-05-04 13:57:18 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
In my C AST I need many dynamic arrays of different types.
Dynamic array of arguments, statements, declarations, declarators etc etc..
Maps of enum values , declarations etc..
I believe the usual approach is to use arrays of pointers to
structs. Pointers help to achieve some kind of polymorphism,
which often will be helpful. The arrays are created with malloc(
membercount * structptrsize ). So you do not need to make a
big fuss with one source file for each array type or some such.
bartc
2017-05-04 15:38:56 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Post by GOTHIER Nathan
What kind of data are you trying to map? Why do you think you need dynamic arrays
to process them?
In my C AST I need many dynamic arrays of different types.
Dynamic array of arguments, statements, declarations, declarators etc etc..
What do you mean by dynamic array?

It might be one whose size is fixed but is not known until runtime.

Or it might be an array which starts empty then grows as elements are added.

I don't use the latter pattern much in a static language. For your
examples, I would use a linked list, as it would be uncommon to need
random access to this data.

Or it may be possible to somehow determine the size of list needed, then
use the simpler fixed kind of dynamic array (which is just a pointer).
Post by Thiago Adams
Maps of enum values , declarations etc..
And what do you mean by a map? Turning a name into a value? In your
example app, wouldn't that be handled by a symbol table?
--
bartc
Thiago Adams
2017-05-04 16:59:22 UTC
Reply
Permalink
Raw Message
Post by bartc
Post by Thiago Adams
Post by GOTHIER Nathan
What kind of data are you trying to map? Why do you think you need dynamic arrays
to process them?
In my C AST I need many dynamic arrays of different types.
Dynamic array of arguments, statements, declarations, declarators etc etc..
What do you mean by dynamic array?
It might be one whose size is fixed but is not known until runtime.
Or it might be an array which starts empty then grows as elements are added.
I mean the second one. empty then grows.
Post by bartc
I don't use the latter pattern much in a static language. For your
examples, I would use a linked list, as it would be uncommon to need
random access to this data.
I think a linked list could be good. But it doesn't change the problem to manage macros and/or generated files. Does it?
Maybe single linked list with just a head pointer can simplify the problem, but I think I would have to use at least head and tail.
Post by bartc
Or it may be possible to somehow determine the size of list needed, then
use the simpler fixed kind of dynamic array (which is just a pointer).
Post by Thiago Adams
Maps of enum values , declarations etc..
And what do you mean by a map? Turning a name into a value? In your
example app, wouldn't that be handled by a symbol table?
Yes. What's is the data structure of symbol table?
I use map and "multimap". In multimap the same key can point for many items. Both use hash tables.
bartc
2017-05-04 17:45:37 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Post by bartc
I don't use the latter pattern much in a static language. For your
examples, I would use a linked list, as it would be uncommon to need
random access to this data.
I think a linked list could be good. But it doesn't change the problem to manage macros and/or generated files. Does it?
Maybe single linked list with just a head pointer can simplify the problem, but I think I would have to use at least head and tail.
A doubly linked list wouldn't be a big deal, just an extra pointer.

I use singly linked ones where possible, but with a pointer to head and
tail if it's necessary to grow in the right order (rather than in reverse).
Post by Thiago Adams
Post by bartc
And what do you mean by a map? Turning a name into a value? In your
example app, wouldn't that be handled by a symbol table?
Yes. What's is the data structure of symbol table?
I use map and "multimap". In multimap the same key can point for many items. Both use hash tables.
OK. I don't know what data structures people like to use for
hierarchical symbol tables. If coding in C, you want them to be
lightweight and efficient.

(I use a single global hash table to store one instance of each unique
identifier. That's what the tokeniser sees. The parser superimposes a
hierarchical structure, using sideways and up and down links. I guess
that isn't typical.)
--
bartc
Thiago Adams
2017-05-05 17:22:32 UTC
Reply
Permalink
Raw Message
Post by bartc
Post by Thiago Adams
Post by bartc
I don't use the latter pattern much in a static language. For your
examples, I would use a linked list, as it would be uncommon to need
random access to this data.
I think a linked list could be good. But it doesn't change the problem to manage macros and/or generated files. Does it?
Maybe single linked list with just a head pointer can simplify the problem, but I think I would have to use at least head and tail.
A doubly linked list wouldn't be a big deal, just an extra pointer.
For arrays, something that could simplify declaration is to add size and capacity (current size of array and total allocated size) inside the array at index [0] and [1].

Generally I use pointers to structs. Otherwise, for int, double etc,
read-to-include containers can be generated.

Type * pTypes = NULL;

Push(&pTypes, pType1);

pTypes is :
[size, capacity, pType1, ... pTypeN]

but pTypes points to p[2]

#define SizeOf(p) ((size_t)*(p - 2))
#define CapacityOf(p) ((size_t)*(p - 1))

for (int i = 0 ; p < SizeOf(pTypes); i++)
{
Type* pType = pTypes[i];
//...
}

I haven't tried this approach on real code.

Malcolm McLean
2017-05-04 13:33:12 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
void * with an element size member.

However C has difficulties with generic containers, which is why no library
has emerged as standard. For example every insert operation can potentially
cause an out of memory error, which the caller has to handle. Then you can
only make shallow copies of structures, which means caller needs to be
careful about putting structures with dynamic members into the container.
There's also no way of deep-destroying the contents.
GOTHIER Nathan
2017-05-04 13:40:27 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:33:12 -0700 (PDT)
Post by Malcolm McLean
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
void * with an element size member.
However C has difficulties with generic containers, which is why no library
has emerged as standard. For example every insert operation can potentially
cause an out of memory error, which the caller has to handle. Then you can
only make shallow copies of structures, which means caller needs to be
careful about putting structures with dynamic members into the container.
There's also no way of deep-destroying the contents.
Most of the time a short linked list is a bad solution because of the cost of
the overhead. I prefer by far to process data in a static buffer or in the
worst case with a resizable linked list to mitigate the overhead cost.
Thiago Adams
2017-05-04 13:54:05 UTC
Reply
Permalink
Raw Message
Post by GOTHIER Nathan
On Thu, 4 May 2017 06:33:12 -0700 (PDT)
Post by Malcolm McLean
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
void * with an element size member.
However C has difficulties with generic containers, which is why no library
has emerged as standard. For example every insert operation can potentially
cause an out of memory error, which the caller has to handle. Then you can
only make shallow copies of structures, which means caller needs to be
careful about putting structures with dynamic members into the container.
There's also no way of deep-destroying the contents.
Most of the time a short linked list is a bad solution because of the cost of
the overhead. I prefer by far to process data in a static buffer or in the
worst case with a resizable linked list to mitigate the overhead cost.
My question is more about how to manage the container creation, and not about the details of the container.
But of course, if some static array was enough, then the problem of manage container creation would disappear because C already have "generic static arrays".

Type1 a1[100];
Type2 a2[200];

If we try to broke the "implementation" of static arrays in small pieces
we don't get too much parts right?
But this is different for dynamic arrays.
If everyone was happy with one type of implementation then we could possible have "build in templates for arrays".

Type1 a1[auto];
Type2 a2[auto];

and push(a1, 1), pop(a1)
GOTHIER Nathan
2017-05-04 14:06:21 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:54:05 -0700 (PDT)
Post by Thiago Adams
My question is more about how to manage the container creation, and not about the details of the container.
But of course, if some static array was enough, then the problem of manage container creation would disappear because C already have "generic static arrays".
Type1 a1[100];
Type2 a2[200];
If we try to broke the "implementation" of static arrays in small pieces
we don't get too much parts right?
But this is different for dynamic arrays.
If everyone was happy with one type of implementation then we could possible have "build in templates for arrays".
Type1 a1[auto];
Type2 a2[auto];
and push(a1, 1), pop(a1)
I'm afraid you have to build some kind of database. :o)

Considering a database, I would put every piece of data (text) in a static
field one by row and I would write the type in a column.

It looks like a hard task because you currently don't have the good tools.
That's always the case when you're inventing new things.
Richard Heathfield
2017-05-04 14:46:18 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
I deal with it using a struct:

{
pcl_constructor *constructor;
pcl_destructor *destructor;
pcl_comparator *comparator;
pcl_executor *executor;
void *data; /* pointer to array data */
size_t size; /* size of one object */
size_t count; /* number of objects */
size_t capacity; /* current capacity, must be >= count */
size_t maxcap; /* maximum capacity */
};

The first four are pointers to functions for creating, destroying,
comparing, and "operating" objects within the array.

The next three (data, size, count) are obvious.

capacity is the number of items for which we have memory.

maxcap is a sanity limit. For example, if there can never be more than
1000 or so items in the array (perhaps they're countries), you might set
maxcap to perhaps double that - so if you hit that capacity, you know
something screwy is going on. If it's cities, though, you'd set the
limit a fair bit higher.

This all works very well.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Thiago Adams
2017-05-04 14:50:40 UTC
Reply
Permalink
Raw Message
Post by Richard Heathfield
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
{
pcl_constructor *constructor;
pcl_destructor *destructor;
pcl_comparator *comparator;
pcl_executor *executor;
void *data; /* pointer to array data */
size_t size; /* size of one object */
size_t count; /* number of objects */
size_t capacity; /* current capacity, must be >= count */
size_t maxcap; /* maximum capacity */
};
The first four are pointers to functions for creating, destroying,
comparing, and "operating" objects within the array.
The next three (data, size, count) are obvious.
capacity is the number of items for which we have memory.
maxcap is a sanity limit. For example, if there can never be more than
1000 or so items in the array (perhaps they're countries), you might set
maxcap to perhaps double that - so if you hit that capacity, you know
something screwy is going on. If it's cities, though, you'd set the
limit a fair bit higher.
This all works very well.
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
Richard Heathfield
2017-05-04 15:10:42 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Post by Richard Heathfield
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
{
pcl_constructor *constructor;
pcl_destructor *destructor;
pcl_comparator *comparator;
pcl_executor *executor;
void *data; /* pointer to array data */
size_t size; /* size of one object */
size_t count; /* number of objects */
size_t capacity; /* current capacity, must be >= count */
size_t maxcap; /* maximum capacity */
};
The first four are pointers to functions for creating, destroying,
comparing, and "operating" objects within the array.
The next three (data, size, count) are obvious.
capacity is the number of items for which we have memory.
maxcap is a sanity limit. For example, if there can never be more than
1000 or so items in the array (perhaps they're countries), you might set
maxcap to perhaps double that - so if you hit that capacity, you know
something screwy is going on. If it's cities, though, you'd set the
limit a fair bit higher.
This all works very well.
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
Every solution has good points and bad points. I like this solution
because it's easy to implement, easy to maintain, easy to read, easy to
extend, and doesn't require bizarre macros.

I generally defer worrying about performance until the point where
performance becomes a problem. So far, it hasn't.

As for type checking, well, you're right - it would certainly be
possible to screw up on the application side. But errors would show up
pretty fast, and it would be pretty obvious what they were. It's not
something that has caused me a problem.

If I felt I needed very strong type checking, C would probably not be my
language of choice!
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Malcolm McLean
2017-05-04 15:18:19 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch. In Javascript you don't have it, because "duck typing" is easier
for the interpreter to implement. And a bug that involves reinterpreting bits
as the wrong type will usually come out very early.

As for performance, as long as you allow null pointers for the constructor and
destructor, there is essentially no overhead for simple types that don't
need constructing and destroying.
Thiago Adams
2017-05-04 16:48:43 UTC
Reply
Permalink
Raw Message
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch. In Javascript you don't have it, because "duck typing" is easier
for the interpreter to implement. And a bug that involves reinterpreting bits
as the wrong type will usually come out very early.
In one javascript project I worked, it took 6 months to find all bugs
caused by a refactoring.
Richard Heathfield
2017-05-04 16:55:09 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch. In Javascript you don't have it, because "duck typing" is easier
for the interpreter to implement. And a bug that involves reinterpreting bits
as the wrong type will usually come out very early.
In one javascript project I worked, it took 6 months to find all bugs
caused by a refactoring.
Or perhaps /revealed/ by a refactoring.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
Ike Naar
2017-05-04 22:04:13 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
In one javascript project I worked, it took 6 months to find all bugs
caused by a refactoring.
How about the ones you haven't found yet?
Ben Bacarisse
2017-05-04 19:03:06 UTC
Reply
Permalink
Raw Message
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch.
That's very much a C (and C-like) language perspective. Even for some
relatively natural type systems, type checking can be undecidable and it
is often NP-complete. But you are right that it is often made easy to
check.

Of course that's, in part, what makes it something that is over fussed
about in that the fuss is more justifiable, the less easy the
type-checking is. At the far end of that spectrum would be a type
system in which type-checking the program is equivalent to proving the
program semantically correct.
Post by Malcolm McLean
In Javascript you don't have it, because "duck typing" is easier
for the interpreter to implement. And a bug that involves reinterpreting bits
as the wrong type will usually come out very early.
JavaScript (AKA EcmaScript) does have type checking -- just very little
of it.

<snip>
--
Ben.
Thiago Adams
2017-05-04 19:25:35 UTC
Reply
Permalink
Raw Message
Post by Ben Bacarisse
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch.
That's very much a C (and C-like) language perspective. Even for some
relatively natural type systems, type checking can be undecidable and it
is often NP-complete. But you are right that it is often made easy to
check.
Of course that's, in part, what makes it something that is over fussed
about in that the fuss is more justifiable, the less easy the
type-checking is. At the far end of that spectrum would be a type
system in which type-checking the program is equivalent to proving the
program semantically correct.
When I know that the compiler will not check type for me,
for instance a cast, I create a "cast" macro.
For instance:

#define Type1_As_Type2(p) ((Type2*)p)

Then let's say Type2 cannot be converted to Type1 anymore.
I just delete the macro and the compiler will show where the
cast is not allowed anymore because it will not find the macro.
Robert Wessel
2017-05-04 20:03:27 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 12:25:35 -0700 (PDT), Thiago Adams
Post by Thiago Adams
Post by Ben Bacarisse
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch.
That's very much a C (and C-like) language perspective. Even for some
relatively natural type systems, type checking can be undecidable and it
is often NP-complete. But you are right that it is often made easy to
check.
Of course that's, in part, what makes it something that is over fussed
about in that the fuss is more justifiable, the less easy the
type-checking is. At the far end of that spectrum would be a type
system in which type-checking the program is equivalent to proving the
program semantically correct.
When I know that the compiler will not check type for me,
for instance a cast, I create a "cast" macro.
#define Type1_As_Type2(p) ((Type2*)p)
Then let's say Type2 cannot be converted to Type1 anymore.
I just delete the macro and the compiler will show where the
cast is not allowed anymore because it will not find the macro.
Would not turning that into a "cast function" be even better:

inline static Type2* Type1_As_Type2(Type1 *p)
{
return ((Type2*)p);
}

You still get the compiler to warn you when the conversion is deleted,
plus you get it to type check the source parameter. And any compiler
should inline and no-op that (assuming the pointer formats are, as is
common, compatible).
Thiago Adams
2017-05-04 20:09:57 UTC
Reply
Permalink
Raw Message
Post by Robert Wessel
On Thu, 4 May 2017 12:25:35 -0700 (PDT), Thiago Adams
Post by Thiago Adams
Post by Ben Bacarisse
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch.
That's very much a C (and C-like) language perspective. Even for some
relatively natural type systems, type checking can be undecidable and it
is often NP-complete. But you are right that it is often made easy to
check.
Of course that's, in part, what makes it something that is over fussed
about in that the fuss is more justifiable, the less easy the
type-checking is. At the far end of that spectrum would be a type
system in which type-checking the program is equivalent to proving the
program semantically correct.
When I know that the compiler will not check type for me,
for instance a cast, I create a "cast" macro.
#define Type1_As_Type2(p) ((Type2*)p)
Then let's say Type2 cannot be converted to Type1 anymore.
I just delete the macro and the compiler will show where the
cast is not allowed anymore because it will not find the macro.
inline static Type2* Type1_As_Type2(Type1 *p)
{
return ((Type2*)p);
}
You still get the compiler to warn you when the conversion is deleted,
plus you get it to type check the source parameter. And any compiler
should inline and no-op that (assuming the pointer formats are, as is
common, compatible).
Actually, I do this way also :D
I agree that is better.
Sometimes this method requires a forward declaration because it uses compiler.


For type safety, the C language can be improved a lot without to change any line from the standard. Just using static analysis.
Tim Rentsch
2017-05-05 08:34:32 UTC
Reply
Permalink
Raw Message
Post by Malcolm McLean
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
You can't type check, but people make far too much fuss about "type safety",
because it happens to be a programming error that is easy for the compiler
to catch. [...]
That is a remarkably naive viewpoint.
GOTHIER Nathan
2017-05-04 15:17:43 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 07:50:40 -0700 (PDT)
Post by Thiago Adams
I think the bad point of this solution is performance because
it is more dynamic. Also less type check.
Once more a C approach wouldn't put any constructor/destructor pointers in a
structure without a good reason to do so, which I don't see in the previous
example if not to mimic a C++ pattern.

I would rather build a machinery to process with static field such as:

#define DATAFIELD_MAX 255

struct row
{
void *prevrow;
void *nextrow;
int freechar;
char datafield[DATAFIELD_MAX];
int datatype;
};

struct table
{
int nrow;
struct *rowp;
};

struct table *insert(struct table *tab, char *data, size_t size);
struct table *remove(struct table *tab, char *data, size_t size);
int gettype(struct table *tab, char *data, size_t size);
char *getdata(struct table *tab, int type);
Ben Bacarisse
2017-05-04 18:36:39 UTC
Reply
Permalink
Raw Message
Post by Richard Heathfield
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
{
pcl_constructor *constructor;
pcl_destructor *destructor;
pcl_comparator *comparator;
pcl_executor *executor;
void *data; /* pointer to array data */
size_t size; /* size of one object */
size_t count; /* number of objects */
size_t capacity; /* current capacity, must be >= count */
size_t maxcap; /* maximum capacity */
};
A slight variation is to have the four functions and the size in a
separate struct, a pointer to which is shared between instances.

The down-side is that you must manage this shared data but that is often
very simple. For example, in some programs you can just statically
declare a fixed number of these "class" structs.

I would probably try to put all the operations into either and array or
a flexible array member. The last time I did this (as with all my
coding these days, it was a toy program) all of the operations had the
same type:

typedef void Method(struct Object *this, ...);

and the constructor was method 0, the destructor method 1 and so on.

<snip>
--
Ben.
Robert Wessel
2017-05-04 17:09:39 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 06:13:59 -0700 (PDT), Thiago Adams
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
look at some of his code:

https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
Robert Wessel
2017-05-04 17:17:45 UTC
Reply
Permalink
Raw Message
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
Post by Robert Wessel
On Thu, 4 May 2017 06:13:59 -0700 (PDT), Thiago Adams
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
Sorry, better link:

https://code.google.com/archive/p/ccl/
Thiago Adams
2017-05-04 17:30:33 UTC
Reply
Permalink
Raw Message
Post by Robert Wessel
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
Post by Robert Wessel
On Thu, 4 May 2017 06:13:59 -0700 (PDT), Thiago Adams
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
3) Use a void* version of each container?
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
https://code.google.com/archive/p/ccl/
I guess the Jacob Navia approach is the "dynamic" approach
using function pointers.
The bad point is performance.

For performance considerations, memory consumption
and program size we need to compare with the container made by hand or generator.
Ian Collins
2017-05-04 19:50:52 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
Post by Robert Wessel
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
Post by Robert Wessel
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
https://code.google.com/archive/p/ccl/
I guess the Jacob Navia approach is the "dynamic" approach
using function pointers.
The bad point is performance.
In most testing I have seen or done, it performs well.
--
Ian
Keith Thompson
2017-05-04 18:29:58 UTC
Reply
Permalink
Raw Message
Post by Robert Wessel
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
[...]
Post by Robert Wessel
Post by Robert Wessel
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
https://code.google.com/archive/p/ccl/
The code.google.com service was shut down in 2016. The project is still
available there, but I hope that jacob moves or copies it to a more
permanent location.
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Andreas Perstinger
2017-05-04 18:34:40 UTC
Reply
Permalink
Raw Message
Post by Robert Wessel
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
Post by Robert Wessel
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
https://code.google.com/archive/p/ccl/
The link to the Google Code Archive is dead.

It looks like Jacob moved the CCL to GitHub:

https://github.com/jacob-navia/ccl

Bye, Andreas
Robert Wessel
2017-05-04 20:07:47 UTC
Reply
Permalink
Raw Message
On Thu, 4 May 2017 18:34:40 -0000 (UTC), Andreas Perstinger
Post by Andreas Perstinger
Post by Robert Wessel
On Thu, 04 May 2017 12:09:39 -0500, Robert Wessel
Post by Robert Wessel
Jacob Navia has implemented a C container library, which does many of
the same things as the C++ STL. It may be worth at least taking a
https://www.cs.virginia.edu/~lcc-win32/ccl/ccl.html
https://code.google.com/archive/p/ccl/
The link to the Google Code Archive is dead.
https://github.com/jacob-navia/ccl
I actually knew Google Code was dead, but had pretty much forgotten,
and didn't look too closely at the actual link (the "archive" should
have been a tip-off). In any event, a link from what (I think) is
Jacob's main page for these things led me to the one I posted. He may
need to update that.

https://www.cs.virginia.edu/~lcc-win32/
Doug Weiman
2017-05-04 21:19:12 UTC
Reply
Permalink
Raw Message
What can containers do that processes cannot do, anyway?
Keith Thompson
2017-05-04 21:41:34 UTC
Reply
Permalink
Raw Message
Post by Doug Weiman
What can containers do that processes cannot do, anyway?
Containers and processes are entirely different things. (Perhaps
you're thinking of a different kind of "container"?)

https://en.wikipedia.org/wiki/Container_(abstract_data_type)
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Doug Weiman
2017-05-04 22:30:01 UTC
Reply
Permalink
Raw Message
Post by Doug Weiman
What can containers do that processes cannot do, anyway?
Containers and processes are entirely different things. (Perhaps you're
thinking of a different kind of "container"?)
https://en.wikipedia.org/wiki/Container_(abstract_data_type)
Yes; my mistake.
A. Bolmarcich
2017-05-04 21:47:09 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
[snip]

When I did it years ago, I used an approach like

#define ARRAY_TYPE MYTYPE
#include "ARRAY.h"
#udef ARRAY_TYPE

I used a single include file instead of separate DECLARE_ARRAY and
IMPLEMENT_ARRAY files. A #define before the #include controlled
whether the include file was to produce declarations or definitions.

The containers held structs rather than individual variables. Memory
management of those structs was the responsibility of the program that
used the container.

One of the elements of that struct was of a type with a name like
ARRAY_LINK. The typename was a struct declared by the include file.

The generated functions accessed only the elements of ARRAY_LINK.
The generated functions were usually short. By default, they were
defined as static so that optimizing compilers could inline calls to
the generated function or generate function call code that was compact.

The generated functions were type-specific to the struct held in a
container.
luser droog
2017-05-05 07:43:52 UTC
Reply
Permalink
Raw Message
Post by Thiago Adams
I need to create many dynamic arrays and some maps in C for different types.
How do you deal with this problem?
1) Create a new file for each type with an generator or by hand?
Remove manually some not used functions?
Keep then in a generated folder?
My APL interpreter does it a somewhat-unique way which amounts
to very little code to add new types. I've explained this a few
times before so a search may turn up more (or at least varied)
details.

The crux is two basic mappings involved in a container like an
array. This may sound complicated by saying something like that
up front, but if you'll bear with me it may seem less unappealing
later on.

The first mapping I call "encoding". All the various types are
mapped into a few bits masked over the top of an 'int'. So 'int'
or 'typedef int object;' becomes an "atomic" representation of
an object.

Then the various containers just contain 'int' as the payload.
All data elements have a (small and) uniform size.

There may be a "performance" hit since all the real "data" is
doubly-indirected. So adding two float "objects" encoded in this
way involves 2 array lookups and a pointer dereference to yield
each float, and a malloc (and possible realloc) to create a new
object for the result.

But adding a new type is now trivial, and all containers
automatically work for the new type.
Post by Thiago Adams
2) Use define - include - undef?
#define TYPE MYTYPE
#include "Array.h"
#undef TYPE
I love love love X-Macros, but do it this way:

http://stackoverflow.com/questions/6635851/real-world-use-of-x-macros/6636596#6636596
Post by Thiago Adams
3) Use a void* version of each container?
I use 'int', but supposedly you could use void*. I find too many
of those on the screen makes me dizzy.
Post by Thiago Adams
4) Define a macro DECLARE_ARRAY and IMPLEMENT_ARRAY?
5) Define only DECLARE_ARRAY with inline functions
That sort of thing isn't necessary with the extra Encoding
step I'm advertising. It allows heterogeneous arrays.
An array of 3 ints is created the same way as an array of
3 floats.

array x = array_new_dims(3);
Post by Thiago Adams
6) Create preprocessor to instantiate types/functions?
8) Create individual macros for each function (eg. ARRAY_PUSH)
9) Create individual macros using the generator?
10) Other?
I think my approach falls under Other. Avoid too many macros.

I've written about various pieces of this design with code
on these pages:

https://codereview.stackexchange.com/questions/140994/encoding-data-into-integer-handles-for-language-interpreter

https://codereview.stackexchange.com/questions/122038/arbitrary-dimensional-arrays-with-transpose-and-slice

https://codereview.stackexchange.com/questions/114243/unicode-capable-symbol-table-n-way-search-tree-with-hash-buckets
Loading...