libnl-util: add NMStringTableth/wip/NMStringIndexth/NMStringIndex

Signed-off-by: Thomas Haller <thaller@redhat.com>

6 files changed, 601 insertions, 2 deletions

diff --git a/.gitignore b/.gitignore
index f9401dabca..c986346643 100644
--- a/.gitignore
+++ b/.gitignore
@@ -174,6 +174,7 @@ valgrind-*.log
 /libnm-util/tests/test-settings-defaults
 /libnm-util/tests/test-general
 /libnm-util/tests/test-need-secrets
+/libnm-util/tests/test-nm-string-index
 /libnm-util/tests/test-secrets
 /libnm-util/tests/test-setting-8021x
 /libnm-util/tests/test-setting-dcb
diff --git a/libnm-util/Makefile.am b/libnm-util/Makefile.am
index 84f4aa303d..3fca7e94d9 100644
--- a/libnm-util/Makefile.am
+++ b/libnm-util/Makefile.am
@@ -58,7 +58,8 @@ libnm_util_la_private_headers = \
 	nm-param-spec-specialized.h	\
 	nm-util-private.h		\
 	nm-utils-private.h		\
-	nm-setting-private.h
+	nm-setting-private.h \
+	nm-string-index.h
 
 libnm_util_la_csources = \
 	crypto.c			\
@@ -91,6 +92,7 @@ libnm_util_la_csources = \
 	nm-setting-wireless.c		\
 	nm-setting-wireless-security.c	\
 	nm-setting-vpn.c		\
+	nm-string-index.c		\
 	nm-util-private.c		\
 	nm-utils-enum-types.c		\
 	nm-utils.c			\
