Live data from Hacker News

Show HN: C library of generic, reference-counted data structures

theck01.github.io

21–30 of 42 posts

Re: Show HN: C library of generic, reference-counted data structures

#21
post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

"For some reason, I don't find myself using resizable array utility code much in C."

Most of the time, the amount of memory you'll need to do something is predictable. When dynamic arrays are always at hand, you lose the habit and end up always reaching for one.

Re: Show HN: C library of generic, reference-counted data structures

#22
post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

> You might also want to look at queue.h from BSD CPP macros, entirely. No, thanks.

I'm not a fan of macros either, which is why I've ended up implementing hybrid C data structures, with the logic in functions, and some optional type helpers in macros:

https://github.com/pmj/genccont

Anyway, these are largely intrusive and don't do reference counting, but that can be seen as an advantage or disadvantage, depending on the situation. (I use these heavily in kernel code) The hash tables (chaining and open addressed linear probing) use function pointers to be type-generic, which might not be to everyone's taste either.

Re: Show HN: C library of generic, reference-counted data structures

#23
post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

Intrusive data structures are indeed more powerful. I made my own instrusive AVL-tree which can be found here [1] and an example here [2]. There's also the extra feature that the concept of a "link" is abstracted, so you can for example build a compressed AVL-tree inside an array using array indices instead of pointers, which don't break when the array is reallocated. It's also built in a different way than this usually done (macros), that is, a header file is included which redefines some identifiers, and the actual code of the functions is not inside macros, hence, easier to read.

About strings, I firmly believe that C's zero-terminated strings should be avoided and only used when necessary to communicate with existing code. They're really not simple and fast. You can't take a null-terminated string and extract a null-terminated sub-string without modifying the original - which is very often needed during various kinds of parsing. Also, null-terminated strings are unable to represent the zero byte, so in general, for example, you can't use them to store the contents of an arbitrary file, and if you do use them for purposes where null bytes can appear, you have to be careful and handle errors where nulls would implicitly truncate your string.

Just use (pointer, length) strings instead. It'll save you a whole bunch of trouble you may not see coming.

[1] https://code.google.com/p/badvpn/source/browse/#svn%2Ftrunk%... (CAvl_)

[2] https://code.google.com/p/badvpn/source/browse/#svn%2Ftrunk%... (cavl_test_)

Re: Show HN: C library of generic, reference-counted data structures

#24
post #8

I would suggest offering the ability to plug custom allocators.

If you feel a need to do that, check cmccabe's comment on the top about intrusive data structures. These let you do your own memory management, in a way that the data structure implementation doesn't need to know about.

Re: Show HN: C library of generic, reference-counted data structures

#25
post #17

nice. it's heartwarming to see things like this in c. in my spare time i am working on struct-sql mapping. it sometimes feels like the popular c libraries don't try hard enough to provide the convenience we get in other languages. with a little imagination (as here) i think we can push things a little further...

What is struct? Or do you mean the C struct type SQL? Like an ORM for C?

yup, exactly - see link above.

Re: Show HN: C library of generic, reference-counted data structures

#26

nice. it's heartwarming to see things like this in c. in my spare time i am working on struct-sql mapping. it sometimes feels like the popular c libraries don't try hard enough to provide the convenience we get in other languages. with a little imagination (as here) i think we can push things a little further...

Is your project hosted somewhere? I would love to see the source for that, no matter how early/unpolished it is.

sure, there's an example at https://bitbucket.org/isti/c-orm/src/4ec76f741d756bf70c2b1b8... but i don't have any text explaining it yet, and it's a bit hard to see what is happening.

but basically there's a python script that parses your struct definitions and then auto-generates a library (this isn't great i know, but what else can you do? if you don't want to use that, you can still use it as an SQL library, but you need to write your own callback functions to do the work of setting values in the struct). that library is

    #include "phonebook.corm.h"
