home.md

+Avl library
+===========
+
+Representation of data
+----------------------
+
+In computer science, an AVL tree is a self-balancing binary search tree,
+and it was the first such data structure to be invented. In an AVL tree,
+the heights of the two child sub-trees of any node differ by at most
+one.\
+Lookup, insertion, and deletion all take **O**(*log* n) time in both the
+average and worst cases, where *n* is the number of nodes in the tree
+prior to the operation.\
+Insertions and deletions may require the tree to be rebalanced by one or
+more tree rotations.
+
+The AVL tree is named after its two Soviet inventors, G.M.
+Adelson-Velskii and E.M. Landis, who published it in their 1962 paper
+"An algorithm for the organization of information."
+
+The balance factor of a node is the height of its left sub-tree minus
+the height of its right sub-tree (sometimes opposite) and a node with
+balance factor 1, 0, or −1 is considered balanced. A node with any other
+balance factor is considered unbalanced and requires rebalancing the
+tree. The balance factor is either stored directly at each node or
+computed from the heights of the sub-trees.
+
+Use of library
+--------------
+
+To be fully functional, a new tree need four pointer functions depending
+of data you want to store.
+
+### Data compare
+
+First of all, an AVL tree need tools to compare your data. Prototype of
+this function must be
+
+```c
+int data_cmp(void *a, void *b);
+```
+
+`a` and `b` are pointer to your data and function must return a positive
+if `a` is higher than `b`, negative if `a` is lesser than `b` or `0` if
+`a` is equal to `b`.\
+If your data is integer, then an example of `data_cmp` implementation
+could be:
+
+```c
+int data_cmp(void *a, void *b)
+{
+    return *((int *) a) - *((int *) b);
+}
+```
+
+If your data is a structure that contains a string key and an integer
+value and if you want to order it in case sensitive lexicographic order
+on string member, you can use the following example:
+
+```c
+struct _data {
+    char *key;
+    int  value;
+};
+
+int data_cmp(void *a, void *b)
+{
+    return strcmp((struct _data *) a)->key, ((struct _data *) b)->key);
+}
+```
+
+### Data print
+
+This function is mainly used for debug purpose. Its main goal is to
+print a data to `stdout` and will be called on each node in tree during
+the `print_tree` process.\
+Its prototype is the following:
+
+```c
+void data_print(void *d);
+```
+
+With the two previous type of data example, you can use the following
+implementation:
+
+```c
+// With integer data
+void data_print(void *d)
+{
+    printf("%d\n", *((int *) d));
+}
+
+// With struct _data
+void data_print(void *d)
+{
+    printf("\"%s\" => %d\n", ((struct _data *) d)->key, ((struct _data *) d)->value);
+}
+```
+
+### Data delete
+
+This function is used to correctly clean your memory after use. When you
+delete a node (or the complete tree), this function is applied to the
+specified node (or on each node of tree). Its prototype is the
+following:
+
+```c
+void data_delete(void *d)
+```
+
+With the previous type example, you can use the following
+implementation:
+
+```c
+// With integer data
+void data_delete(void *d)
+{
+    free(d);
+}
+
+// With struct _data
+void data_delete(void *d)
+{
+    if (d != NULL)
+        free(((struct _data *) d)->key);
+    free(d);
+}
+```
+
+#### Data copy
+
+This function is used to copy data in `get` function to extract the
+whole data from a tree. It takes three arguments:\
+a source pointer to data in tree, a destination pointer to external
+memory allocated for data and the size of the data.
+
+```c
+void data_copy(void *src, void *dst, size_t len);
+```
+
+Again, with the previous type definition, you can use the following
+implementation:
+
+```c
+// With integer
+void data_copy(void *src, void *dst, size_t len)
+{
+    memcpy(dst, src, len);
+}
+
+// With _data structure
+void data_copy(void *src, void *dst, size_t len)
+{
+    (void) len;
+    struct _data *src_t = (struct _data *) src;
+    struct _data *dst_t = (struct _data *) dst;
+    if (src_t != NULL && dst_t != NULL) {
+        dst_t->key = malloc((strlen(src_t->key) + 1) * sizeof(char));
+        if (dst_t->key != NULL)
+            strcpy(dst_t->key, src_t->key);
+        dst_t->value = src_t->value;
+    }
+}
+```
\ No newline at end of file