include/tlist.h

   1 #ifndef TLIST_H
   2 #define TLIST_H
   3
   4 #include <stddef.h>
   5
   6 /*
   7    tlist, aka treap list. (C) 2024 rofl0r.
   8
   9    the core's algorithm is based on the "implicit treap" described on
  10    e-maxx.ru.
  11
  12    tlist behaves like a dynamic array, but unlike a real array supports
  13    insertion and deletion with O(log N) performance characteristics.
  14
  15    indexing is also O(log N), so if you don't need fast insertion and
  16    deletion, only appending, picking a traditional dynamic array will be
  17    faster for your usecase.
  18
  19    on a fast machine with plenty of cache, a traditional dynamic array
  20    will also be faster if you need to insert or remove some items, and
  21    the array is reasonably small (up to about 2k entries).
  22    though even there the tlist is quite competitive.
  23    for anything else, the tlist outperforms the traditional array by far.
  24
  25    its most appealing characteristic, aside from the above, is that it
  26    can be implemented in less than 100 lines.
  27    it comes at a cost though.
  28    the memory consumption per node is 24 bytes on 64bit machines, and 16
  29    on 32 bit. plus the size of the item being stored in it.
  30
  31    the list is initialized with the fixed size of a single item that
  32    needs to be stored - it could be a single integer, a struct,
  33    or a pointer.
  34
  35    on insertion, you pass a pointer to a single item, the object being
  36    pointed to is then copied into the node.
  37
  38    for non-fixed size data items such as strings, you'd use the size
  39    of a pointer for tlist_new(). then you need to allocate the strings
  40    yourself and insert a pointer to the string - i.e. a char**.
  41    the list can free the pointed to content automatically if you use
  42    the _deep suffixed functions.
  43
  44    the list can hold a maximum of UINT_MAX items.
  45
  46    note that unlike in my dynamic array implementation "sblist", functions
  47    taking an index receive it as second, not third argument.
  48    it seems more natural to first pass the list, then the index, then the
  49    value, as the index refers to the list.
  50    apart from that, the api is almost identical, which allows for a quick
  51    swap-out.
  52 */
  53
  54 struct tlist;
  55 typedef struct tlist tlist;
  56
  57 /* allocates a new list prepared to store nodes of itemsize size.
  58    may return NULL on resource exhaustion. */
  59 struct tlist *tlist_new(unsigned itemsize);
  60
  61 /* return the number of items/nodes in the list. */
  62 size_t tlist_getsize(struct tlist* t);
  63
  64 /* get the pointer to the data of idx'th item in the list.
  65    may return NULL if the idx is equal or greater than list size,
  66    you have to cast the return value to a pointer to the type
  67    that you inserted. */
  68 void *tlist_get(struct tlist* t, size_t idx);
  69
  70 /* insert value at position idx */
  71 /* returns 1 on success, 0 otherwise (i.e. not enough ram) */
  72 int tlist_insert(struct tlist* t, size_t idx, void* val);
  73
  74 /* append value to the end of the list */
  75 int tlist_append(struct tlist* t, void *val);
  76
  77 /* delete item as position idx */
  78 /* returns 1 on success, 0 otherwise (invalid index) */
  79 int tlist_delete(struct tlist *t, size_t idx);
  80 /* same as tlist_delete, but frees the stored pointer too - only use
  81    if you initialized the list with sizeof(pointer) */
  82 int tlist_delete_deep(struct tlist *t, size_t idx);
  83
  84 /* remove and free all items in list, but not the list itself. */
  85 void tlist_free_items(struct tlist *t);
  86 void tlist_free_items_deep(struct tlist *t);
  87
  88 /* free the list and all items in it - returns NULL so you can do
  89    mylist = tlist_free(mylist) instead of requiring 2 statements to
  90    have your list freed and nulled. */
  91 void* tlist_free(struct tlist *t);
  92 void* tlist_free_deep(struct tlist *t);
  93
  94 /* this is just a debug function that prints the node balance of
  95    the tree. it's not built-in by default because it prints stuff
  96    to stdout. */
  97 float tlist_getbalance(struct tlist *t);
  98
  99 #pragma RcB2 DEP "../src/tlist/*.c"
 100
 101 #endif
 102