in the linked code. then you can do things like

    static int find_name(isti_db *db, const char *text, name** name) {
      corm_name_select *select = NULL;
      *name = NULL;
      STATUS;
      CHECK(cname.select(&select, db));
      CHECK(select->name(select, "like", text)->_go_one(select, name));
      EXIT;
      if (status == ISTI_ERR_NO_RESULT) status = ISTI_OK; // see NULL name
      if (select) status = select->_free(select, status);
      RETURN;
}

(the STATUS, CHECK, EXIT and RETURN are just macros for the usual "return an int as status and goto exit on error" handling). the snippet above populates the name (a struct typedef) pointer with values (id and name value in this case) from the database. the thing called select is a struct with function pointers that generates SQL select functions (so there's the usual objects-in-C pattern of passing the struct in to the function in "select->name(select, ..." for example). and the SQL being generated is "select * from [table] where name like [value]". it's all escaped correctly to avoid SQL injection.

the API for the database backend is isolated out, but the only current implementation is sqlite.

the complete repo is at https://bitbucket.org/isti/c-orm/src (if you download it and run doxygen you should see better docs - but they're incomplete and not online yet)

if people are interested, email me at andrew@acooke.org and i'll get back to you when it's in a usable state (it mainly needs docs, polishing, and perhaps another database backend - probably postgres).

also, of course, there are many limitations compared to ORM systems. there's no way to retrieve related objects, for example (so if a struct has a pointer to another struct, that pointer isn't retrieved - the best you can do is also store a pointer to the primary key and then make a second call based on that). and currently table and column names must exactly match struct and field names.

Re: Show HN: C library of generic, reference-counted data structures

#27
post #15

I was interested to know how this compares with existing C libraries, so I "ported" the prime number example program to use GMP and GLib instead. It's not quite working yet (see the description) and I have to run now, but here's the code--I think it's nearly complete and would be interesting to benchmark once done. https://gist.github.com/jzwinck/5787359

Shoot, if I had known someone was going to do this I would have made the prime number program a bit more efficient. Since it looks like you've ported the algorithm exactly it shouldn't affect the result though. Let me know what the test reveals, I tried to write the fasted arbitrary precision algorithms I could.

Re: Show HN: C library of generic, reference-counted data structures

#28
post #9

It's nice that you made these available. You might also want to look at queue.h from BSD (see http://fxr.watson.org/fxr/source/sys/queue.h ) and tree.h ( http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h ), single-file "libraries" that can generate a few different kinds of linked list and binary tree. These don't require typecasting at all, since they generate functions for your particular type. They are also…

Sadly some form of OBString is a necessity, any string object needs a reference count and some function pointers packaged in the struct to work. Converting OBString to have the same interface as standard string handling functions is a good idea though, and using the standard functions as a backend would also be done in that case.

Re: Show HN: C library of generic, reference-counted data structures

#29
post #14

Was there a rationale to choosing performActionOnStruct() names instead of the perhaps-more-idiomatic struct_perform_action() style? I strongly advise against putting identifiers like release() and getCString() in the global namespace, that's probably not the wisest idea if you plan to use libraries other than your own.

Some bad habits from Java are the only reason. I thought about having obrelease and obgetCString. Putting ob at the beginning of every function seems like overkill, and I don't like that only some functions had would have ob at the beginning if I didn't do a global name change. Any suggestions?

Re: Show HN: C library of generic, reference-counted data structures

#30
post #18

I've been meaning to refresh and expand both my algorithms knowledge and my C programming with a project like this, myself (as an application developer I find I've barely used either since graduating from university). Was that part of your goal at all? I think this is pretty cool. I like the presence of the tests as well.

I just graduated, so most of the data structures are still pretty fresh in my mind. I started after getting tired of implementing data structures in my many C based classes, hoping that at least I would get some use out of them during school. Sadly after that I never took another C based class, but the project became interesting in its own right and I stuck with it.
Post reply on HN