* Linked List Implementation @ 2017-11-27 1:27 Charlie Sale 2017-11-27 8:02 ` tomas 2017-11-27 12:02 ` Florian Weimer 0 siblings, 2 replies; 8+ messages in thread From: Charlie Sale @ 2017-11-27 1:27 UTC (permalink / raw) To: libc-help 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 1:27 Linked List Implementation Charlie Sale @ 2017-11-27 8:02 ` tomas 2017-11-27 12:02 ` Florian Weimer 1 sibling, 0 replies; 8+ messages in thread From: tomas @ 2017-11-27 8:02 UTC (permalink / raw) To: libc-help -----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----- ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 1:27 Linked List Implementation Charlie Sale 2017-11-27 8:02 ` tomas @ 2017-11-27 12:02 ` Florian Weimer 2017-11-27 12:19 ` Toebs Douglass 2017-11-27 15:19 ` Charlie Sale 1 sibling, 2 replies; 8+ messages in thread From: Florian Weimer @ 2017-11-27 12:02 UTC (permalink / raw) To: Charlie Sale; +Cc: libc-help 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 12:02 ` Florian Weimer @ 2017-11-27 12:19 ` Toebs Douglass 2017-11-27 16:22 ` Florian Weimer 2017-11-27 15:19 ` Charlie Sale 1 sibling, 1 reply; 8+ messages in thread From: Toebs Douglass @ 2017-11-27 12:19 UTC (permalink / raw) To: libc-help 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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 12:19 ` Toebs Douglass @ 2017-11-27 16:22 ` Florian Weimer 2017-11-27 16:38 ` Toebs Douglass 0 siblings, 1 reply; 8+ messages in thread From: Florian Weimer @ 2017-11-27 16:22 UTC (permalink / raw) To: Toebs Douglass; +Cc: libc-help 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 16:22 ` Florian Weimer @ 2017-11-27 16:38 ` Toebs Douglass 2017-11-27 16:56 ` Florian Weimer 0 siblings, 1 reply; 8+ messages in thread From: Toebs Douglass @ 2017-11-27 16:38 UTC (permalink / raw) To: libc-help 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 :-) ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 16:38 ` Toebs Douglass @ 2017-11-27 16:56 ` Florian Weimer 0 siblings, 0 replies; 8+ messages in thread From: Florian Weimer @ 2017-11-27 16:56 UTC (permalink / raw) To: Toebs Douglass, libc-help 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Linked List Implementation 2017-11-27 12:02 ` Florian Weimer 2017-11-27 12:19 ` Toebs Douglass @ 2017-11-27 15:19 ` Charlie Sale 1 sibling, 0 replies; 8+ messages in thread From: Charlie Sale @ 2017-11-27 15:19 UTC (permalink / raw) To: Florian Weimer; +Cc: libc-help 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2017-11-27 16:56 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-11-27 1:27 Linked List Implementation Charlie Sale 2017-11-27 8:02 ` tomas 2017-11-27 12:02 ` Florian Weimer 2017-11-27 12:19 ` Toebs Douglass 2017-11-27 16:22 ` Florian Weimer 2017-11-27 16:38 ` Toebs Douglass 2017-11-27 16:56 ` Florian Weimer 2017-11-27 15:19 ` Charlie Sale
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).