Container Interfaces

[jacob navia]

When building a software project, one of the many pitfalls you can
encounter is releasing the software too early. When released, software
gets used, and the way it is designed gets frozen for fears of not being
backwards compatible and leaving the few users with a lot of work of
changing their code.

Luckily, I haven't released any code for my container library, so I can
rewrite completely the way it presents itself to the user without any
problems.

I did just that.

I decided to

(1) Hide all definitions of the data types used, leaving abstract data
types instead:

typedef struct List List;

(2) leave only a public list of functions in a single object:

typedef struct tagListInterface {
List *Create(size_t elementSize);
// .. many other functions
} ListInterface;

(3) Declare as extern a single global object that is the ONLY exported
name from all the interface:

extern ListInterface iList;
extern HastTableInterface iHashTable;

etc.

(4)

All user code now uses the global interface, what makes disappear that
horrible:

list_object->VTable->Find(list_object, data);

replacing it with the much simpler:

iList.Find(list_object,data);

(5)
This way of interfacing containers has the added advantage that the
creation function can be replaced by your own one, without having the
need to instantiate an object to be able to get it.

(6)
The impact in the linker symbol table is reduced to just ONE symbol for
each container.

----------------------------------------------------------------------

As an example of how this looks like, here is an example of a container
that I added recently: Bloom filters. This filters apply several times
hash functions to a datum, and the hash result index a bitstring,
setting each bit n times to 1. More can be found in the wikipedia.

Here is the header file


typedef struct tagBloomFilter BloomFilter;
typedef struct tagBloomFilterInterface {
BloomFilter *(*Create)(size_t MaxElements,double probability);
size_t (*SetElement)(BloomFilter *b,
const void *key,size_t keylen);
int (*GetElement)(BloomFilter *b,const void *key,size_t keylen);
int (*Clear)(BloomFilter *b);
int (*Finalize)(BloomFilter *b);
} BloomFilterInterface;
extern BloomFilterInterface iBloomFilter;



Here is the implementation

/*
The bloom filter uses k hash functions to store k bits in a bit string
that represent a stored value. It can return false positives, but if it
says that an element is NOT there, it is definitely not there.

The size of the bloom filter and the number of hash functions you should
be using depending on your application can be calculated using the
formulas on the Wikipedia page:

m = -n*ln(p)/(ln(2)^2)

This will tell you the number of bits m to use for your filter, given
the number n of elements in your filter and the false positive
probability p you want to achieve. All that for the ideal number of hash
functions k which you can calculate like this:

k = 0.7*m/n

*/
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "containers.h"
struct tagBloomFilter {
size_t count; // Elements stored already
size_t MaxNbOfElements;
double Probability;
size_t HashFunctions;
size_t nbOfBits;
unsigned char *bits;
unsigned Seeds[1];
ContainerMemoryManager *Allocator;
};

//-----------------------------------------------------------------------------
// MurmurHash2, by Austin Appleby
// Note - This code makes a few assumptions about how your machine behaves -
// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4
// And it has a few limitations -
// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
// machines.
static unsigned int Hash(const void * key, int len, unsigned int seed )
{
// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.

const unsigned int m = 0x5bd1e995;
const int r = 24;
// Initialize the hash to a 'random' value
unsigned int h = seed ^ len;
// Mix 4 bytes at a time into the hash
const unsigned char * data = (const unsigned char *)key;
while(len >= 4)
{
unsigned int k = *(unsigned int *)data;

k *= m;
k ^= k >> r;
k *= m;

h *= m;
h ^= k;

data += 4; len -= 4;
}
// Handle the last few bytes of the input array
switch(len)
{
case 3: h ^= data[2] << 16;
case 2: h ^= data[1] << 8;
case 1: h ^= data[0];
h *= m;
};
// Do a few final mixes of the hash to ensure the last few
// bytes are well-incorporated.
h ^= h >> 13; h *= m; h ^= h >> 15;
return h;
}
static BloomFilter *Create(size_t nbOfElements,double Probability)
{
int nbOfBits;
int k;
BloomFilter *result;

if (Probability >= 1.0) {
iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_BADARG);
return NULL;
}
nbOfBits = -round(nbOfElements*log(Probability)/(log(2.0)*log(2.0)));
k = round(0.7*nbOfBits/nbOfElements);
result = CurrentMemoryManager->malloc(sizeof(BloomFilter) + k*sizeof(int));
if (result == NULL) {
iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_NOMEMORY);
return NULL;
}
result->bits = CurrentMemoryManager->malloc(1+nbOfBits/8);
if (result->bits == NULL) {
CurrentMemoryManager->free(result);
iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_NOMEMORY);
return NULL;
}
result->nbOfBits = nbOfBits;
result->MaxNbOfElements = nbOfElements;
result->Probability = Probability;
result->HashFunctions = k;
while (k > 0) {
k--;
result->Seeds[k] = rand();

}
result->Allocator = CurrentMemoryManager;
return result;
}

