Re: Standard containers (Was: Wiki by the committee closed?)

Le 11/12/11 12:53, André Gillibert a écrit :
jacob navia<jacob@xxxxxxxxxxxx> wrote:


== ISSUE 1 ==
The Save/Load functions seems a bit underspecified. I understand that
each element is saved by invoking SaveFunction, in some unspecified
order (are they loaded in the same order?), plus some unspecified
metadata.

Yes.

I assume (but didn't read), that the SaveFunction must save a
contiguous chunk of bytes, advancing the seek pointer of the some
offset, without seeking elsewhere, because the Save function may need
that in order to keep the state consistent.

Well, that's right, but I did not thought about explicitly specifying
that since it seemed too obvious to me. I will add it. Thanks.

A "default save function" is mentioned but its behavior is unspecified.


This will just write element size bytes into the stream at the very
least. It can be recursive and save all "pointed to" data if you
want, the ONLY requirement is that the load function understands
what the save function writes. That is ALL.

I will add that to the specs. Thanks.

Since the metadata format and position of data is unspecified, I assume
this function is unlikely to produce files in a format portable
between two implementations, even if they are compiling the same code,
which reduces its usefulness, although this may be enough for
unspecified temporary files.

IMHO, the metadata format could at least be specified for sequence
containers, and, maybe for associative containers.


This is a rather complicated problem. If you overspecify,
implementations can be constrained by what they need to save.

What do we know of requirements in a few years from now? Maybe
some implementation wants to add a CRC, others will want a GUID,
or some metadata like endian order, time stamp, you name it.

It will be very difficult to cover ALL those problems in a
first iteration of the specifications.

== ISSUE 2 ==
The NewIterator function can fail with error CONTAINER_ERROR_NOMEMORY.
This makes it very hard, if not impossible, to write good code,
catching all OOM conditions, and properly pre-allocating data before
it's needed.
Proposal: Since a fixed size is certainly enough for an iterator,
define a structure for each iterator, and provide a InitIterator
function.
Issue: The iterator structure won't be the same for all containers,
which is a problem for container-agnostic algorithms.
Providing an opaque iterator structure that's big enough for all
containers (probably implemented as a union), would be ugly too...


I haven't defined ANY structure in the specifications. The library
writers are left ALL freedom to do whatever they want within the context
of the functional specifications.

One solution would be to add to each container a

"GetIteratorSize(void)"

API, that would allow you to write:

int fn(int foo)
{
size_t siz = iList.GetIteratorSize();
char buf[siz];
iList.InitIterator(buf);
// Use the iterator here
}

Anyway, the current state is not good. Further thought is required.


Yes. Thanks

General issues:
== ISSUE 3 ==
Error handling is a bit different from the traditional POSIX/C
errno-based error handling. Why this inconsistency? errno-based
handling may be ugly, but it's the standard, and all implementations
manage to implement it.

Okay, that's partially explained in 1.6.1.
But, the default behavior of outputing error information on stderr may
be fine when debugging, but should not be the default, because, it may
output nothing when everything is fine, and start to write data, in
some cases, but not always, when the system is in production. This is
bad if the program usually outputs well-formatted data on stderr.

Solution: Make the default error reporting function output nothing on
stderr. For errors that should never happen in a correct program (e.g.
bad pointers, overflows, and maybe even CONTAINER_ERROR_INDEX), why not
abort by default? The program is necessarily in inconsistent state, the
same way as a program that segfaults on UNIX. Continuing execution as
if nothing happened is a security issue.


This is implementation defined. All implementations are required to
provide a default error function but I left that out to give library
writers as much leeway as possible. The sample implementation provides
(granted) a not so fanciful error function.


BTW, it's not clear if CONTAINER_ERROR_INDEX is guaranteed, or not, to
be reported if a container is accessed out of bounds.


Yes. But I fear many people will complain because of this obsession with
execution speed.


== ISSUE 4 ==
Implementation of interfaces, using pointer functions as member of
structures, differs from the usual C/POSIX standard libraries, but may
be useful to write container-agnostic algorithms... except that it
is not portable, because functions don't take void pointers for
the container.

Well, why would you pass a void pointer? All functions expect a List *
or a HashTable * and you HAVE to pass it a pointer to the right
container if not they will crash. The problem of void pointers is that
they can't be checked by the compiler. Now, if you replace (subclass) a
library function you can, but you HAVE to keep the interface.

For example, converting a function pointer from iList.GetElement (whose
prototype is void *(*)(List *L, size_t index)) to void *(*)(void *C,
size_t index) and invoking it with a list instance is undefined
behavior.


Yes, but why would you need to pass a void pointer?

Moreover, iList.GeElement prototype is specified twice in the
document, but they don't match. :|
Page 78:
void *(*GetElement)(List *list, size_t idx);
Page 66:
void *(*GetElement)(List *L, int idx);


Second is wrong, excuse me. I will correct that immediately.
This has histerical reasons :-)


