README.adoc

   1 = Generic Data Structures
   2
   3 A set of Data Structures for the C programming language.
   4
   5 It includes:
   6
   7 * Vector
   8 * LinkedList
   9 * AVLTree
  10 * Graph
  11 * Dictionary
  12 * Heap
  13 * Stack
  14 * Queue
  15
  16 These structures are "generic" in the sense that they can store any kind
  17 of data type, by only knowing the size of it.
  18
  19 [source,c]
  20 ----
  21 int main(){
  22     Vector *vec = vector_init(sizeof(int), compare_int);
  23     int tmp = 12;
  24     vector_append(vec, &tmp);
  25     tmp = 3;
  26     vector_append(vec, &tmp);
  27     vector_free(vec);
  28     return 0;
  29 }
  30 ----
  31
  32 In the example above, we create a vector of integers.
  33 To do so, we pass sizeof(int) as a parameter when initializing it.
  34 When calling ``vector_append``, the function copies the size of an integer
  35 from the address of the variable 'tmp' into the vector.
  36 Note that these structures store values, not references (i.e. they don't
  37 store the pointer we pass, but rather they copy the value that's inside)
  38
  39 Tip: you can use https://gcc.gnu.org/onlinedocs/gcc/Compound-Literals.html[compound literals] to avoid having to declare a variable.
  40 [source,c]
  41 ----
  42 vector_append(vec, &(int){12});
  43 vector_append(vec, &(int){3});
  44 ----
  45
  46 == How are elements compared?
  47 Since we store "generic" data, there must be a way to compare it.
  48 These structures require a comparator function to be passed as a
  49 parameter when they are initialized.
  50 That function must be like this:
  51 [source,c]
  52 ----
  53 int func_name(const void* e_1, const void* e_2);
  54 ----
  55 And it must return:
  56
  57 * -1 if e_1 is < than e_2
  58 * 0     if e_1 is == than e_2
  59 * 1 if e_1 is > than e_2
  60
  61 For example:
  62 [source,c]
  63 ----
  64 int compare_int(const void* e_1, const void* e_2){
  65     int i_1 = * (int*) e_1;
  66     int i_2 = * (int*) e_2;
  67     return i_1 - i_2;
  68 }
  69
  70 int main(){
  71     int a = 1;
  72     int b = 2;
  73     assert(compare_int(&a, &b) < 0);
  74     return 0;
  75 }
  76 ----
  77
  78 The header file *comparator.h* defines functions to compare the most common data types (int, char, long, etc.)
  79
  80 [source,c]
  81 ----
  82 LinkedList *list = list_init(sizeof(char), compare_char); // This list stores chars
  83 ----
  84
  85 If you don't need to compare elements inside the structure you can use the ``compare_equal``, ``compare_lesser`` and ``compare_greater`` functions, which always return 0, -1, and 1 respectively.
  86
  87 == Destructors
  88 You can set a "destructor" function to perform additional cleanup.
  89 Say you have a Vector of char*, and you allocate it's elements using malloc.
  90 You can use the ``vector_set_destructor`` function, and pass the ``destroy_ptr`` function as a destructor for that vector.
  91 When freeing the vector or removing an element from it, that "destructor" function will be called on that element(s).
  92 You can also write your own destructors. See ``/example/destructors.c``
  93
  94 *Note:* To remove an element without calling the destructor on that element you can use the pop function instead.
  95
  96 [source,c]
  97 ----
  98 // Signature
  99 void destructor_func(void *e); // e is a POINTER to the element to destroy
 100
 101 // Example: destroy a malloc'd pointer
 102 void destroy_ptr(void *e){
 103     if (e){
 104         void *ptr;
 105         memcpy(&ptr, e, sizeof(void*));
 106         free(ptr);
 107     }
 108 }
 109
 110 // Example: destroy a struct
 111 struct buffer {
 112     char *buf; // malloc'd
 113     size_t capacity;
 114     size_t size;
 115 };
 116
 117 void destroy_buffer(void *e){
 118     struct buffer *buffer = (struct buffer*) e;
 119     free(buffer->buf);
 120 }
 121 ----
 122
 123 == Building
 124 You can use the Makefile to build and install the library.
 125
 126 * ``make``: builds the library
 127 * ``make test``: builds and runs test programs
 128 * ``make install``: installs the library on the computer.
 129                   The default installation path is /usr/local, but it
 130                   can be overriden by defining INSTALL_PATH (e.g. ``make install INSTALL_PATH=~/.local``)
 131 * ``make uninstall``: removes the library from the computer. Remember to set INSTALL_PATH to the same value as in installation.
 132 * ``make doxygen``: Builds the doxygen documentation.
 133 * ``make clean``: Removes the binaries.
 134
 135 To use the library, just include the header(s) and add
 136 the ``-lGDS`` or ``-lGDS-static`` flags when compiling. The headers are installed in $(INSTALL_PATH)/include/GDS.
 137
 138 Example:
 139 [source,c]
 140 ----
 141 #include <GDS/GDS.h> // or #include <GDS/Vector.h>
 142
 143 int main(){
 144         Vector *v = vector_init(sizeof(int), compare_int);
 145         // ....
 146         vector_free(v);
 147         return 0;
 148 }
 149 ----
 150
 151 == Another example:
 152 [source,c]
 153 ----
 154 struct Person{
 155     int id;
 156     int age;
 157     char *name;
 158 };
 159
 160 int compare_person(const void* e_1, const void* e_2){
 161     struct Person p1 = * (struct Person*) e_1;
 162     struct Person p2 = * (struct Person*) e_2;
 163     return p1.id - p2.id;
 164 }
 165
 166 int main(){
 167     Vector *vector = vector_init(sizeof(struct Person), compare_person);
 168     vector_append(vector, &(struct Person){012345, 23, "My name"});
 169     vector_free(vector);
 170 }
 171 ----
 172