diff --git a/libnm-util/nm-string-index.c b/libnm-util/nm-string-index.c
new file mode 100644
index 0000000000..ad5c049763
--- /dev/null
+++ b/libnm-util/nm-string-index.c
@@ -0,0 +1,377 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
+
+/*
+ * Dan Williams <dcbw@redhat.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301 USA.
+ *
+ * (C) Copyright 2014 Red Hat, Inc.
+ */
+
+#include "nm-string-index.h"
+
+#include <string.h>
+
+const NMStringIndexCompareFunc COMPARE_DEFAULT = &strcmp;
+
+typedef struct NMStringIndex {
+	guint size;
+	NMStringIndexCompareFunc compare;
+
+	void *_offset;
+} NMStringIndex;
+
+#define OFFSET_STRING(table)     ((const char **) ((&((table)->_offset))))
+#define OFFSET_DATA(table)       ((void **) &(OFFSET_STRING (table)[(table)->size + 1]))
+#define OFFSET_STATICSTR(table)  ((const char *) &(OFFSET_DATA (table)[(table)->size + 1]))
+
+#ifndef G_DISABLE_ASSERT
+struct prepare_sort_data
+{
+	NMStringIndexCompareFunc compare;
+	gboolean duplicate;
+};
+
+static gint
+prepare_sort_check (gconstpointer a, gconstpointer b, gpointer user_data)
+{
+	const NMStringIndexItem *a1 = a;
+	const NMStringIndexItem *a2 = b;
+	struct prepare_sort_data *data = user_data;
+	int c;
+
+	c = (data->compare) (a1->key, a2->key);
+	if (c == 0)
+		data->duplicate = TRUE;
+	return c;
+}
+#else
+static gint
+prepare_sort_direct (gconstpointer a, gconstpointer b, gpointer user_data)
+{
+	const NMStringIndexItem *a1 = a;
+	const NMStringIndexItem *a2 = b;
+
+	return ((NMStringIndexCompareFunc) user_data) (a1->key, a2->key);
+}
+#endif
+
+static NMStringIndex *
+_new (NMStringIndexCompareFunc compare, GArray *prepare)
+{
+	NMStringIndex *self;
+	guint i;
+	const char **tab_str;
+	const char *tab_static;
+	void **tab_dat;
+	size_t len;
+	GString *static_strings;
+	guint argc = prepare ? prepare->len : 0;
+
+	if (!compare)
+		compare = COMPARE_DEFAULT;
+
+	if (argc > G_MAXINT) {
+		g_array_free (prepare, TRUE);
+		g_return_val_if_reached (NULL);
+		return NULL;
+	}
+
+	static_strings = g_string_new ("");
+
+	if (prepare) {
+#ifndef G_DISABLE_ASSERT
+		struct prepare_sort_data sort_data = { .compare = compare };
+
+		g_array_sort_with_data (prepare, prepare_sort_check, &sort_data);
+		if (sort_data.duplicate) {
+			g_string_free (static_strings, TRUE);
+			g_array_free (prepare, TRUE);
+			g_return_val_if_reached (NULL);
+		}
+#else
+		g_array_sort_with_data (prepare, prepare_sort_direct, compare);
+#endif
+
+		for (i = 0; i < argc; i++) {
+			NMStringIndexItem *data = &g_array_index (prepare, NMStringIndexItem, i);
+			char *new_key = &static_strings->str[static_strings->len];
+
+			g_string_append (static_strings, data->key);
+			g_string_append_c (static_strings, '\0');
+			data->key = new_key;
+		}
+	} else
+		g_string_append_c (static_strings, '\0');
+
+	len = offsetof (NMStringIndex, _offset) +
+	      (argc + 1) * (sizeof (const char *) + sizeof (void *)) +
+	      static_strings->len;
+
+	self = g_malloc (len);
+	self->size = argc;
+	self->compare = compare;
+
+	tab_str = OFFSET_STRING (self);
+	tab_dat = OFFSET_DATA (self);
+	tab_static = OFFSET_STATICSTR (self);
+	memcpy ((char *) tab_static, static_strings->str, static_strings->len);
+	for (i = 0; i < argc; i++) {
+		NMStringIndexItem *data = &g_array_index (prepare, NMStringIndexItem, i);
+
+		(*tab_str++) = &tab_static[data->key - static_strings->str];
+		(*tab_dat++) = data->data;
+	}
+	*tab_str = NULL;
+	*tab_dat = NULL;
+
+	g_string_free (static_strings, TRUE);
+
+	if (prepare)
+		g_array_free (prepare, TRUE);
+
+	return self;
+}
+
+#ifndef G_DISABLE_ASSERT
+static gboolean
+_assert_args (GArray *prepare, int argc)
+{
+	guint i;
+
+	g_return_val_if_fail (prepare, FALSE);
+	g_return_val_if_fail (prepare->len == argc, FALSE);
+
+	for (i = 0; i < prepare->len; i++ )
+		g_return_val_if_fail (g_array_index (prepare, NMStringIndexItem, i).key, FALSE);
+	return TRUE;
+}
+#define ASSERT_ARGS(prepare, argc) \
+	G_STMT_START { \
+		if (!_assert_args (prepare, argc)) { \
+			g_array_free (prepare, TRUE); \
+			return NULL; \
+		} \
+	} G_STMT_END
+#else
+#define ASSERT_ARGS(prepare, argc) G_STMT_START { ; } G_STMT_END
+#endif
+
+NMStringIndex *
+nm_string_index_new_keys_only (NMStringIndexCompareFunc compare, int argc, const char **args)
+{
+	guint i;
+	GArray *prepare = NULL;
+
+	g_return_val_if_fail ((argc > 0 && args) || argc <= 0, NULL);
+
+	if (argc > 0 || args) {
+		NMStringIndexItem data = { 0 };
+
+		prepare = g_array_sized_new (FALSE, FALSE, sizeof (NMStringIndexItem), argc > 0 ? argc : 0);
+		if (argc > 0) {
+			for (i = 0; i < argc; i++) {
+				data.key = args[i];
+				g_array_append_val (prepare, data);
+			}
+			ASSERT_ARGS (prepare, argc);
+		} else if (argc < 0) {
+			/* argc is negative, that means that args is NULL terminated. */
+			for (; *args; args++) {
+				data.key = *args;
+				g_array_append_val (prepare, data);
+			}
+		}
+	}
+	return _new (compare, prepare);
+}
+
+NMStringIndex *
+nm_string_index_new (NMStringIndexCompareFunc compare, int argc, const NMStringIndexItem *args)
+{
+	GArray *prepare = NULL;
+
+	g_return_val_if_fail (!argc || args, NULL);
+
+	if (argc > 0 || args) {
+		prepare = g_array_sized_new (FALSE, FALSE, sizeof (NMStringIndexItem), 0);
+		if (argc > 0) {
+			g_array_append_vals (prepare, args, argc);
+			ASSERT_ARGS (prepare, argc);
+		} else if (argc < 0) {
+			/* argc is negative, that means that args is NULL terminated. */
+			for (; args->key; args++)
+				g_array_append_val (prepare, *args);
+		}
+	}
+	return _new (compare, prepare);
+}
+
+
+guint
+nm_string_index_size (NMStringIndex *self)
+{
+	g_return_val_if_fail (self, 0);
+
+	return self->size;
+}
+
+static int
+_lookup_by_key (NMStringIndex *self, const char *key)
+{
+	const char *const*t_str;
+	guint imin, imax, imid;
+
+	g_return_val_if_fail (self, -1);
+	g_return_val_if_fail (key, -1);
+
+	if (self->size == 0)
+		return -1;
+
+	t_str = OFFSET_STRING (self);
+	imin = 0;
+	imax = self->size - 1;
+
+	if (key >= t_str[0] && key <= t_str[imax]) {
+		/* Try binary search using the pointer value. We try this
+		 * optimization, because the user might lookup using one of the
+		 * key values themselves.
+		 */
+		while (imax >= imin) {
+			/* save against overflow, because size is <= INT_MAX */
+			imid = (imax + imin) / 2;
+			if (t_str[imid] == key)
+				return imid;
+			if (t_str[imid] < key)
+				imin = imid + 1;
+			else
+				imax = imid - 1;
+		}
+
+		/* if we did not find by pointer comparison, try again using
+		 * strcmp. The user has provided a substring to one of the keys...
+		 */
+		imin = 0;
+		imax = self->size - 1;
+	}
+	/* binary search using the compare function. */
+	while (imax >= imin) {
+		int c;
+
+		/* save against overflow, because size is <= INT_MAX */
+		imid = (imax + imin) / 2;
+		c = self->compare (key, t_str[imid]);
+
+		if (!c)
+			return imid;
+		if (c > 0)
+			imin = imid + 1;
+		else
+			imax = imid - 1;
+	}
+
+	return -1;
+}
+
+static gboolean
+_access_at_index (NMStringIndex *self, int idx, const char **out_key, gpointer **out_data)
+{
+	if (idx < 0) {
+		if (out_key)
+			*out_key = NULL;
+		if (out_data)
+			out_data = NULL;
+		return FALSE;
+	}
+	if (out_key)
+		*out_key = OFFSET_STRING (self)[idx];
+	if (out_data)
+		*out_data = &OFFSET_DATA (self)[idx];
+	return TRUE;
+}
+
+gboolean
+nm_string_index_lookup_by_key (NMStringIndex *self, const char *key, int *out_idx, const char **out_key, gpointer **out_data)
+{
+	int idx = _lookup_by_key (self, key);
+
+	if (out_idx)
+		*out_idx = idx;
+	return _access_at_index (self, idx, out_key, out_data);
+}
+
+gboolean
+nm_string_index_lookup_by_index (NMStringIndex *self, int idx, const char **out_key, gpointer **out_data)
+{
+	g_return_val_if_fail (self, FALSE);
+
+	if (idx >= self->size) {
+		/* don't check for idx<0, _access_at_index will handle that. */
+		idx = -1;
+	}
+	return _access_at_index (self, idx, out_key, out_data);
+}
+
+gpointer
+nm_string_index_get_data_by_key (NMStringIndex *self, const char *key)
+{
+	int idx = _lookup_by_key (self, key);
+
+	return idx >= 0 ? OFFSET_DATA (self)[idx] : NULL;
+}
+
+const char *const*
+nm_string_index_get_keys (NMStringIndex *self)
+{
+	g_return_val_if_fail (self, NULL);
+
+	return OFFSET_STRING (self);
+}
+
+gpointer *
+nm_string_index_get_data (NMStringIndex *self)
+{
+	g_return_val_if_fail (self, NULL);
+
+	return OFFSET_DATA (self);
+}
+
+NMStringIndexCompareFunc
+nm_string_index_get_compare_func (NMStringIndex *self)
+{
+	g_return_val_if_fail (self, NULL);
+
+	return self->compare;
+}
+
+void
+nm_string_index_foreach (NMStringIndex *self, NMStringIndexForeachFunc func, void *user_data)
+{
+	const char **tab_str;
+	void **tab_dat;
+	guint i, size;
+
+	g_return_if_fail (self);
+	g_return_if_fail (func);
+
+	tab_str = OFFSET_STRING (self);
+	tab_dat = OFFSET_DATA (self);
+	for (i = 0, size = self->size; i < size; i++) {
+		if (!func (tab_str[i], &tab_dat[i], i, user_data))
+			return;
+	}
+}
+
diff --git a/libnm-util/nm-string-index.h b/libnm-util/nm-string-index.h
new file mode 100644
index 0000000000..63eb77fa00
--- /dev/null
+++ b/libnm-util/nm-string-index.h
@@ -0,0 +1,58 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
+
+/*
+ * Dan Williams <dcbw@redhat.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301 USA.
+ *
+ * (C) Copyright 2014 Red Hat, Inc.
+ */
+
+#ifndef __NM_STRING_INDEX_H__
+#define __NM_STRING_INDEX_H__
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+typedef struct NMStringIndex NMStringIndex;
+
+typedef int (*NMStringIndexCompareFunc) (const char *s1, const char *s2);
+typedef gboolean (*NMStringIndexForeachFunc) (const char *key, gpointer *pdata, int idx, void *user_data);
+
+typedef struct {
+	const char *key;
+	void *data;
+} NMStringIndexItem;
+
+NMStringIndex *nm_string_index_new (NMStringIndexCompareFunc compare, int argc, const NMStringIndexItem *args);
+NMStringIndex *nm_string_index_new_keys_only (NMStringIndexCompareFunc compare, int argc, const char **args);
+
+guint nm_string_index_size (NMStringIndex *table);
+NMStringIndexCompareFunc nm_string_index_get_compare_func (NMStringIndex *table);
+gboolean nm_string_index_lookup_by_key (NMStringIndex *table, const char *key, int *out_idx, const char **out_key, gpointer **out_data);
+gboolean nm_string_index_lookup_by_index (NMStringIndex *table, int idx, const char **out_key, gpointer **out_data);
+
+gpointer nm_string_index_get_data_by_key (NMStringIndex *table, const char *key);
+
+const char *const*nm_string_index_get_keys (NMStringIndex *table);
+gpointer *nm_string_index_get_data (NMStringIndex *table);
+
+void nm_string_index_foreach (NMStringIndex *table, NMStringIndexForeachFunc func, void *user_data);
+
+G_END_DECLS
+
+#endif /* __NM_STRING_INDEX_H__ */
diff --git a/libnm-util/tests/Makefile.am b/libnm-util/tests/Makefile.am
index 0ef1bc007e..de9c72832d 100644
--- a/libnm-util/tests/Makefile.am
+++ b/libnm-util/tests/Makefile.am
@@ -17,6 +17,7 @@ noinst_PROGRAMS = \
 	test-crypto \
 	test-secrets \
 	test-general \
