Update zix

10 files changed, 179 insertions, 103 deletions

diff --git a/NEWS b/NEWS
index 24dc627..ef5a599 100644
--- a/NEWS
+++ b/NEWS
@@ -1,3 +1,9 @@
+lilv (0.24.13) unstable;
+
+  * Update zix tree
+
+ -- David Robillard <d@drobilla.net>  Mon, 11 Jan 2021 11:20:00 +0000
+
 lilv (0.24.12) stable;
 
   * Allow connecting ports to structures in Python
diff --git a/src/collections.c b/src/collections.c
index 1ee9ad1..fdaca93 100644
--- a/src/collections.c
+++ b/src/collections.c
@@ -26,13 +26,13 @@
 #include <stdint.h>
 
 int
-lilv_ptr_cmp(const void* a, const void* b, void* user_data)
+lilv_ptr_cmp(const void* a, const void* b, const void* user_data)
 {
   return (intptr_t)a - (intptr_t)b;
 }
 
 int
-lilv_resource_node_cmp(const void* a, const void* b, void* user_data)
+lilv_resource_node_cmp(const void* a, const void* b, const void* user_data)
 {
   const SordNode* an = ((const LilvNode*)a)->node;
   const SordNode* bn = ((const LilvNode*)b)->node;
diff --git a/src/lilv_config.h b/src/lilv_config.h
index d0e23c3..10231c5 100644
--- a/src/lilv_config.h
+++ b/src/lilv_config.h
@@ -29,7 +29,7 @@
 #define LILV_CONFIG_H
 
 // Define version unconditionally so a warning will catch a mismatch
-#define LILV_VERSION "0.24.12"
+#define LILV_VERSION "0.24.13"
 
 #if !defined(LILV_NO_DEFAULT_CONFIG)
 
diff --git a/src/lilv_internal.h b/src/lilv_internal.h
index b8089c5..12b56de 100644
--- a/src/lilv_internal.h
+++ b/src/lilv_internal.h
@@ -351,16 +351,16 @@ LilvNode*
 lilv_node_new_from_node(LilvWorld* world, const SordNode* node);
 
 int
-lilv_header_compare_by_uri(const void* a, const void* b, void* user_data);
+lilv_header_compare_by_uri(const void* a, const void* b, const void* user_data);
 
 int
-lilv_lib_compare(const void* a, const void* b, void* user_data);
+lilv_lib_compare(const void* a, const void* b, const void* user_data);
 
 int
-lilv_ptr_cmp(const void* a, const void* b, void* user_data);
+lilv_ptr_cmp(const void* a, const void* b, const void* user_data);
 
 int
-lilv_resource_node_cmp(const void* a, const void* b, void* user_data);
+lilv_resource_node_cmp(const void* a, const void* b, const void* user_data);
 
 static inline int
 lilv_version_cmp(const LilvVersion* a, const LilvVersion* b)
diff --git a/src/state.c b/src/state.c
index 684350a..b74cd7a 100644
--- a/src/state.c
+++ b/src/state.c
@@ -81,13 +81,13 @@ struct LilvStateImpl {
 };
 
 static int
-abs_cmp(const void* a, const void* b, void* user_data)
+abs_cmp(const void* a, const void* b, const void* user_data)
 {
   return strcmp(((const PathMap*)a)->abs, ((const PathMap*)b)->abs);
 }
 
 static int
-rel_cmp(const void* a, const void* b, void* user_data)
+rel_cmp(const void* a, const void* b, const void* user_data)
 {
   return strcmp(((const PathMap*)a)->rel, ((const PathMap*)b)->rel);
 }
diff --git a/src/world.c b/src/world.c
index 04bbbf7..9020ce7 100644
--- a/src/world.c
+++ b/src/world.c
@@ -356,7 +356,7 @@ lilv_world_blank_node_prefix(LilvWorld* world)
 
 /** Comparator for sequences (e.g. world->plugins). */
 int
-lilv_header_compare_by_uri(const void* a, const void* b, void* user_data)
+lilv_header_compare_by_uri(const void* a, const void* b, const void* user_data)
 {
   const struct LilvHeader* const header_a = (const struct LilvHeader*)a;
   const struct LilvHeader* const header_b = (const struct LilvHeader*)b;
@@ -372,7 +372,7 @@ lilv_header_compare_by_uri(const void* a, const void* b, void* user_data)
    consequently different contents (mainly plugins).
  */
 int
-lilv_lib_compare(const void* a, const void* b, void* user_data)
+lilv_lib_compare(const void* a, const void* b, const void* user_data)
 {
   const LilvLib* const lib_a = (const LilvLib*)a;
   const LilvLib* const lib_b = (const LilvLib*)b;
diff --git a/src/zix/common.h b/src/zix/common.h
index 51683c4..d47586c 100644
--- a/src/zix/common.h
+++ b/src/zix/common.h
@@ -1,5 +1,5 @@
 /*
-  Copyright 2016 David Robillard <d@drobilla.net>
+  Copyright 2016-2020 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -17,39 +17,65 @@
 #ifndef ZIX_COMMON_H
 #define ZIX_COMMON_H
 
+#include <stdbool.h>
+
 /**
    @addtogroup zix
    @{
 */
 
 /** @cond */
-#ifdef ZIX_SHARED
-#  ifdef _WIN32
-#    define ZIX_LIB_IMPORT __declspec(dllimport)
-#    define ZIX_LIB_EXPORT __declspec(dllexport)
-#  else
-#    define ZIX_LIB_IMPORT __attribute__((visibility("default")))
-#    define ZIX_LIB_EXPORT __attribute__((visibility("default")))
-#  endif
-#  ifdef ZIX_INTERNAL
-#    define ZIX_API ZIX_LIB_EXPORT
-#  else
-#    define ZIX_API ZIX_LIB_IMPORT
-#  endif
-#  define ZIX_PRIVATE static
-#elif defined(ZIX_INLINE)
-#  define ZIX_API static inline
-#  define ZIX_PRIVATE static inline
+#if defined(_WIN32) && !defined(ZIX_STATIC) && defined(ZIX_INTERNAL)
+#  define ZIX_API __declspec(dllexport)
+#elif defined(_WIN32) && !defined(ZIX_STATIC)
+#  define ZIX_API __declspec(dllimport)
+#elif defined(__GNUC__)
+#  define ZIX_API __attribute__((visibility("default")))
 #else
 #  define ZIX_API
-#  define ZIX_PRIVATE static
 #endif
+
+#ifdef __GNUC__
+#  define ZIX_PURE_FUNC __attribute__((pure))
+#  define ZIX_CONST_FUNC __attribute__((const))
+#  define ZIX_MALLOC_FUNC __attribute__((malloc))
+#else
+#  define ZIX_PURE_FUNC
+#  define ZIX_CONST_FUNC
+#  define ZIX_MALLOC_FUNC
+#endif
+
+#define ZIX_PURE_API \
+  ZIX_API            \
+  ZIX_PURE_FUNC
+
+#define ZIX_CONST_API \
+  ZIX_API             \
+  ZIX_CONST_FUNC
+
+#define ZIX_MALLOC_API \
+  ZIX_API              \
+  ZIX_MALLOC_FUNC
+
 /** @endcond */
 
 #ifdef __cplusplus
 extern "C" {
+#endif
+
+#ifdef __GNUC__
+#  define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1)))
 #else
-#  include <stdbool.h>
+#  define ZIX_LOG_FUNC(fmt, arg1)
+#endif
+
+// Unused parameter macro to suppresses warnings and make it impossible to use
+#if defined(__cplusplus)
+#  define ZIX_UNUSED(name)
+#elif defined(__GNUC__)
+#  define ZIX_UNUSED(name) name##_unused __attribute__((__unused__))
+#else
+#  define ZIX_UNUSED(name) name
 #endif
 
 typedef enum {
@@ -62,10 +88,34 @@ typedef enum {
   ZIX_STATUS_BAD_PERMS
 } ZixStatus;
 
+static inline const char*
+zix_strerror(const ZixStatus status)
+{
+  switch (status) {
+  case ZIX_STATUS_SUCCESS:
+    return "Success";
+  case ZIX_STATUS_ERROR:
+    return "Unknown error";
+  case ZIX_STATUS_NO_MEM:
+    return "Out of memory";
+  case ZIX_STATUS_NOT_FOUND:
+    return "Not found";
+  case ZIX_STATUS_EXISTS:
+    return "Exists";
+  case ZIX_STATUS_BAD_ARG:
+    return "Bad argument";
+  case ZIX_STATUS_BAD_PERMS:
+    return "Bad permissions";
+  }
+  return "Unknown error";
+}
+
 /**
    Function for comparing two elements.
 */
-typedef int (*ZixComparator)(const void* a, const void* b, void* user_data);
+typedef int (*ZixComparator)(const void* a,
+                             const void* b,
+                             const void* user_data);
 
 /**
    Function for testing equality of two elements.
diff --git a/src/zix/tree.c b/src/zix/tree.c
index 658cafc..9faf13c 100644
--- a/src/zix/tree.c
+++ b/src/zix/tree.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011-2019 David Robillard <d@drobilla.net>
+  Copyright 2011-2020 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -15,10 +15,10 @@
 */
 
 #include "zix/tree.h"
+
 #include "zix/common.h"
 
 #include <assert.h>
-#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -38,7 +38,7 @@ struct ZixTreeNodeImpl {
   struct ZixTreeNodeImpl* left;
   struct ZixTreeNodeImpl* right;
   struct ZixTreeNodeImpl* parent;
-  int_fast8_t             balance;
+  int                     balance;
 };
 
 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
@@ -65,11 +65,11 @@ struct ZixTreeNodeImpl {
 #  define DEBUG_PRINTF(fmt, ...)
 #endif
 
-ZIX_API ZixTree*
-        zix_tree_new(bool           allow_duplicates,
-                     ZixComparator  cmp,
-                     void*          cmp_data,
-                     ZixDestroyFunc destroy)
+ZixTree*
+zix_tree_new(bool           allow_duplicates,
+             ZixComparator  cmp,
+             void*          cmp_data,
+             ZixDestroyFunc destroy)
 {
   ZixTree* t          = (ZixTree*)malloc(sizeof(ZixTree));
   t->root             = NULL;
@@ -81,7 +81,7 @@ ZIX_API ZixTree*
   return t;
 }
 
-ZIX_PRIVATE void
+static void
 zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
 {
   if (n) {
@@ -94,7 +94,7 @@ zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
   }
 }
 
-ZIX_API void
+void
 zix_tree_free(ZixTree* t)
 {
   if (t) {
@@ -103,13 +103,13 @@ zix_tree_free(ZixTree* t)
   }
 }
 
-ZIX_API size_t
+size_t
 zix_tree_size(const ZixTree* t)
 {
   return t->size;
 }
 
-ZIX_PRIVATE void
+static void
 rotate(ZixTreeNode* p, ZixTreeNode* q)
 {
   assert(q->parent == p);
@@ -153,8 +153,8 @@ rotate(ZixTreeNode* p, ZixTreeNode* q)
  *     / \        / \
  *    B   C      A   B
  */
-ZIX_PRIVATE ZixTreeNode*
-            rotate_left(ZixTreeNode* p, int* height_change)
+static ZixTreeNode*
+rotate_left(ZixTreeNode* p, int* height_change)
 {
   ZixTreeNode* const q = p->right;
   *height_change       = (q->balance == 0) ? 0 : -1;
@@ -186,8 +186,8 @@ ZIX_PRIVATE ZixTreeNode*
  *  A   B          B   C
  *
  */
-ZIX_PRIVATE ZixTreeNode*
-            rotate_right(ZixTreeNode* p, int* height_change)
+static ZixTreeNode*
+rotate_right(ZixTreeNode* p, int* height_change)
 {
   ZixTreeNode* const q = p->left;
   *height_change       = (q->balance == 0) ? 0 : -1;
@@ -221,8 +221,8 @@ ZIX_PRIVATE ZixTreeNode*
  *    B   C
  *
  */
-ZIX_PRIVATE ZixTreeNode*
-            rotate_left_right(ZixTreeNode* p, int* height_change)
+static ZixTreeNode*
+rotate_left_right(ZixTreeNode* p, int* height_change)
 {
   ZixTreeNode* const q = p->left;
   ZixTreeNode* const r = q->right;
@@ -268,8 +268,8 @@ ZIX_PRIVATE ZixTreeNode*
  *  B   C
  *
  */
-ZIX_PRIVATE ZixTreeNode*
-            rotate_right_left(ZixTreeNode* p, int* height_change)
+static ZixTreeNode*
+rotate_right_left(ZixTreeNode* p, int* height_change)
 {
   ZixTreeNode* const q = p->right;
   ZixTreeNode* const r = q->left;
@@ -304,7 +304,7 @@ ZIX_PRIVATE ZixTreeNode*
   return r;
 }
 
-ZIX_PRIVATE ZixTreeNode*
+static ZixTreeNode*
 zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
 {
 #ifdef ZIX_TREE_HYPER_VERIFY
@@ -341,7 +341,7 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
   return replacement;
 }
 
-ZIX_API ZixStatus
+ZixStatus
 zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
 {
   DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
@@ -355,9 +355,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
     cmp = t->cmp(e, n->data, t->cmp_data);
     if (cmp < 0) {
       n = n->left;
-    } else if (cmp > 0) {
-      n = n->right;
-    } else if (t->allow_duplicates) {
+    } else if (cmp > 0 || t->allow_duplicates) {
       n = n->right;
     } else {
       if (ti) {
@@ -440,13 +438,13 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
   return ZIX_STATUS_SUCCESS;
 }
 
-ZIX_API ZixStatus
+ZixStatus
 zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
 {
   ZixTreeNode* const n          = ti;
   ZixTreeNode**      pp         = NULL;      // parent pointer
   ZixTreeNode*       to_balance = n->parent; // lowest node to balance
-  int8_t             d_balance  = 0;         // delta(balance) for n->parent
+  int                d_balance  = 0;         // delta(balance) for n->parent
 
   DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
 
@@ -484,6 +482,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
       to_balance    = n->parent;
       height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
     }
+
   } else if (!n->left) {
     // Replace n with right (only) child
     if (pp) {
@@ -494,6 +493,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
     }
     n->right->parent = n->parent;
     height_change    = -1;
+
   } else if (!n->right) {
     // Replace n with left (only) child
     if (pp) {
@@ -504,6 +504,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
     }
     n->left->parent = n->parent;
     height_change   = -1;
+
   } else {
     // Replace n with in-order successor (leftmost child of right subtree)
     ZixTreeNode* replace = n->right;
@@ -543,6 +544,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
       assert(t->root == n);
       t->root = replace;
     }
+
     replace->parent = n->parent;
     replace->left   = n->left;
     n->left->parent = replace;
@@ -596,7 +598,7 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
   return ZIX_STATUS_SUCCESS;
 }
 
-ZIX_API ZixStatus
+ZixStatus
 zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
 {
   ZixTreeNode* n = t->root;
@@ -617,14 +619,14 @@ zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
   return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
 }
 
-ZIX_API void*
+void*
 zix_tree_get(const ZixTreeIter* ti)
 {
   return ti ? ti->data : NULL;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_begin(ZixTree* t)
+ZixTreeIter*
+zix_tree_begin(ZixTree* t)
 {
   if (!t->root) {
     return NULL;
@@ -634,17 +636,18 @@ ZIX_API ZixTreeIter*
   while (n->left) {
     n = n->left;
   }
+
   return n;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_end(ZixTree* t)
+ZixTreeIter*
+zix_tree_end(ZixTree* ZIX_UNUSED(t))
 {
   return NULL;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_rbegin(ZixTree* t)
+ZixTreeIter*
+zix_tree_rbegin(ZixTree* t)
 {
   if (!t->root) {
     return NULL;
@@ -654,29 +657,30 @@ ZIX_API ZixTreeIter*
   while (n->right) {
     n = n->right;
   }
+
   return n;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_rend(ZixTree* t)
+ZixTreeIter*
+zix_tree_rend(ZixTree* ZIX_UNUSED(t))
 {
   return NULL;
 }
 
-ZIX_API bool
+bool
 zix_tree_iter_is_end(const ZixTreeIter* i)
 {
   return !i;
 }
 
-ZIX_API bool
+bool
 zix_tree_iter_is_rend(const ZixTreeIter* i)
 {
   return !i;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_iter_next(ZixTreeIter* i)
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i)
 {
   if (!i) {
     return NULL;
@@ -698,8 +702,8 @@ ZIX_API ZixTreeIter*
   return i;
 }
 
-ZIX_API ZixTreeIter*
-        zix_tree_iter_prev(ZixTreeIter* i)
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i)
 {
   if (!i) {
     return NULL;
@@ -710,6 +714,7 @@ ZIX_API ZixTreeIter*
     while (i->right) {
       i = i->right;
     }
+
   } else {
     while (i->parent && i->parent->left == i) { // i is a left child
       i = i->parent;
diff --git a/src/zix/tree.h b/src/zix/tree.h
index 15ad105..a2d5fe7 100644
--- a/src/zix/tree.h
+++ b/src/zix/tree.h
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011-2019 David Robillard <d@drobilla.net>
+  Copyright 2011-2020 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -39,103 +39,118 @@ extern "C" {
 typedef struct ZixTreeImpl ZixTree;
 
 /**
-   An iterator over a ZixTree.
+   An iterator over a @ref ZixTree.
 */
 typedef struct ZixTreeNodeImpl ZixTreeIter;
 
 /**
    Create a new (empty) tree.
 */
-ZIX_API ZixTree*
-        zix_tree_new(bool           allow_duplicates,
-                     ZixComparator  cmp,
-                     void*          cmp_data,
-                     ZixDestroyFunc destroy);
+ZIX_API
+ZixTree*
+zix_tree_new(bool           allow_duplicates,
+             ZixComparator  cmp,
+             void*          cmp_data,
+             ZixDestroyFunc destroy);
 
 /**
    Free `t`.
 */
-ZIX_API void
+ZIX_API
+void
 zix_tree_free(ZixTree* t);
 
 /**
    Return the number of elements in `t`.
 */
-ZIX_API size_t
+ZIX_PURE_API
+size_t
 zix_tree_size(const ZixTree* t);
 
 /**
    Insert the element `e` into `t` and point `ti` at the new element.
 */
-ZIX_API ZixStatus
+ZIX_API
+ZixStatus
 zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
 
 /**
    Remove the item pointed at by `ti` from `t`.
 */
-ZIX_API ZixStatus
+ZIX_API
+ZixStatus
 zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
 
 /**
    Set `ti` to an element equal to `e` in `t`.
    If no such item exists, `ti` is set to NULL.
 */
-ZIX_API ZixStatus
+ZIX_API
+ZixStatus
 zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
 
 /**
    Return the data associated with the given tree item.
 */
-ZIX_API void*
+ZIX_PURE_API
+void*
 zix_tree_get(const ZixTreeIter* ti);
 
 /**
    Return an iterator to the first (smallest) element in `t`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_begin(ZixTree* t);
+ZIX_PURE_API
+ZixTreeIter*
+zix_tree_begin(ZixTree* t);
 
 /**
    Return an iterator the the element one past the last element in `t`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_end(ZixTree* t);
+ZIX_CONST_API
+ZixTreeIter*
+zix_tree_end(ZixTree* t);
 
 /**
    Return true iff `i` is an iterator to the end of its tree.
 */
-ZIX_API bool
+ZIX_CONST_API
+bool
 zix_tree_iter_is_end(const ZixTreeIter* i);
 
 /**
    Return an iterator to the last (largest) element in `t`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_rbegin(ZixTree* t);
+ZIX_PURE_API
+ZixTreeIter*
+zix_tree_rbegin(ZixTree* t);
 
 /**
    Return an iterator the the element one before the first element in `t`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_rend(ZixTree* t);
+ZIX_CONST_API
+ZixTreeIter*
+zix_tree_rend(ZixTree* t);
 
 /**
    Return true iff `i` is an iterator to the reverse end of its tree.
 */
-ZIX_API bool
+ZIX_CONST_API
+bool
 zix_tree_iter_is_rend(const ZixTreeIter* i);
 
 /**
    Return an iterator that points to the element one past `i`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_iter_next(ZixTreeIter* i);
+ZIX_PURE_API
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i);
 
 /**
    Return an iterator that points to the element one before `i`.
 */
-ZIX_API ZixTreeIter*
-        zix_tree_iter_prev(ZixTreeIter* i);
+ZIX_PURE_API
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i);
 
 /**
    @}
diff --git a/wscript b/wscript
index 6f3c6a4..f95c88b 100644
--- a/wscript
+++ b/wscript
@@ -12,7 +12,7 @@ from waflib.extras import autowaf
 # major increment <=> incompatible changes
 # minor increment <=> compatible changes (additions)
 # micro increment <=> no interface changes
-LILV_VERSION       = '0.24.12'
+LILV_VERSION       = '0.24.13'
 LILV_MAJOR_VERSION = '0'
 
 # Mandatory waf variables