Linked List Implementation

Linked List Implementation

[Charlie Sale]

Hello glibc

I was wondering why glibc does not have any sort of linked list or related
data structures implemented? Is glibc not the place for it, or is there
some other reason? Because if there is no reason for there not to be a
linked list implementation, I thought about giving it a shot. Would it be
appreciated?

~Charlie

Re: Linked List Implementation

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sun, Nov 26, 2017 at 08:26:35PM -0500, Charlie Sale wrote:
> Hello glibc
> 
> I was wondering why glibc does not have any sort of linked list or related
> data structures implemented? Is glibc not the place for it, or is there
> some other reason? Because if there is no reason for there not to be a
> linked list implementation, I thought about giving it a shot. Would it be
> appreciated?

For historical reasons, mainly. But nowadays standards have settled in a
way that it doesn't make sense to pack even more into libc than currently
is. As of now, libc concerns itself with some string handling, (float,
double) numeric functions and (the biggest part) operating system
interface. And that's already a tall order, mind you :-)

See [1] for a good overview on what is there and how it came to be.

As far as I know there are no "standard" libraries for the classical
algorithms and data structures in C, although if you look around you'll
find many good implementations as spin-off of several projects.

The C++ folks have gone some way into standardizing this (cf. STL [2]),
perhaps because in C++ it's somewhat easier to express generic
algorithms.

Cheers

[1] https://en.wikipedia.org/wiki/Libc
[2] https://en.wikipedia.org/wiki/Standard_Template_Library

- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAlobxnwACgkQBcgs9XrR2kbxwwCeLMbULbkh9rWhvT9jo52R/muP
1+EAn0junh8tMznQfzNSlhE1RkmXYI+l
=V+lf
-----END PGP SIGNATURE-----

Re: Linked List Implementation

[Florian Weimer]

On 11/27/2017 02:26 AM, Charlie Sale wrote:

> I was wondering why glibc does not have any sort of linked list or related
> data structures implemented?

In fact, there is an implementation of doubly-linked lists, see insque 
and remque.  Balanced binary search trees are provided with tsearch and 
related functions.  For hash tables, see hsearch_r.

These interfaces are old and somewhat difficult to use, but I expect it 
will be difficult to get consensus for a new set of interfaces because 
everyone looks for something different in a container library.

Thanks,
Florian

Re: Linked List Implementation

[Toebs Douglass]

On 27/11/17 12:02, Florian Weimer wrote:
> These interfaces are old and somewhat difficult to use, but I expect it 
> will be difficult to get consensus for a new set of interfaces because 
> everyone looks for something different in a container library.

As a data structure developer, I'm very interested to find out what 
other people are expecting from APIs.

For me, there is a struct for state, a struct per element, each element 
has two void pointers, one to the key, one to the value.  The 
per-element struct is normally a member of the user struct which is to 
placed into data structure, the the value is set to be the address of 
that user data structure.

The caller performs all allocations, so he can use heap, stack, globals, 
etc.

There's an init() and a cleanup() for the main state struct, and the 
data structure functions themselves (link to list, insert to btree, etc, 
depending on the data structure).

Where reasonably possible, APIs are macros, as often very little work is 
being done.

Data structures are either single threaded, and the user handles 
locking, or lock-free (in which case, heaven help us all :-)

And that's it - that's what I've come to, after all these years.

I'd love to find some new ideas, things I've totally missed, use cases I 
had no idea about.

Re: Linked List Implementation

[Florian Weimer]

On 11/27/2017 01:19 PM, Toebs Douglass wrote:
> I'd love to find some new ideas, things I've totally missed, use cases I 
> had no idea about.

There's some disagreement whether inline allocation of keys/values needs 
to be supported, whether key/value pointers should be void *, and 
whether the allocator should be tied to malloc/free.  Some people prefer 
macros which generate function definitions, others prefer function 
pointers (sometimes with a closure argument, sometimes without).  Some 
are strictly opposed to aliasing violations which happen to work today, 
others want strict language conformance.

For individual data structures, the level of configuration offered 
varies greatly.  Not everyone things a custom resize policy is necessary 
for arrays or hash tables, or you need to be able to choose between 
different conflict resolution strategies in hash tables.

Some people want C++ compatibility, others are strictly opposed to it.

Those are just he issues that come to my mind immediately.