static size_t Add(BloomFilter *b, const void *key, size_t keylen)
{
unsigned hash;
int i;

for (i=0; i<b->HashFunctions;i++) {
hash = Hash(key,keylen,b->Seeds);
hash %= b->nbOfBits;
b->bits[hash >> 3] |= 1 << (hash&7);
}
return ++b->count;
}

static int GetElement(BloomFilter *b, const void *key, size_t keylen)
{
unsigned hash;
int i;

for (i=0; i<b->HashFunctions;i++) {
hash = Hash(key,keylen,b->Seeds);
hash %= b->nbOfBits;
if ((b->bits[hash >> 3] & (1 << (hash&7))) == 0)
return 0;
}
return 1;
}

static int Clear(BloomFilter *b)
{
memset(b->bits,0,1+b->nbOfBits/8);
return 1;
}

static int Finalize(BloomFilter *b)
{
b->Allocator->free(b->bits);
b->Allocator->free(b);
return 1;

}

BloomFilterInterface iBloomFilter = {
Create,
Add,
GetElement,
Clear,
Finalize,
};

#ifdef TEST
int main(void)
{
BloomFilter *b = iBloomFilter.Create(10,0.00001);
int i,errors=0;
i = 4734;
iBloomFilter.SetElement(b,&i,sizeof(int));
i = 9457;
iBloomFilter.SetElement(b,&i,sizeof(int));
i = 458223;
iBloomFilter.SetElement(b,&i,sizeof(int));
i = 40774;
iBloomFilter.SetElement(b,&i,sizeof(int));
i = 9334422;
iBloomFilter.SetElement(b,&i,sizeof(int));
i = 9334422;
if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
printf("9334422 found as it should\n");
}
else printf("9334422 not found and is present\n");
i = 4734;
if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
printf("4734 found as it should\n");
}
else {
printf("4734 not found and is present\n");
errors++;
}
i = 9;
if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
printf("9 found as it should not\n");
errors++;
}
else printf("9 not found and is not present\n");
iBloomFilter.Finalize(b);
return errors;
}
#endif

 

[Ersek, Laszlo]

I feel obligated to fulfill my role as the ever-tangential smart-ass.

static unsigned int Hash(const void * key, int len, unsigned int seed )

const unsigned char * data = (const unsigned char *)key;

unsigned int k = *(unsigned int *)data;

That may be an unaligned (undefined) pointer conversion, or an unaligned
acces through the converted pointer. Fixable with memcpy(). That in turn
may result in a trap representation. Fixable (I hope!) with an exact-width
unsigned integer type. (There are pre-C99 standards requiring them. Once
you hit the wire, you can't remain platform-independent. See in_addr_t and
in_port_t in <netinet/in.h> in the SUSv1 XNS (C438), for example.)

Or just use manual << and bitor. (Thanks for the opportunity to use the
word "bitor" in public.)

(I'm operating under the notion that you're writing a portable library.)

G'night,
lacos

 

[jacob navia]

Ersek, Laszlo a écrit :

I feel obligated to fulfill my role as the ever-tangential smart-ass.





That may be an unaligned (undefined) pointer conversion, or an unaligned
acces through the converted pointer. Fixable with memcpy(). That in turn
may result in a trap representation. Fixable (I hope!) with an
exact-width unsigned integer type. (There are pre-C99 standards
requiring them. Once you hit the wire, you can't remain
platform-independent. See in_addr_t and in_port_t in <netinet/in.h> in
the SUSv1 XNS (C438), for example.)

