Show HN: C library of generic, reference-counted data structures(theck01.github.io) |
Show HN: C library of generic, reference-counted data structures(theck01.github.io) |
Anyway, it's nice to see a portable, modern CF-like library, although of course it's too slow for some cases where code specialization is called for.
Edit: On the general subject of C data structures, in case anyone's interested, I wrote a little portable C header that provides minimal hash table functionality using macros, with a large amount of control - still generic, but totally opposite to the approach used by this library, much lower level. It's modeled after the BSD <sys/queue.h> header, provides three versions (open, closed, and a higher level version), and is completely undocumented, but I'm somewhat happy with it as a proof of concept. Just throwing it out there. https://github.com/comex/cbit/blob/master/hash.h
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"
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.
http://ccodearchive.net/list.html
https://github.com/rustyrussell/ccan
And GMP for arbitrary precision math (integers and floating point numbers).
Linked library in nice, but how many C projects do you know that use camelCase() function naming as opposed to K&R's lower_case_naming()? If it were a complex library, like OpenSSL, then - sure, to the hell with the notation, just put a wrapper around it and use it anyway. It's barely an issue. But if it is a simpler library that is meant to be weaved into the code, like data containers, the choice of naming notation is always a thing to consider.
There is obviously an indent tool, but resorting to it means using a modified version of the original with all the consequences that follow. Perhaps, it might be the next thing for GitHub to tackle - "Download in Xyz naming notation"... I know I'd use it.
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.
That's "C-style namespaces" - really the only sane way to avoid an identifier collision, sorry.
I think your project looks very interesting. Reference counted datastructures is a great convenience.
Thanks, and Good Luck further.
I think this is pretty cool. I like the presence of the tests as well.
Any particular reason why you're avoiding the C99 _Bool?
* only a header file * has hash, array, string, list, implementations
However I didn't do reference counting. Good job OP!
I once built classes using structs and function pointers, but this sounds different?
With regard to OBString: don't. Really. C strings are very flexible and powerful with just what's in the standard library. You don't need charAtStringIndex, for example: you have rindex and index. You don't need splitString; you have strtok_r. You don't need findSubstring; you have strstr.
If you think you need regexes, consider fnmatch, a libc function which matches shell wildcard patterns. It's always there, it's simple, and it's fast. Or you could bring in something like PCRE. In general, if you need full regexes in a small program, it might be worth rethinking whether your program should be in C anyway.
For some reason, I don't find myself using resizable array utility code much in C. It's pretty easy to do it yourself with realloc-- that's really one of the first things they should teach people learning practical C. Perhaps a small, minimal set of macros could wrap the reallocs and make it a little bit nicer.
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_)
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.
CPP macros, entirely. No, thanks.
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.
Currently I'm using this code just for a string buffers and other arrays where the individual elements are stored in-place in the array.
I don't really understand the fear of macros. void pointers are much scarier than macros, since they open you up to the threat of bugs going undetected by the type system.
You're not by any chance maintaining one of those much-maligned "driver portability" layers, are you?
If you look at the slist, slist_queue and dlist, you'll find there are typed macros (via a container-of macro) that call down to the generic functions. I might try to extend this to macros that generate a full set of shim inline function for a particular type of list element, if it turns out to be less error prone. You won't see a void pointer being passed around on any of these.
Where function pointers come into play (binary tree, hash tables) I'll admit it's maybe not quite so clear cut as the indirection messes with branch predictors, etc. and the callbacks all take void pointer arguments. Maybe for those containers it would be better to have generator macros that produce function prototypes and implementations.
And no, I'm not doing anything particularly focused on driver portability. I mostly write OS X kexts, and the built-in data structures in xnu aren't terribly helpful. (the OSContainer family uses blocking memory allocations, can only hold refcounted objects and the map and set use linear search) Some kernel code I write is designed to be portable, and I use these data structures for that code, but it's pretty much just a standard factored design - general core and platform specific setup and API use. Nothing with any pretence of being a general solution.