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

jacob navia <jacob@xxxxxxxxxxxx> wrote:

Anyway let's forget this. I will start immediately to discuss this
in the french group, then I will send that letter formally.

jacob

P.S. if anyone wants to know what I am talking about go to:

http://code.google.com/p/ccl/

There you will find the documentation and the sample implementation.

Interesting.
Since there's more incentive to standardize things that have several
existing implementations, I suggest that you try to propose it to some
other compiler implementers. For example, the GNU GCC has been known to
be used as an experimentation field for new features.
On the other hand, GCC guys may argue that this is library stuff and
should best be implemented in GLIBC/uClibc rather than in libgcc, which
would be right... Unfortunately, Ulrich Drepper being who he is, he is
unlikely to accept new functions that have not yet been standardized
(e.g. he didn't accept strlcpy/strl* even though they have several
implementations).
That's why, you have more chance getting your code accepted in the
EGLIBC and uClibc as optional modules, selected during the library
compilation.

I had a quick overview of the document and have a few comments.

== 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. 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.
A "default save function" is mentioned but its behavior is unspecified.

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.

== 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...

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

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.

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

== 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.
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.

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);

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.

== 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.

== 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;
};

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

Have a nice day.
--
André Gillibert
.

Relevant Pages

  • Re: BUG: "const _Ty&" vs "const_reference"
    ... > allocators, implementations are free to substitute at will. ... it's purely a QoI issue whether or not containers ...
    (microsoft.public.vc.stl)
  • Re: OT: Requesting C advice
    ... packages, or if the package you choose supports it, have it compile K&R. ... heap and locals are on a stack. ... But the main point is that it doesn't matter what bit pattern represents a null pointer. ...
    (Fedora)
  • Re: sizeof(ptr) = ?
    ... the smallest directly addressable memory unit is much larger than the ... On such implementations, addressibility of individual bytes is not ... using a pointer that contains both a memory address and a byte ... There are also machines with byte addressing but not byte access, ...
    (comp.lang.c)
  • Re: N1298 - try/finally for C
    ... Do you mean that "struct throwInfo" should be optional? ... that exception handling would be supported only on implementations ... If the standard mandates an integer as throw argument, ... should be an integer wide enough to encode a pointer if necessary. ...
    (comp.std.c)
  • Re: Ada Pointer Problem
    ... > definition should not unnecessarily constrain implementations. ... > value may not necessarily be just a pointer; ... but then I like assembly language too. ...
    (comp.lang.ada)