That could be done, yes. Another way would be to see if the address
starts at an odd byte not multiple of sizeof(unsigned), and treat the
preceding bytes exactly like the trailing bytes that are handled with a
special case switch at the end.

Or just use manual << and bitor. (Thanks for the opportunity to use the
word "bitor" in public.)

You are welcome.

(I'm operating under the notion that you're writing a portable library.)

Yes, that's the goal. But since now all implementation issues are
completely separated from the interface descriptions, they can be
completely different for each implementation in each machine/system
without affecting the portability of the interface, that is the real
portable proposal.

G'night,
lacos

Thanks for your input.

 

[ImpalerCore]

When building a software project, one of the many pitfalls you can
encounter is releasing the software too early. When released, software
gets used, and the way it is designed gets frozen for fears of not being
backwards compatible and leaving the few users with a lot of work of
changing their code.

It's a double-edged sword. Releasing the code gives you access to
user feedback and testing that can be used to refine or redesign the
source, but at the same time not releasing the code until you're ready
is a good idea. You could just prefix your release with "alpha" to
test the waters, and most people will understand that the interface is
still in fluid form. Then you can see if most users like the
direction you're going, or if you should go back to the drawing board.

Luckily, I haven't released any code for my container library, so I can
rewrite completely the way it presents itself to the user without any
problems.

I did just that.

I decided to

(1) Hide all definitions of the data types used, leaving abstract data
types instead:

typedef struct List List;

Yeah, I've come to that conclusion as well, plus I have a personal
distaste for writing 'struct type' everywhere; I'm probably spoiled
from C++ I suppose. Now you need to decide on whether a prefix is
needed to differentiate your library from others. There's some risk
of overlap for 'List', but less so for 'JList' or 'JNList'. Just
don't take 'GList' ;-)

(2) leave only a public list of functions in a single object:

typedef struct tagListInterface {
        List *Create(size_t elementSize);
        // .. many other functions

} ListInterface;

I don't have enough experience to know whether or not I like/dislike
it.

(3) Declare as extern a single global object that is the ONLY exported
name from all the interface:

extern ListInterface iList;
extern HastTableInterface iHashTable;

etc.

Same as 2.

(4)

All user code now uses the global interface, what makes disappear that
horrible:

  list_object->VTable->Find(list_object, data);

replacing it with the much simpler:

  iList.Find(list_object,data);

A vast improvement in style imo. The only question is if you will
package the type casting in a macro or let the user provide it. Both
have merits, but I prefer wrapping the type in a macro.

\code snippet
#define list_find( list, object, type ) \
( (type*)(iList.Find( (list), (object) )) )

int find_me = 33;
int i_p* = NULL;

i_p = (int*)iList.Find( list, &find_me );

or

i_p = list_find( list, &find_me, int );

if ( i_p ) {
printf( "Found %d.\n", *i_p );
}
\endcode

(5)
This way of interfacing containers has the added advantage that the
creation function can be replaced by your own one, without having the
need to instantiate an object to be able to get it.

I'm guessing the main reason is to provide your own memory management
under the hood (malloc, static array, GC, etc.)?

(6)
The impact in the linker symbol table is reduced to just ONE symbol for
each container.

Same as 2.

----------------------------------------------------------------------

As an example of how this looks like, here is an example of a container
that I added recently: Bloom filters. This filters apply several times
hash functions to a datum, and the hash result index a bitstring,
setting each bit n times to 1. More can be found in the wikipedia.

Here is the header file

typedef struct tagBloomFilter BloomFilter;
typedef struct tagBloomFilterInterface {
        BloomFilter *(*Create)(size_t MaxElements,double probability);
        size_t (*SetElement)(BloomFilter *b,
                              const void *key,size_t keylen);
        int (*GetElement)(BloomFilter *b,const void *key,size_t keylen);
        int (*Clear)(BloomFilter *b);
        int (*Finalize)(BloomFilter *b);} BloomFilterInterface;

extern BloomFilterInterface iBloomFilter;

Here is the implementation

