diff options
author | Thomas Haller <thaller@redhat.com> | 2014-03-17 19:18:48 +0100 |
---|---|---|
committer | Thomas Haller <thaller@redhat.com> | 2014-03-24 15:10:35 +0100 |
commit | 9e2b5330c5890da7e8a8c8819e25530be0983f54 (patch) | |
tree | 078426a7e28e0d79216645f6560a9fd3f3170df8 | |
parent | 2e8b16ae4ed16b1c7e9ad19bc336e1564e2beecd (diff) | |
download | NetworkManager-th/NMStringTable.tar.gz |
libnl-util: add NMStringTableth/NMStringTable
Signed-off-by: Thomas Haller <thaller@redhat.com>
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | libnm-util/Makefile.am | 4 | ||||
-rw-r--r-- | libnm-util/nm-string-table.c | 377 | ||||
-rw-r--r-- | libnm-util/nm-string-table.h | 58 | ||||
-rw-r--r-- | libnm-util/nm-util-private.c | 8 | ||||
-rw-r--r-- | libnm-util/nm-util-private.h | 10 | ||||
-rw-r--r-- | libnm-util/tests/Makefile.am | 12 | ||||
-rw-r--r-- | libnm-util/tests/test-nm-string-table.c | 163 |
8 files changed, 631 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore index f9401dabca..fbc979fbe2 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-table /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..5d74ac63cd 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-table.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-table.c \ nm-util-private.c \ nm-utils-enum-types.c \ nm-utils.c \ diff --git a/libnm-util/nm-string-table.c b/libnm-util/nm-string-table.c new file mode 100644 index 0000000000..5cb056f934 --- /dev/null +++ b/libnm-util/nm-string-table.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-table.h" + +#include <string.h> + +const NMStringTableCompareFunc COMPARE_DEFAULT = &strcmp; + +typedef struct NMStringTable { + guint size; + NMStringTableCompareFunc compare; + + void *_offset; +} NMStringTable; + +#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 +{ + NMStringTableCompareFunc compare; + gboolean duplicate; +}; + +static gint +prepare_sort_check (gconstpointer a, gconstpointer b, gpointer user_data) +{ + const NMStringTableTuple *a1 = a; + const NMStringTableTuple *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 NMStringTableTuple *a1 = a; + const NMStringTableTuple *a2 = b; + + return ((NMStringTableCompareFunc) user_data) (a1->key, a2->key); +} +#endif + +static NMStringTable * +_new (NMStringTableCompareFunc compare, GArray *prepare) +{ + NMStringTable *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++) { + NMStringTableTuple *data = &g_array_index (prepare, NMStringTableTuple, 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 (NMStringTable, _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++) { + NMStringTableTuple *data = &g_array_index (prepare, NMStringTableTuple, 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, NMStringTableTuple, 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 + +NMStringTable * +nm_string_table_new_keys_only (NMStringTableCompareFunc 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) { + NMStringTableTuple data = { 0 }; + + prepare = g_array_sized_new (FALSE, FALSE, sizeof (NMStringTableTuple), 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); +} + +NMStringTable * +nm_string_table_new (NMStringTableCompareFunc compare, int argc, const NMStringTableTuple *args) +{ + GArray *prepare = NULL; + + g_return_val_if_fail (!argc || args, NULL); + + if (argc > 0 || args) { + prepare = g_array_sized_new (FALSE, FALSE, sizeof (NMStringTableTuple), 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_table_size (NMStringTable *self) +{ + g_return_val_if_fail (self, 0); + + return self->size; +} + +static int +_lookup_by_key (NMStringTable *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 (NMStringTable *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_table_lookup_by_key (NMStringTable *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_table_lookup_by_index (NMStringTable *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_table_get_data_by_key (NMStringTable *self, const char *key) +{ + int idx = _lookup_by_key (self, key); + + return idx >= 0 ? OFFSET_DATA (self)[idx] : NULL; +} + +const char *const* +nm_string_table_get_keys (NMStringTable *self) +{ + g_return_val_if_fail (self, NULL); + + return OFFSET_STRING (self); +} + +gpointer * +nm_string_table_get_data (NMStringTable *self) +{ + g_return_val_if_fail (self, NULL); + + return OFFSET_DATA (self); +} + +NMStringTableCompareFunc +nm_string_table_get_compare_func (NMStringTable *self) +{ + g_return_val_if_fail (self, NULL); + + return self->compare; +} + +void +nm_string_table_foreach (NMStringTable *self, NMStringTableForeachFunc 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-table.h b/libnm-util/nm-string-table.h new file mode 100644 index 0000000000..3d4d12caef --- /dev/null +++ b/libnm-util/nm-string-table.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_TABLE_H__ +#define __NM_STRING_TABLE_H__ + +#include <glib.h> + +G_BEGIN_DECLS + +typedef struct NMStringTable NMStringTable; + +typedef int (*NMStringTableCompareFunc) (const char *s1, const char *s2); +typedef gboolean (*NMStringTableForeachFunc) (const char *key, gpointer *pdata, int idx, void *user_data); + +typedef struct { + const char *key; + void *data; +} NMStringTableTuple; + +NMStringTable *nm_string_table_new (NMStringTableCompareFunc compare, int argc, const NMStringTableTuple *args); +NMStringTable *nm_string_table_new_keys_only (NMStringTableCompareFunc compare, int argc, const char **args); + +guint nm_string_table_size (NMStringTable *table); +NMStringTableCompareFunc nm_string_table_get_compare_func (NMStringTable *table); +gboolean nm_string_table_lookup_by_key (NMStringTable *table, const char *key, int *out_idx, const char **out_key, gpointer **out_data); +gboolean nm_string_table_lookup_by_index (NMStringTable *table, int idx, const char **out_key, gpointer **out_data); + +gpointer nm_string_table_get_data_by_key (NMStringTable *table, const char *key); + +const char *const*nm_string_table_get_keys (NMStringTable *table); +gpointer *nm_string_table_get_data (NMStringTable *table); + +void nm_string_table_foreach (NMStringTable *table, NMStringTableForeachFunc func, void *user_data); + +G_END_DECLS + +#endif /* __NM_STRING_TABLE_H__ */ diff --git a/libnm-util/nm-util-private.c b/libnm-util/nm-util-private.c index 2902f8ce8c..fc4fc47ca3 100644 --- a/libnm-util/nm-util-private.c +++ b/libnm-util/nm-util-private.c @@ -22,6 +22,14 @@ #include "nm-util-private.h" static const NMUtilPrivateData data = { + .f_nm_string_table_new = &nm_string_table_new, + .f_nm_string_table_size = &nm_string_table_size, + .f_nm_string_table_get_keys = &nm_string_table_get_keys, + .f_nm_string_table_get_compare_func = &nm_string_table_get_compare_func, + .f_nm_string_table_lookup_by_key = &nm_string_table_lookup_by_key, + .f_nm_string_table_lookup_by_index= &nm_string_table_lookup_by_index, + .f_nm_string_table_get_data_by_key= &nm_string_table_get_data_by_key, + .f_nm_string_table_get_data = &nm_string_table_get_data, }; const NMUtilPrivateData * diff --git a/libnm-util/nm-util-private.h b/libnm-util/nm-util-private.h index be55ee13db..5b3cb08046 100644 --- a/libnm-util/nm-util-private.h +++ b/libnm-util/nm-util-private.h @@ -24,9 +24,19 @@ #include <glib.h> +#include "nm-string-table.h" + G_BEGIN_DECLS typedef struct NMUtilPrivateData { + NMStringTable *(*f_nm_string_table_new) (NMStringTableCompareFunc compare, int argc, const NMStringTableTuple *args); + guint (*f_nm_string_table_size) (NMStringTable *table); + const char *const*(*f_nm_string_table_get_keys) (NMStringTable *table); + NMStringTableCompareFunc (*f_nm_string_table_get_compare_func) (NMStringTable *table); + gboolean (*f_nm_string_table_lookup_by_key) (NMStringTable *table, const char *key, int *out_idx, const char **out_key, gpointer **out_data); + gboolean (*f_nm_string_table_lookup_by_index) (NMStringTable *table, int idx, const char **out_key, gpointer **out_data); + gpointer (*f_nm_string_table_get_data_by_key) (NMStringTable *table, const char *key); + gpointer *(*f_nm_string_table_get_data) (NMStringTable *table); } NMUtilPrivateData; const NMUtilPrivateData *nm_util_get_private (void); diff --git a/libnm-util/tests/Makefile.am b/libnm-util/tests/Makefile.am index 0ef1bc007e..6ed763cb65 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-table \ test-setting-8021x \ test-setting-dcb @@ -52,6 +53,14 @@ test_general_LDADD = \ $(GLIB_LIBS) \ $(DBUS_LIBS) +test_nm_string_table_SOURCES = \ + test-nm-string-table.c + +test_nm_string_table_LDADD = \ + $(top_builddir)/libnm-util/libnm-util.la \ + $(GLIB_LIBS) \ + $(DBUS_LIBS) + test_setting_8021x_SOURCES = \ test-setting-8021x.c @@ -68,10 +77,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-table $(abs_builddir)/test-settings-defaults $(abs_builddir)/test-secrets $(abs_builddir)/test-general + $(abs_builddir)/test-nm-string-table $(abs_builddir)/test-setting-dcb # Private key and CA certificate in the same file (PEM) diff --git a/libnm-util/tests/test-nm-string-table.c b/libnm-util/tests/test-nm-string-table.c new file mode 100644 index 0000000000..54c0438d33 --- /dev/null +++ b/libnm-util/tests/test-nm-string-table.c @@ -0,0 +1,163 @@ +/* -*- 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-table.h" + +#include <glib.h> +#include <string.h> + +#include "nm-utils.h" +#include "nm-util-private.h" + +#define C(f) (NM_UTIL_PRIVATE_CALL (f)) + +static void +assert_table (NMStringTable *table, guint size) +{ + const char *const* keys; + guint i, j; + NMStringTableCompareFunc compare; + gpointer *data; + gboolean success; + + g_assert (table); + g_assert_cmpint (size, ==, C (nm_string_table_size) (table)); + + compare = C (nm_string_table_get_compare_func) (table); + g_assert (compare); + + keys = C (nm_string_table_get_keys) (table); + data = C (nm_string_table_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 = C (nm_string_table_lookup_by_key) (table, "SUBSUB", NULL, &l_key, NULL); + g_assert (success); + l_key = &l_key[3]; + } else + break; + success = C (nm_string_table_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] == C (nm_string_table_get_data_by_key) (table, l_key)); + + g_free (tmp_release); + + if (j == 0) { + success = C (nm_string_table_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 () +{ + NMStringTable *table; + const NMStringTableTuple 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 = C (nm_string_table_new) (NULL, -1, args1); + assert_table (table, 7); + + g_free (table); +} + +#define TPATH "/libnm-util/nm-string-table/" + +int main (int argc, char **argv) +{ + GError *error = NULL; + gboolean success; + + g_test_init (&argc, &argv, NULL); + g_type_init (); + + success = nm_utils_init (&error); + g_assert_no_error (error); + g_assert (success); + + g_log_set_always_fatal (G_LOG_LEVEL_CRITICAL); + + g_test_add_func (TPATH "run", test_run); + + return g_test_run (); +} + |