glib inlined into SameTime

git-svn-id: http://svn.miranda-ng.org/main/trunk@8685 1316c22d-e87f-b044-9b9b-93d7a3e3ba9c

1 files changed, 303 insertions, 0 deletions

diff --git a/protocols/Sametime/src/glib/gbsearcharray.h b/protocols/Sametime/src/glib/gbsearcharray.h
new file mode 100644
index 0000000000..1ad893c4ac
--- /dev/null
+++ b/protocols/Sametime/src/glib/gbsearcharray.h
@@ -0,0 +1,303 @@
+/* GBSearchArray - Binary Searchable Array implementation
+ * Copyright (C) 2000-2003 Tim Janik
+ *
+ * This software is provided "as is"; redistribution and modification
+ * is permitted, provided that the following disclaimer is retained.
+ *
+ * This software is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * In no event shall the authors or contributors be liable for any
+ * direct, indirect, incidental, special, exemplary, or consequential
+ * damages (including, but not limited to, procurement of substitute
+ * goods or services; loss of use, data, or profits; or business
+ * interruption) however caused and on any theory of liability, whether
+ * in contract, strict liability, or tort (including negligence or
+ * otherwise) arising in any way out of the use of this software, even
+ * if advised of the possibility of such damage.
+ */
+#ifndef __G_BSEARCH_ARRAY_H__
+#define __G_BSEARCH_ARRAY_H__
+
+#include <glib.h>
+#include <string.h>
+
+
+G_BEGIN_DECLS   /* c++ guards */
+
+/* this implementation is intended to be usable in third-party code
+ * simply by pasting the contents of this file. as such, the
+ * implementation needs to be self-contained within this file.
+ */
+
+/* convenience macro to avoid signed overflow for value comparisions */
+#define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) > (v2) ? +1 : (v1) == (v2) ? 0 : -1)
+
+
+/* --- typedefs --- */
+typedef gint  (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */
+                                      gconstpointer bsearch_node2);
+typedef enum
+{
+  G_BSEARCH_ARRAY_ALIGN_POWER2  = 1 << 0, /* align memory to power2 sizes */
+  G_BSEARCH_ARRAY_AUTO_SHRINK  = 1 << 1   /* shrink array upon removal */
+} GBSearchArrayFlags;
+
+
+/* --- structures --- */
+typedef struct
+{
+  guint               sizeof_node;
+  GBSearchCompareFunc cmp_nodes;
+  guint               flags;
+} GBSearchConfig;
+typedef union
+{
+  guint    n_nodes;
+  /*< private >*/
+  gpointer alignment_dummy1;
+  glong    alignment_dummy2;
+  gdouble  alignment_dummy3;
+} GBSearchArray;
+
+
+/* --- public API --- */
+static inline GBSearchArray*    g_bsearch_array_create    (const GBSearchConfig *bconfig);
+static inline gpointer          g_bsearch_array_get_nth   (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           guint                 nth);
+static inline guint             g_bsearch_array_get_index (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           gconstpointer         node_in_array);
+static inline GBSearchArray*    g_bsearch_array_remove    (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           guint                 index_);
+/* provide uninitialized space at index for node insertion */
+static inline GBSearchArray*    g_bsearch_array_grow      (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           guint                 index);
+/* insert key_node into array if it does not exist, otherwise do nothing */
+static inline GBSearchArray*    g_bsearch_array_insert    (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           gconstpointer         key_node);
+/* insert key_node into array if it does not exist,
+ * otherwise replace the existing node's contents with key_node
+ */
+static inline GBSearchArray*    g_bsearch_array_replace   (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig,
+                                                           gconstpointer         key_node);
+static inline void              g_bsearch_array_free      (GBSearchArray        *barray,
+                                                           const GBSearchConfig *bconfig);
+#define g_bsearch_array_get_n_nodes(barray)     (((GBSearchArray*) (barray))->n_nodes)
+
+/* g_bsearch_array_lookup():
+ * return NULL or exact match node
+ */
+#define g_bsearch_array_lookup(barray, bconfig, key_node)       \
+    g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 0)
+
+/* g_bsearch_array_lookup_sibling():
+ * return NULL for barray->n_nodes==0, otherwise return the
+ * exact match node, or, if there's no such node, return the
+ * node last visited, which is pretty close to an exact match
+ * (will be one off into either direction).
+ */
+#define g_bsearch_array_lookup_sibling(barray, bconfig, key_node)       \
+    g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 1)
+
+/* g_bsearch_array_lookup_insertion():
+ * return NULL for barray->n_nodes==0 or exact match, otherwise
+ * return the node where key_node should be inserted (may be one
+ * after end, i.e. g_bsearch_array_get_index(result) <= barray->n_nodes).
+ */
+#define g_bsearch_array_lookup_insertion(barray, bconfig, key_node)     \
+    g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 2)
+
+
+/* --- implementation --- */
+/* helper macro to cut down realloc()s */
+#ifdef  DISABLE_MEM_POOLS
+#define G_BSEARCH_UPPER_POWER2(n)       (n)
+#else   /* !DISABLE_MEM_POOLS */
+#define G_BSEARCH_UPPER_POWER2(n)       ((n) ? 1 << g_bit_storage ((n) - 1) : 0)
+#endif  /* !DISABLE_MEM_POOLS */
+#define G_BSEARCH_ARRAY_NODES(barray)    (((guint8*) (barray)) + sizeof (GBSearchArray))
+static inline GBSearchArray*
+g_bsearch_array_create (const GBSearchConfig *bconfig)
+{
+  GBSearchArray *barray;
+  guint size;
+
+  g_return_val_if_fail (bconfig != NULL, NULL);
+
+  size = sizeof (GBSearchArray) + bconfig->sizeof_node;
+  if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)
+    size = G_BSEARCH_UPPER_POWER2 (size);
+  barray = (GBSearchArray *) g_malloc (size);
+  memset (barray, 0, sizeof (GBSearchArray));
+
+  return barray;
+}
+static inline gpointer
+g_bsearch_array_lookup_fuzzy (GBSearchArray             *barray,
+                              const GBSearchConfig      *bconfig,
+                              gconstpointer              key_node,
+                              const guint                sibling_or_after);
+static inline gpointer
+g_bsearch_array_lookup_fuzzy (GBSearchArray        *barray,
+                              const GBSearchConfig *bconfig,
+                              gconstpointer         key_node,
+                              const guint           sibling_or_after)
+{
+  GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes;
+  guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray);
+  guint n_nodes = barray->n_nodes, offs = 0;
+  guint sizeof_node = bconfig->sizeof_node;
+  gint cmp = 0;
+
+  while (offs < n_nodes)
+    {
+      guint i = (offs + n_nodes) >> 1;
+
+      check = nodes + i * sizeof_node;
+      cmp = cmp_nodes (key_node, check);
+      if (cmp == 0)
+        return sibling_or_after > 1 ? NULL : check;
+      else if (cmp < 0)
+        n_nodes = i;
+      else /* (cmp > 0) */
+        offs = i + 1;
+    }
+
+  /* check is last mismatch, cmp > 0 indicates greater key */
+  return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check;
+}
+static inline gpointer
+g_bsearch_array_get_nth (GBSearchArray        *barray,
+                         const GBSearchConfig *bconfig,
+                         guint                 nth)
+{
+  return (G_LIKELY (nth < barray->n_nodes) ?
+          G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node :
+          NULL);
+}
+static inline guint
+g_bsearch_array_get_index (GBSearchArray        *barray,
+                           const GBSearchConfig *bconfig,
+                           gconstpointer         node_in_array)
+{
+  guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray);
+
+  g_return_val_if_fail (node_in_array != NULL, barray->n_nodes);
+
+  distance /= bconfig->sizeof_node;
+
+  return MIN (distance, barray->n_nodes + 1); /* may return one after end */
+}
+static inline GBSearchArray*
+g_bsearch_array_grow (GBSearchArray        *barray,
+                      const GBSearchConfig *bconfig,
+                      guint                 index_)
+{
+  guint old_size = barray->n_nodes * bconfig->sizeof_node;
+  guint new_size = old_size + bconfig->sizeof_node;
+  guint8 *node;
+
+  g_return_val_if_fail (index_ <= barray->n_nodes, NULL);
+
+  if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
+    {
+      new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
+      old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
+      if (old_size != new_size)
+        barray = (GBSearchArray *) g_realloc (barray, new_size);
+    }
+  else
+    barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
+  node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
+  g_memmove (node + bconfig->sizeof_node, node, (barray->n_nodes - index_) * bconfig->sizeof_node);
+  barray->n_nodes += 1;
+  return barray;
+}
+static inline GBSearchArray*
+g_bsearch_array_insert (GBSearchArray        *barray,
+                        const GBSearchConfig *bconfig,
+                        gconstpointer         key_node)
+{
+  guint8 *node;
+
+  if (G_UNLIKELY (!barray->n_nodes))
+    {
+      barray = g_bsearch_array_grow (barray, bconfig, 0);
+      node = G_BSEARCH_ARRAY_NODES (barray);
+    }
+  else
+    {
+      node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node);
+      if (G_LIKELY (node))
+        {
+          guint index_ = g_bsearch_array_get_index (barray, bconfig, node);
+
+          /* grow and insert */
+          barray = g_bsearch_array_grow (barray, bconfig, index_);
+          node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
+        }
+      else /* no insertion needed, node already there */
+        return barray;
+    }
+  memcpy (node, key_node, bconfig->sizeof_node);
+  return barray;
+}
+static inline GBSearchArray*
+g_bsearch_array_replace (GBSearchArray        *barray,
+                         const GBSearchConfig *bconfig,
+                         gconstpointer         key_node)
+{
+  guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node);
+  if (G_LIKELY (node))  /* expected path */
+    memcpy (node, key_node, bconfig->sizeof_node);
+  else                  /* revert to insertion */
+    barray = g_bsearch_array_insert (barray, bconfig, key_node);
+  return barray;
+}
+static inline GBSearchArray*
+g_bsearch_array_remove (GBSearchArray        *barray,
+                        const GBSearchConfig *bconfig,
+                        guint                 index_)
+{
+  guint8 *node;
+
+  g_return_val_if_fail (index_ < barray->n_nodes, NULL);
+
+  barray->n_nodes -= 1;
+  node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node;
+  g_memmove (node, node + bconfig->sizeof_node, (barray->n_nodes - index_) * bconfig->sizeof_node);
+  if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_AUTO_SHRINK))
+    {
+      guint new_size = barray->n_nodes * bconfig->sizeof_node;
+      guint old_size = new_size + bconfig->sizeof_node;
+
+      if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2))
+        {
+          new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size);
+          old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size);
+          if (old_size != new_size)
+            barray = (GBSearchArray *) g_realloc (barray, new_size);
+        }
+      else
+        barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size);
+    }
+  return barray;
+}
+static inline void
+g_bsearch_array_free (GBSearchArray        *barray,
+                      const GBSearchConfig *bconfig)
+{
+  g_return_if_fail (barray != NULL);
+
+  g_free (barray);
+}
+
+G_END_DECLS     /* c++ guards */
+
+#endif  /* !__G_BSEARCH_ARRAY_H__ */