/*
The bloom filter uses k hash functions to store k bits in a bit string
that represent a stored value. It can return false positives, but if it
says that an element is NOT there, it is definitely not there.

The size of the bloom filter and the number of hash functions you should
be using depending on your application can be calculated using the
formulas on the Wikipedia page:

m = -n*ln(p)/(ln(2)^2)

This will tell you the number of bits m to use for your filter, given
the number n of elements in your filter and the false positive
probability p you want to achieve. All that for the ideal number of hash
functions k which you can calculate like this:

k = 0.7*m/n

*/
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "containers.h"
struct tagBloomFilter {
        size_t count; // Elements stored already
        size_t MaxNbOfElements;
        double Probability;
        size_t HashFunctions;
        size_t nbOfBits;
        unsigned char *bits;
        unsigned Seeds[1];
        ContainerMemoryManager *Allocator;

};

//-----------------------------------------------------------------------------
// MurmurHash2, by Austin Appleby
// Note - This code makes a few assumptions about how your machine behaves -
// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4
// And it has a few limitations -
// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
//    machines.
static unsigned int Hash(const void * key, int len, unsigned int seed )
{
        // 'm' and 'r' are mixing constants generated offline.
        // They're not really 'magic', they just happen to work well.

        const unsigned int m = 0x5bd1e995;
        const int r = 24;
        // Initialize the hash to a 'random' value
        unsigned int h = seed ^ len;
        // Mix 4 bytes at a time into the hash
        const unsigned char * data = (const unsigned char *)key;
        while(len >= 4)
        {
                unsigned int k = *(unsigned int *)data;

                k *= m;
                k ^= k >> r;
                k *= m;

                h *= m;
                h ^= k;

                data += 4;      len -= 4;
        }
        // Handle the last few bytes of the input array
        switch(len)
        {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0];
                h *= m;
        };
        // Do a few final mixes of the hash to ensure the last few
        // bytes are well-incorporated.
        h ^= h >> 13;     h *= m; h ^= h >> 15;
        return h;}

static BloomFilter *Create(size_t nbOfElements,double Probability)
{
        int nbOfBits;
        int k;
        BloomFilter *result;

        if (Probability >= 1.0) {
                iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_BADARG);
                return NULL;
        }
        nbOfBits = -round(nbOfElements*log(Probability)/(log(2.0)*log(2.0)));
        k = round(0.7*nbOfBits/nbOfElements);
        result = CurrentMemoryManager->malloc(sizeof(BloomFilter) + k*sizeof(int));
        if (result == NULL) {
                iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_NOMEMORY);
                return NULL;
        }
        result->bits = CurrentMemoryManager->malloc(1+nbOfBits/8);
        if (result->bits == NULL) {
                CurrentMemoryManager->free(result);
                iError.RaiseError("BloomFilter.Create",CONTAINER_ERROR_NOMEMORY);
                return NULL;
        }
        result->nbOfBits = nbOfBits;
        result->MaxNbOfElements = nbOfElements;
        result->Probability = Probability;
        result->HashFunctions = k;
        while (k > 0) {
                k--;
                result->Seeds[k] = rand();

        }
        result->Allocator = CurrentMemoryManager;
        return result;

}

static size_t Add(BloomFilter *b, const void *key, size_t keylen)
{
        unsigned hash;
        int i;

        for (i=0; i<b->HashFunctions;i++) {
                hash = Hash(key,keylen,b->Seeds);
                hash %= b->nbOfBits;
                b->bits[hash >> 3] |= 1 << (hash&7);
        }
        return ++b->count;

}

static int GetElement(BloomFilter *b, const void *key, size_t keylen)
{
        unsigned hash;
        int i;

        for (i=0; i<b->HashFunctions;i++) {
                hash = Hash(key,keylen,b->Seeds);
                hash %= b->nbOfBits;
                if ((b->bits[hash >> 3] & (1 << (hash&7))) == 0)
                        return 0;
        }
        return 1;

}

static int Clear(BloomFilter *b)
{
        memset(b->bits,0,1+b->nbOfBits/8);
        return 1;

}

static int Finalize(BloomFilter *b)
{
        b->Allocator->free(b->bits);
        b->Allocator->free(b);
        return 1;

}

BloomFilterInterface iBloomFilter = {
Create,
Add,
GetElement,
Clear,
Finalize,

};