+	test-nm-string-index \
 	test-setting-8021x \
 	test-setting-dcb
 
@@ -52,6 +53,13 @@ test_general_LDADD = \
 	$(GLIB_LIBS) \
 	$(DBUS_LIBS)
 
+test_nm_string_index_SOURCES = \
+	test-nm-string-index.c \
+	$(top_builddir)/libnm-util/nm-string-index.c
+
+test_nm_string_index_LDADD = \
+	$(GLIB_LIBS)
+
 test_setting_8021x_SOURCES = \
 	test-setting-8021x.c
 
@@ -68,10 +76,11 @@ test_setting_dcb_LDADD = \
 	$(GLIB_LIBS) \
 	$(DBUS_LIBS)
 
-check-local: test-settings-defaults test-crypto test-secrets test-setting-8021x test-setting-dcb
+check-local: test-settings-defaults test-crypto test-secrets test-setting-8021x test-setting-dcb test-nm-string-index
 	$(abs_builddir)/test-settings-defaults
 	$(abs_builddir)/test-secrets
 	$(abs_builddir)/test-general
+	$(abs_builddir)/test-nm-string-index
 	$(abs_builddir)/test-setting-dcb
 
 # Private key and CA certificate in the same file (PEM)
diff --git a/libnm-util/tests/test-nm-string-index.c b/libnm-util/tests/test-nm-string-index.c
new file mode 100644
index 0000000000..a7b709cebe
--- /dev/null
+++ b/libnm-util/tests/test-nm-string-index.c
@@ -0,0 +1,152 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: t; c-basic-offset: 4 -*- */
+/*
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program 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.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Copyright (C) 2013 Red Hat, Inc.
+ *
+ */
+
+#include "nm-string-index.h"
+
+#include <glib.h>
+#include <glib-object.h>
+#include <string.h>
+
+static void
+assert_table (NMStringIndex *table, guint size)
+{
+	const char *const* keys;
+	guint i, j;
+	NMStringIndexCompareFunc compare;
+	gpointer *data;
+	gboolean success;
+
+	g_assert (table);
+	g_assert_cmpint (size, ==, nm_string_index_size (table));
+
+	compare = nm_string_index_get_compare_func (table);
+	g_assert (compare);
+
+	keys = nm_string_index_get_keys (table);
+	data = nm_string_index_get_data (table);
+	g_assert (keys);
+	g_assert (data);
+	for (i = 0; i < size; i++) {
+		g_assert (keys[i]);
+		g_assert (data[i]);
+		if (i > 0) {
+			g_assert (keys[i-1] < keys[i]);
+			g_assert (keys[i] == &(keys[i-1][strlen (keys[i-1]) + 1]));
+			g_assert_cmpint (compare (keys[i-1], keys[i]), <, 0);
+
+			g_assert_cmpint (GPOINTER_TO_INT (data[i-1]), ==, GPOINTER_TO_INT (data[i]) - 1);
+		}
+
+		for (j = 0; ; j++) {
+			const char *l_key;
+			char *tmp_release = NULL;
+			int out_idx = 4711 + j;
+			const char *out_key = "axb";
+			gpointer *out_data = GINT_TO_POINTER (2324+j);
+
+			if (j == 0) {
+				l_key = keys[i];
+			} else if (j == 1) {
+				l_key = tmp_release = g_strdup (keys[i]);
+			} else if(j == 2 && strcmp (keys[i], "SUB") == 0) {
+				success = nm_string_index_lookup_by_key (table, "SUBSUB", NULL, &l_key, NULL);
+				g_assert (success);
+				l_key = &l_key[3];
+			} else
+				break;
+			success = nm_string_index_lookup_by_key (table, l_key, &out_idx, &out_key, &out_data);
+			g_assert (success);
+			g_assert_cmpint (i, ==, out_idx);
+			g_assert (&data[i] == out_data);
+			g_assert (keys[i] == out_key);
+
+			g_assert (data[i] == nm_string_index_get_data_by_key (table, l_key));
+
+			g_free (tmp_release);
+
+			if (j == 0) {
+				success = nm_string_index_lookup_by_index (table, i, &out_key, &out_data);
+				g_assert (success);
+				g_assert (&data[i] == out_data);
+				g_assert (keys[i] == out_key);
+			}
+		}
+	}
+	g_assert (!keys[size]);
+	g_assert (!data[size]);
+}
+
+static void
+test_run ()
+{
+	NMStringIndex *table;
+	const NMStringIndexItem args1[] = {
+		{
+			.key = "c",
+			.data = GINT_TO_POINTER (5),
+		},
+		{
+			.key = "SUBSUB",
+			.data = GINT_TO_POINTER (2),
+		},
+		{
+			.key = "SUB",
+			.data = GINT_TO_POINTER (1),
+		},
+		{
+			.key = "b",
+			.data = GINT_TO_POINTER (4),
+		},
+		{
+			.key = "a",
+			.data = GINT_TO_POINTER (3),
+		},
+		{
+			.key = "dddc",
+			.data = GINT_TO_POINTER (6),
+		},
+		{
+			.key = "dddd",
+			.data = GINT_TO_POINTER (7),
+		},
+		{ 0 },
+	};
+
+	table = nm_string_index_new (NULL, -1, args1);
+	assert_table (table, 7);
+
+	g_free (table);
+}
+
+#define TPATH "/libnm-util/nm-string-index/"
+
+int main (int argc, char **argv)
+{
+	g_test_init (&argc, &argv, NULL);
+	g_type_init ();
+
+	g_log_set_always_fatal (G_LOG_LEVEL_CRITICAL);
+
+	g_test_add_func (TPATH "run", test_run);
+
+	return g_test_run ();
+}
+