Function pointers may also cause a performance penalty for simple
functions (e.g. vector GetElement), because if it were not a
function pointer, it could easily be an inline function.


A compiler can optimize that, if the committee approves this library.
The user can specify that he/she does NOT subclass any functions
of the library and then the compiler is free to inline all those
functions.

For instance a C compiler can specify

#pragma CCL_NOSUBCLASSING (on/off)


Or (maybe better) we could add it to the library specifications
so that all code would be portable:

#pragma STDC_CCL_NOSUBCLASSING (on/off)


== ISSUE 5 ==
Conditions where some iterators may be invalidated are not well
specified. The Replace function is said not to invalidate iterators,
but, for example, the behavior of the list Reverse function is
unspecified.


There is only ONE rule: Any change to a container's structure
or to its contents invalidates ALL pointers.

When you use an iterator to do the replacement THAT iterator
is NOT invalidated but ALL others are.


== ISSUE 6 ==
I guess that vector's Add function may move the data of any element in
the vector (with a function equivalent to memmove), while the list Add
function may not. This is not specified, even though it may be very
important if the programmer uses data structures with internal
pointers.

struct data_structure {
int *ptr; /* set to point to value1 or value2 */
int value1, value2;
};


In general there is only one rule: If you modify anything, all pointers
are invalidated. True, a list COULD be a special case but that would
lead us to the problems of C++ where there are a huge number of complex
rules for each container. If you change containers, and that is one of
the reasons of using them in the first place, you have to review all
your pointers to see if the rules of the new container do not introduce
any bugs.

That is a nightmare. Much easier is to have SIMPLE rules that everyone
understands, even if some optimizations are left out, like for instance,
the possibility of keeping valid pointers to list data in the middle
of a list reorganization.

Obviously implementations can add their own specs:

OUR list elements never change when you add something to our lists.

But then you are not writing portable code since other implementations
could compact list data at random times when deleting elements, for
instance... If we would allow list pointers to be kept we would make
those implementations impossible.



=======
Overall, it doesn't look bad.

Have a nice day.

Thank you for your very good comments. I will introduce all the ideas
that you have suggested and correct the bugs you pointed me to.

jacob
.

Relevant Pages

  • Re: abstract containers: does such a thing exist, conceptually?
    ... create a firewall between different types of lists. ... > behaviour by the additional pointers. ... I do not like much STL's style of iteration with iterator objects, ... For example, an array view for containers with ordered elements, ...
    (comp.object)
  • Re: discriminant questions
    ... Aren't you a proponent of iterator approach? ... The problem here is the semantics of existing iterators upon container ... a circular list probably deserves a different interface ... Circular lists are the most important ones among doubly-linked lists, ...
    (comp.lang.ada)
  • Re: STL Vector: Unexpected behavior
    ... iterator of that container. ... you could move all pointers you want to keep to a new ... you also omit checking if the pointer is zero in your loop. ...
    (microsoft.public.vc.stl)
  • Re: List or Iterator
    ... A reference is a reference. ... There are Lists, Iterables and Iterators and they are not interchangeable. ... obtain an Iterator from it and the Iterator will produce items in the ... obtaining items from the container one at a time. ...
    (comp.lang.java.programmer)
  • Re: Idioms for iterators in C
    ... I think returning a deep copy of the contained object is overkill. ... container is purpose-built for the data type, ... pointers around because he thinks they threaten security;-) ... should try not to invalidate any existing iterator. ...
    (comp.lang.c)