#ifdef TEST
int main(void)
{
        BloomFilter *b = iBloomFilter.Create(10,0.00001);
        int i,errors=0;
        i = 4734;
        iBloomFilter.SetElement(b,&i,sizeof(int));
        i = 9457;
        iBloomFilter.SetElement(b,&i,sizeof(int));
        i = 458223;
        iBloomFilter.SetElement(b,&i,sizeof(int));
        i = 40774;
        iBloomFilter.SetElement(b,&i,sizeof(int));
        i = 9334422;
        iBloomFilter.SetElement(b,&i,sizeof(int));
        i = 9334422;
        if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
                printf("9334422 found as it should\n");
        }
        else printf("9334422 not found and is present\n");
        i = 4734;
        if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
                printf("4734 found as it should\n");
        }
        else {
                printf("4734 not found and is present\n");
                errors++;
        }
        i = 9;
        if (iBloomFilter.GetElement(b,&i,sizeof(int))) {
                printf("9 found as it should not\n");
                errors++;
        }
        else printf("9 not found and is not present\n");
        iBloomFilter.Finalize(b);
        return errors;}

#endif

I noticed that your interface has a lot of 'sizeof(int)' to pass the
size to the interface. There is a couple different 'styles' that you
can try out.

1. Instead of writing 'sizeof(int)' everywhere, consider making a
macro that takes the type 'int' and calls the appropriate interface
function with 'sizeof(int)'. You can also package the casting into
the macro so the user doesn't have to add his own casts. I mentioned
this before, but I'm just reiterating it here in this context.

\code snippet
#define bloom_filter_get_element( bloom, data, type ) \
( (type*)(iBloomFilter.GetElement( (bloom), (data) ,
sizeof(type) )) )

i = 4734;
if ( bloom_filter_get_element( bf, &i, int ) ) {
printf("4734 found as it should\n");
}
else {
printf("4734 not found and is present\n");
errors++;
}
\endcode

It saves a few keystrokes, and imo it more clearly documents that this
operation is dealing with a container that uses integers. You may or
may not like it, but it's what I do.

2. The creation of container is the best place to define the type of
object it contains.

This means that when you create a container, you should know from the
get go that it is a BloomFilter of 'integers'. Your example above
creates a BloomFilter of something.

BloomFilter *b = iBloomFilter.Create(10,0.00001);

I think the fact that no type is used makes it more difficult to
maintain this code. Imo, this is the best location to define what
kind of object the container uses. To accommodate it, the 'Create'
method will need an element size. You could then wrap the 'Create'
method with a macro to allow the user to pass the type as an argument
to bloom filter creation.

\code snippet
static BloomFilter *Create(size_t nbOfElements, double Probability,
size_t type_sz)
{
...
}

#define bloom_filter_create( n_elem, prob, type ) \
(iBloomFilter.Create( (n_elem), (prob) , sizeof(type) ))

BloomFilter *b = bloom_filter_create( 10, 0.00001, int );
\endcode

For containers where the data is not distributed (like linked lists
and trees), storing the element size within the container can simplify
the interface. For example, if BloomFilter has an 'ElementSize'
member, your SetElement no longer requires 'sizeof(int)' to insert an
integer.

\code snippet
/* Uses b->ElementSize implicitly */
iBloomFilter.SetElement(b,&i);
\endcode

3. Provide a modicum of type checking to your container.

One of the main problems with containers using void* is the lack of
type validation, and determining if user code has a type mismatch can
be very difficult. I know you already know this, but consider what
happens if you decide to store ElementSize within BloomFilter, and
require 'sizeof(type)' to be passed to the interface.

\code snippet
void BloomFilter_SetElement( BloomFilter* b, void* data, size_t
type_sz )
{
assert( b->ElementSize == type_sz );
...
}
\endcode

Provided that your iBloomFilter.Create stores the element size of the
container, requiring the user to provide the size when using
'SetElement' gives you a little bit of type checking that will be
flagged if the user makes a gross type mismatch. This again can be
wrapped in a macro that takes a type argument and passes
'sizeof(type)' to 'BloomFilter_SetElement'. Whether or not it's worth
the extra complexity in the framework is another question. The main
benefit imo is that documenting the type when a void* argument to do
something with a generic container is used is good practice because it
is more likely to be noticed by the maintainer.