Thanks,
Florian

Re: Linked List Implementation

[Toebs Douglass]

On 27/11/17 16:22, Florian Weimer wrote:
> On 11/27/2017 01:19 PM, Toebs Douglass wrote:
>> I'd love to find some new ideas, things I've totally missed, use cases 
>> I had no idea about.
> 
> There's some disagreement whether inline allocation of keys/values needs 
> to be supported,

Inline?  do you mean by this inside the data structure function calls?

> whether key/value pointers should be void *,

What are the alternatives?

> and whether the allocator should be tied to malloc/free.

If the user handles allocation, this problem is solved, because it is up 
to the user.

As it is, NUMA alone makes allocation inside a data structure ugly, 
because you have to pass in so many parameters.

In general though the user benefit hugely from being able to allocate 
from the stack or heap, or globals; when I stopped doing allocation 
inside data structures, it seemed to me absolutely clearly the right 
thing to do - resource allocation is a different and separate task.

> Some people prefer 
> macros which generate function definitions,

Hard to follow in a debugger.  Code should look like it is.

> others prefer function 
> pointers (sometimes with a closure argument, sometimes without).

Do you mean function pointers for the API functions?  stored in say the 
state structure?

> Some 
> are strictly opposed to aliasing violations which happen to work today, 
> others want strict language conformance.

I'm not sure I've ever run into aliasing issues... why would you benefit 
from doing so / what would you be doing for it to occur anyway?

> For individual data structures, the level of configuration offered 
> varies greatly.  Not everyone things a custom resize policy is necessary 
> for arrays or hash tables, or you need to be able to choose between 
> different conflict resolution strategies in hash tables.

Yes, but this doesn't matter - data structures in what they offer, as 
opposed to how they are implemented (macros, allocation, etc), vary.  A 
list is not a tree.  It's fine to have many different data structures 
which offer different things.

> Some people want C++ compatibility, others are strictly opposed to it.

I've heard of "Clean C", which can be compiled in C++ mode, where the 
compiler can optimize more thoroughly.  That seems nice.

> Those are just he issues that come to my mind immediately.

Heh!

I've clearly been living under the stairs for a long time :-)

Re: Linked List Implementation

[Florian Weimer]

On 11/27/2017 05:38 PM, Toebs Douglass wrote:
> On 27/11/17 16:22, Florian Weimer wrote:
>> On 11/27/2017 01:19 PM, Toebs Douglass wrote:
>>> I'd love to find some new ideas, things I've totally missed, use 
>>> cases I had no idea about.
>>
>> There's some disagreement whether inline allocation of keys/values 
>> needs to be supported,
> 
> Inline?  do you mean by this inside the data structure function calls?

Without pointer indirection.

>> whether key/value pointers should be void *,
> 
> What are the alternatives?

Concrete pointers and more macros to generate the struct definitions (or 
type-safe accessor functions).

>> others prefer function pointers (sometimes with a closure argument, 
>> sometimes without).
> 
> Do you mean function pointers for the API functions?  stored in say the 
> state structure?

Yes.  It provides for more code sharing, fewer macros, and thus better 
debugging, but reduces type safety and may counteract security hardening 
efforts.

>> Some are strictly opposed to aliasing violations which happen to work 
>> today, others want strict language conformance.
> 
> I'm not sure I've ever run into aliasing issues... why would you benefit 
> from doing so / what would you be doing for it to occur anyway?

Lying about concrete types often enables additional code sharing, which 
reduces icache pressure and thus increases performance.

Thanks,
Florian

Re: Linked List Implementation

[Charlie Sale]

On Mon, Nov 27, 2017, 7:02 AM Florian Weimer <fweimer@redhat.com> wrote:

> On 11/27/2017 02:26 AM, Charlie Sale wrote:
>
> > I was wondering why glibc does not have any sort of linked list or
> related
> > data structures implemented?
>
> In fact, there is an implementation of doubly-linked lists, see insque
> and remque.  Balanced binary search trees are provided with tsearch and
> related functions.  For hash tables, see hsearch_r.
>
> These interfaces are old and somewhat difficult to use, but I expect it
> will be difficult to get consensus for a new set of interfaces because
> everyone looks for something different in a container library.
>
> Thanks,
> Florian
>

Thanks for the info. I will drop the project.

~Charlie

> --

~Charlie Sale