////////////////////////////// * Common Headers * ////////////////////////////// /* The internal bit keys are represented as unsigned integers so we import the standard integer definitions. */ #include #include /* These next 3 lines are just for generating the examples with CMake and can be omitted. */ #ifndef RBT_NO_CMAKE # include "cmake_config.h" #endif //RBT_NO_CMAKE /* Import common headers. Uncomment the second line to enable debugging messages. */ #include "common.h" // #define RBT_DEBUG 1 #include "debug.h" ////////////////////////////////// * key.h * /////////////////////////////////// /* Now it is time to define the internal key representation. `RBT_KEY_H_PREFIX_` determines the function name prefix that will be used for all of the resulting key functions. `RBT_PIN_T` determines the size of the unsigned ints in the key arrays. Here we use unsigned 8-bit (1-byte) integers as they will align perfectly with our string key values (which are arrays of chars). This alignment is not necessary. You can use 32-bit unsigned ints as well, and it may even be faster on some systems. For large tree trees, however, misalignment will lead to some wasted space because a node that holds 1 char will still use a 32-bit (4-byte) int. The choice depends on intended usage but for most cases it is trivial. */ #define RBT_KEY_H_PREFIX_ string_to_const_string_ #define RBT_PIN_T uint_fast8_t /* `RBT_KEY_SIZE_T` determines the type of variable that stores key lengths. For example, if you have a fixed-length key such as a 32-bit integer or a 4-byte struct, then the longest key will be 32 bits. An unsigned char's maximum value is 255, which would therefore suffice. In this case, the keys are string values of arbitrary length. They may therefore be any size, but we must select a fixed value for the key size type. Here we choose (unsigned!) 32-bit integers. The maximum value such an integer may hold is 4294967295, so our key length is therefore practically limited to 4294967295 bits, or 536870911 bytes. They key strings may therefore be over 536 *million* characters long. That should be enough. `RBT_KEY_SIZE_T_FORMAT` is simply the printf formatter required to print values of type `RBT_KEY_SIZE_T`. "%u" is what we use for unsigned integers. */ #define RBT_KEY_SIZE_T uint_fast32_t #define RBT_KEY_SIZE_T_FORMAT PRIuFAST32 /* Finally we include `key.h`, which will define the appropriate functions based on these macros. */ #include "key.h" ////////////////////////////////// * node.h * ////////////////////////////////// /* Next it is time to define the tree node type. These will hold keys and values, which is why they are defined after the keys above. `RBT_NODE_H_PREFIX_` serves the same purpose for the node functions as `RBT_KEY_H_PREFIX_` does for the key functions. Here we make them the same because we are only dealing with one tree type, but they could be different. This is useful when you want to use the same key type in different trees, e.g. instead of `string_to_const_string_`, you may use the key prefix `uint8_` to indicate generic 8-bit keys. */ #define RBT_NODE_H_PREFIX_ string_to_const_string_ /* `RBT_VALUE_TYPE` determines the type of value to store in the node. Here we store pointers to constrant strings. `RBT_VALUE_NULL` determines our null value. A node with this value is considered empty. For strings, we use the `NULL` pointer. `RBT_VALUE_IS_EQUAL` is a function for comparing node values. It must return 0 if the values are to be considered different and non-zero otherwise. Among other things, this is used to determine if the node is empty by comparing the value to the null value. Note that the simple `==` comparison suffices for values of `const char *` because of the way constant strings are store (pointers are re-used and thus comparable) . If we were storing allocated strings then we would need to use `strcmp`, because the pointers could be different. */ #define RBT_VALUE_T const char * #define RBT_VALUE_NULL NULL #define RBT_VALUE_IS_EQUAL(a, b) (a == b) /* `RBT_VALUE_COPY` is a function for copying the values. Again, because we are dealing with constant strings we can simply copy the pointer. Allocated strings would require an invocation of `strcpy` to copy the data from one pointer to another. If we used a simple assignment, the original pointer would be lost, which would lead to a memory leak, and both nodes would then point to the same area of memory. */ #define RBT_VALUE_COPY(a, b, fail) a = b /* `RBT_VALUE_FREE` is used to free the value when the node is freed. Here it does nothing because constant strings are not allocated, but if the value were a pointer to allocated memory then we would use `free(val)`. This function allows for more complicated management of values that are no longer used, e.g. removing directories from inotify watchlists, etc. */ #define RBT_VALUE_FREE(val) /* `RBT_VALUE_FPRINT` is used for printing trees. It should only print the value if it is not equal to the null value. */ #define RBT_VALUE_FPRINT(fd, val) \ do \ { \ if (val != NULL) \ { \ fprintf(fd, "%s", val); \ } \ } while(0) /* Finally we include `node.h` to define the node functions and `traverse_with_key.h` for traversal functions. We could optionally define `RBT_TRAVERSE_H_PREFIX_` before including the latter to customize the function names but this is only necessary when creating different traversal types, e.g. for different fixed-length keys. */ #include "node.h" #include "traverse_with_key.h" //////////////////////////////// * wrapper.h * ///////////////////////////////// /* The final section of the header provides a way to automatically convert strings to keys. `RBT_WRAPPER_H_PREFIX_` sets the prefix for wrapper function names. Again, we choose the same prefix as before. `RBT_KEY_T` is the key value type. Here we are using dynamic strings, so the key type will be a pointer to an array of chars. `RBT_KEY_SIZE_FIXED` is set to 0 to indicate that the key length is variable. If out key type had been an `int` then we could have used `sizeof(int)`, for example. The same would work with keys of type struct, for example. */ #define RBT_WRAPPER_H_PREFIX_ string_to_const_string_ #define RBT_KEY_T char * #define RBT_KEY_SIZE_FIXED 0 /* `RBT_KEY_COUNT_BITS` is a function to return the length **in bits** of the key. Here we use `strlen` because we do not care about the trailing `\0` at the end of our strings. This has a real consequence for internal key representations. If the terminating null character is included, then "foo" is not a radix of "foobar" because internally foo is represented as "foo\0", so the tree will include a node for "foo" with two child nodes: one for "\0" and one for "bar\0". Without the terminating null character, there will only be two nodes: "foo" and a child node "bar". The "+1 variant will include the terminating null character. */ #define RBT_KEY_COUNT_BITS(key) (strlen(key) * BITS_PER_BYTE) // #define RBT_KEY_COUNT_BITS(key) ((strlen(key) + 1) * BITS_PER_BYTE) /* `RBT_KEY_PTR` is a function to return a pointer to the underlying data so that the bytes can be copied from the key to the underlying array and vice versa. For a string value the key is already a pointer. For simple non-pointer types the `&` operator would be used. */ #define RBT_KEY_PTR(key) (key) /* `RBT_KEY_FPRINT` is used to provide a way to print the key. Here the length (in bytes) is used with `%.*s` because the strings are not null-terminated. The length thus provides a way to know when the end of the string has been reached. If we had used null terminators then `%s` could have been used and the length could have been ignored. */ #define RBT_KEY_FPRINT(fd, key, len) fprintf(fd, "%.*s", (int) len, key); /* Finally we include `wrapper.h` after these definitions to defined the wrapper functions. */ #include "wrapper.h" /* Note that the wrapper defines how our key types are converted to and from the internal key representation specified by the definitions preceding `key.h` above. It is important to understand the distinction between the two. Internal keys are arrays of bytes (actually, bits). Anything data type that can be represented as a continuous array of bytes can be converted to an internal key, and this is precisely what the functions in `wrapper.h` do, so that these key types can be used to transparently access the tree. */