\code snippet
#define bloom_filter_set_element( bloom, data, type ) \
(iBloomFilter.SetElement( (bloom), (data), sizeof(type) ))

BloomFilter* b;
int i = 33;
double d = 1.0;

b = bloom_filter_create( 10, 0.00001, int );
if ( b == NULL )
{
fprintf( stderr, "bloom_filter_create: Failed to allocate bloom
filter 'b'!\n" );
return EXIT_FAILURE;
}
....

/* ok, sizeof(int) == b->ElementSize */
bloom_filter_set_element( b, &i, int );

/* assert violation */
bloom_filter_set_element( b, &d, double );

/* ok, I can't win them all, but maybe the maintainer will
* notice after a bug report
*/
bloom_filter_set_element( b, &d, int );
\endcode

These are all just my opinions based on some of the ideas I've been
playing with.

Best regards,
John D.

 

[Nick]

When building a software project, one of the many pitfalls you can
encounter is releasing the software too early. When released, software
gets used, and the way it is designed gets frozen for fears of not
being backwards compatible and leaving the few users with a lot of
work of changing their code.

That's what I love about web served applications. You can release new
versions three times a day if you want and all your users are always
using the newest version. No good for your library of course, but
brilliant for a self-contained application.

static unsigned int Hash(const void * key, int len, unsigned int seed )
{

const unsigned char * data = (const unsigned char *)key;

Sir, sir! He casted void sir.

In other words, you don't need that cast -
const unsigned char * data = key;
will work perfectly.

 

[ng2010]

When building a software project, one of the many pitfalls you can
encounter is releasing the software too early.

Along with the other 2 dozen important things to doing product
development? Oh, and, btw, what happened to those 2 guys that invented
the PC in their garage? And why?

When released, software
gets used,

Oh that's prophetic.

and the way it is designed gets frozen

The way it is designed gets frozen, huh? The thing is, Jake, when you
post or pontificate or whatever you are doing (advertising) you really
need to understand how you are coming across. Technical incorrectness in
your speaking is not going to help sell your ideas or software: it will
do the opposite (as if I thought you had a fighting chance for selling
horse and buggy... ok, perhaps the latter ).

for fears

You "design" software out of fear. Does that work? I don't want to buy
your software because you are afraid, but I might for charitable reasons.

of not
being backwards compatible and leaving the few users with a lot of
work of changing their code.

Isn't that from the movie with Cherie in it, where her mother asks the
guy why men chase younger women? Do (will "did" now, cuz there are surely
only a few left) C programmers expect to "live forever"?

Luckily, I haven't released any code for my container library,

Cuz I'd look at it and assess it?

so I
can rewrite completely the way it presents itself to the user without
any problems.

Why are you wasting other peoples' time if it's not done yet? Outside of
you needing help, if so, I don't get it. Your friends will help you if
you need it. I've read this group and I know you have friends here.
Making your personal issues a "standard" is another story.

I did just that.

I should maybe read whole posts before I respond to any portion. (Wasn't
a question, note lack of question mark).

I decided to

(1) Hide all definitions of the data types used, leaving abstract data
types instead:

And the stuff I rejected 20 years ago comes around again. Jacob (is
"Jake' OK to address you as?), C is dead. Bury it already. And you're
doing a fine job of doing just that whether you know it or not, and I
know you don't.

typedef struct List List;

Quite tedious syntax, don't ya think?

I can't read anymore of your aimlessness. If you just need help, I think
you are covered. Else, your target market is small and dwindling. But
what of those that come in here and don't know any better and get caught
up in your spiel? You gonna pay them back for how you wasted their time?
Social responsibilty Jacob, learn it. clc is not a charity nor a
marketing avenue.

 

[ng2010]

Ersek, Laszlo a écrit :

That could be done, yes. Another way would be to see if the address
starts at an odd byte not multiple of sizeof(unsigned), and treat the
preceding bytes exactly like the trailing bytes that are handled with
a special case switch at the end.

Jacob, please stop using this room for your personal R&D endeavors. Get
the fucking thing done and present it when it is done and shut up in the
mean time. No one wants your misery, else ally with them and come back
jointly when it is done.I assess that it will take you 5 to 10 years full
time before there is a product if you keep with your current process. I
too assess that what you create will be as useless then as the proposal
is now. But only time will tell. Stop using this as your R&D lab please
because you are hurting people and wasting other's time. Do you know
anything about time Jacob?

 

[Seebs]

Jacob, please stop using this room for your personal R&D endeavors.

This *newsgroup* (not a "room") is for discussion of C, including coding
style, implementation advice, and the like. Jacob's posts about container
interfaces are interesting and topical.

There isn't so much topical discussion of C that we should go around
discouraging people from posting it.

-s

 

[Keith Thompson]

This *newsgroup* (not a "room") is for discussion of C, including coding
style, implementation advice, and the like. Jacob's posts about container
interfaces are interesting and topical.

There isn't so much topical discussion of C that we should go around
discouraging people from posting it.

Agreed. ng2010, feel free to use a killfile if you don't want to
read some particular poster's articles.

 

[Kenny McCormack]

Jacob, please stop using this room for ...

Looks like somebody's off their meds.

It is, of course, beyond hysterical that you are ranting and raving
about how Jacob "comes across", when you really do look, to all the
world, like a raving lunatic.

I wouldn't want you around anything sharp, much less anything
electrical.

--
(This discussion group is about C, ...)

Wrong. It is only OCCASIONALLY a discussion group
about C; mostly, like most "discussion" groups, it is
off-topic Rorsharch [sic] revelations of the childhood
traumas of the participants...

 

[Nick Keighley]

This *newsgroup* (not a "room") is for discussion of C, including coding
style, implementation advice, and the like.  Jacob's posts about container
interfaces are interesting and topical.

There isn't so much topical discussion of C that we should go around
discouraging people from posting it.

AOL. me too

 

[Kenny McCormack]

AOL. me too

But, technically, Jacob's posts *aren't* topical. Because they have to
do with interfaces (and what is, in the real world, generally referred
to as "programming"). As we know (and, no, I am not being facetious
when I say this), programming/interfaces/algorithms are considered
off-topic in CLC, because they are not language-specific. I.e., you can
write, say, the game of Life, or a container library, in any language.

You often see people, most commonly, Kiki, saying things like "That is
not specific to the C language. Therefore, it is off-topic. Maybe you
should try comp.programming (or whatever. Just get-the-hell out of *my*
newsgroup)".

N.B. There is no mention of container libraries in the C standards
documents. QED.

--
(This discussion group is about C, ...)

Wrong. It is only OCCASIONALLY a discussion group
about C; mostly, like most "discussion" groups, it is
off-topic Rorsharch [sic] revelations of the childhood
traumas of the participants...

 

[William Hughes]

Jacob, please stop using this room for your personal R&D endeavors. Get
the fucking thing done and present it when it is done and shut up in the
mean time. No one wants your misery, else ally with them and come back
jointly when it is done.I assess that it will take you 5 to 10 years full
time before there is a product if you keep with your current process. I
too assess that what you create will be as useless then as the proposal
is now. But only time will tell. Stop using this as your R&D lab please
because you are hurting

Sticks and stones ...

people and wasting other's time. Do you know
anything about time Jacob?

If you think Jacob Navia's posts are a waste of
your time, don't read them. (Use a killfile
and you won't have to see them in the first place).
Your assertion that the container library
is "useless" is not new and adds very little to the debate.

- William Hughes

 

[Nick Keighley]

But, technically, Jacob's posts *aren't* topical.  Because they have to
do with interfaces (and what is, in the real world, generally referred
to as "programming").  As we know (and, no, I am not being facetious
when I say this), programming/interfaces/algorithms are considered
off-topic in CLC, because they are not language-specific.  I.e., you can
write, say, the game of Life, or a container library, in any language.

whilst i know you're just trolling, what you say isn't actually true.
Jacob is specifically describing C interfaces to C programs. Now if he
wrote in some language independent (is this possible?) pseudo-code

-- frobniocates Mandrils to produce new Borograves,
-- may modify world Vorpalness levels
frobnicate (in Mandrils[], out Borogroves[], inout Vorpalness)

you might have a point, but he isn't so you haven't.

You often see people [...] saying things like "That is
not specific to the C language.  Therefore, it is off-topic.  [...]

N.B.  There is no mention of container libraries in the C standards
documents.  QED.

besides *my* definition of topicality in clc includes a fair amount of
programming practice and software engineering principles

 

[Kenny McCormack]

..., what you say isn't actually true.

Yes. It is.

Jacob is specifically describing C interfaces to C programs. Now if he...

In Kiki's world, it doesn't matter. It's not specifically about C itself.
I am not making this up.

besides *my* definition of topicality in clc includes a fair amount of
programming practice and software engineering principles

That may be so. But *your* definition does *not* agree with that of
Leader Kiki. And it is Leader Kiki's opinion that counts.

--
(This discussion group is about C, ...)

Wrong. It is only OCCASIONALLY a discussion group
about C; mostly, like most "discussion" groups, it is
off-topic Rorsharch [sic] revelations of the childhood
traumas of the participants...

 

[Mike Weller]

<snip>
(1) Hide all definitions of the data types used, leaving abstract data types instead:

typedef struct List List;
<snip>

What are people's thoughts on inline support for C libraries?

In order to provide inline functions to users of the library you need
the full struct definition in the headers. I like the feeling of
hiding a struct's definition in a .c file, but frankly if people go
messing in your private structs then they are asking for trouble
anyway. I think we put a lot of emphasis on this idea of people
messing with private member vars when it's not really a big issue.

 

[Eric Sosman]

What are people's thoughts on inline support for C libraries?

In order to provide inline functions to users of the library you need
the full struct definition in the headers. I like the feeling of
hiding a struct's definition in a .c file, but frankly if people go
messing in your private structs then they are asking for trouble
anyway. I think we put a lot of emphasis on this idea of people
messing with private member vars when it's not really a big issue.

I'm not sure whether you're speaking of C's own Standard library,
or of libraries a user might write in C. If the former, details can
still be hidden because "implementation magic" can be at work.

For user-written libraries, I feel that the benefit comes not
so much from defending against malicious (and suicidal) users, but
from maintaining separability in the face of version changes. If my
library uses an opaque struct type and allows the caller to get hold
of pointers (but not free-standing instances), I can distribute a
new library version with an altered struct layout without requiring
the callers to take any action at all -- without even requiring them
to recompile. That's a significant advantage, IMHO.

Case in point: At a PPOE, our C library exposed some details of
the FILE struct to user code, in the form of macros that accessed
this or that struct element to get their work done. One of the
details exposed was the fact that a FILE used an `unsigned char' to
hold a "file descriptor," essentially a "handle" for the I/O channel
the FILE's stream talked to. This knowledge was compiled in to every
program that used a FILE -- not that the users had done anything evil,
but the library-supplied macros built into their code "knew" how to
find the file descriptor in a FILE.

Eventually, the day came when 256 files were not enough: You'd
have Web servers and the like with tens of thousands of open files.
And, of course, we were in Deep Trouble ... We *could* have changed
FILE to use an `unsigned long' or something, but then we'd have had
to tell hundreds of thousands of users to recompile millions of
programs (not exaggerating) -- which would be particularly troublesome
for programs using third-party libraries in object form ...

Eventually the problem was solved, but the result was neither
pretty nor efficient. The experience is enough to convince me, at
any rate, of the value of keeping private details under wraps: Even
if you don't see a reason for secrecy today, tomorrow will come.

 

[jacob navia]

Mike Weller a écrit :

What are people's thoughts on inline support for C libraries?

In order to provide inline functions to users of the library you need
the full struct definition in the headers. I like the feeling of
hiding a struct's definition in a .c file, but frankly if people go
messing in your private structs then they are asking for trouble
anyway. I think we put a lot of emphasis on this idea of people
messing with private member vars when it's not really a big issue.

The crux of this work is to specify a series of interfaces to be
standardized into the language.

A concrete implementation could add all definition it wants instead of
just making it hidden. That would allow it to make inline functions, as
you point out, or to display the inner structure in the debugger, etc.

That is an implementation issue, not a specification issue. The
specifications, the contents of "containers.h", shouldn't contain ANY
definitions of any structure, so that different implementations can use
the same interface.

In the sample implementation that will be distributed with the
containers specifications, all structures are hidden. This has
advantages and disadvantages of course.

In my opinion, for the sample implementation, speed is not that
important. It should just provide an example of how things could be done.