aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2018-09-15 17:47:49 +0300
committerSergey Poznyakoff <gray@gnu.org>2018-09-15 18:17:59 +0300
commita7be650dc0b3528f1ca75bcb03fc4a94c2d65c49 (patch)
tree3094570ed3e59c628a123a92281ea3ae0a4a6a87
parent1cf9d2d93642283bf7a338d2541eb5a5b396dd0c (diff)
downloaddico-a7be650dc0b3528f1ca75bcb03fc4a94c2d65c49.tar.gz
dico-a7be650dc0b3528f1ca75bcb03fc4a94c2d65c49.tar.bz2
Provide own binary search and sort functions.
* lib/bsearch.c: New file. * lib/mergesort.c: New file. * include/dico/list.h (dico_list_comp_t): Change signature. (dico_list_set_comparator) (dico_list_intersect, dico_list_intersect_p) (_dico_list_locate, _dico_list_remove): Change signature. (dico_list_set_comparator_data) (dico_list_get_comparator_data): New protos. * lib/list.c (dico_list)<comp_data>: New member. (dico_list_set_comparator) (dico_list_intersect, dico_list_intersect_p) (_dico_list_locate, _dico_list_remove): Change signature. (dico_list_set_comparator_data) (dico_list_get_comparator_data): New functions. * lib/Makefile.am: Raise library version number. * dico/saslauth.c: Reflect the above changes. * dicod/acl.c: Likewise. * dicod/alias.c: Likewise. * dicod/capa.c: Likewise. * dicod/commands.c: Likewise. * dicod/gsasl.c: Likewise. * dicod/lang.c: Likewise. * dicod/main.c: Likewise. * dicod/virtual.c: Likewise. * include/dico/strat.h: Likewise. * include/dico/util.h: Likewise. * lib/assoc.c: Likewise. * lib/markup.c: Likewise. * lib/strat.c: Likewise. * lib/tests/listop.c: Likewise. * lib/udb.c: Likewise. * modules/gcide/gcide.c: Likewise. * modules/wordnet/wordnet.c: Likewise. * modules/dict.org/dictorg.c: Use appropriate comparisons in uniq_comp and compare_entry_ptr.
-rw-r--r--dico/saslauth.c4
-rw-r--r--dicod/acl.c4
-rw-r--r--dicod/alias.c4
-rw-r--r--dicod/capa.c4
-rw-r--r--dicod/commands.c8
-rw-r--r--dicod/gsasl.c6
-rw-r--r--dicod/lang.c12
-rw-r--r--dicod/main.c11
-rw-r--r--dicod/virtual.c12
-rw-r--r--include/dico/list.h23
-rw-r--r--include/dico/strat.h2
-rw-r--r--include/dico/util.h6
-rw-r--r--lib/Makefile.am4
-rw-r--r--lib/assoc.c31
-rw-r--r--lib/bsearch.c61
-rw-r--r--lib/list.c90
-rw-r--r--lib/markup.c4
-rw-r--r--lib/mergesort.c101
-rw-r--r--lib/strat.c4
-rw-r--r--lib/tests/listop.c4
-rw-r--r--lib/udb.c4
-rw-r--r--modules/dict.org/dictorg.c95
-rw-r--r--modules/gcide/gcide.c5
-rw-r--r--modules/wordnet/wordnet.c6
24 files changed, 363 insertions, 142 deletions
diff --git a/dico/saslauth.c b/dico/saslauth.c
index 1adf8f3..6052b30 100644
--- a/dico/saslauth.c
+++ b/dico/saslauth.c
@@ -56,7 +56,7 @@ get_implemented_mechs(Gsasl *ctx)
}
static int
-str_str_cmp(const void *item, void *data)
+str_str_cmp(const void *item, const void *data, void *closure)
{
return c_strcasecmp(item, data);
}
@@ -284,7 +284,7 @@ saslauth0(struct dict_connection *conn, struct auth_cred *cred,
if (cred->mech)
mechlist = dico_list_intersect(cred->mech, authctx->mech,
- str_str_cmp);
+ str_str_cmp, NULL);
else
mechlist = cred->mech;
if (!mechlist || dico_list_count(mechlist) == 0) {
diff --git a/dicod/acl.c b/dicod/acl.c
index c200e01..4f8357a 100644
--- a/dicod/acl.c
+++ b/dicod/acl.c
@@ -310,7 +310,7 @@ parse_acl_line(grecs_locus_t *locus, int allow, dicod_acl_t acl,
/* ACL verification */
static int
-cmp_group_name(const void *item, void *data)
+cmp_group_name(const void *item, const void *data, void *ignore)
{
return strcmp((char*)item, (char*)data);
}
@@ -366,7 +366,7 @@ _acl_check(struct acl_entry *ent)
if (ent->groups) {
result = dico_list_intersect_p(ent->groups, user_groups,
- cmp_group_name);
+ cmp_group_name, NULL);
if (!result)
return 0;
}
diff --git a/dicod/alias.c b/dicod/alias.c
index 2cdbd5d..2c12717 100644
--- a/dicod/alias.c
+++ b/dicod/alias.c
@@ -74,7 +74,7 @@ alias_install(const char *kw, int argc, char **argv, grecs_locus_t *ploc)
}
static int
-list_alias_cmp(const void *a, void *b)
+list_alias_cmp(const void *a, const void *b, void *ignore)
{
const struct alias *ap1 = a;
const struct alias *ap2 = b;
@@ -96,7 +96,7 @@ alias_expand(int argc, char **argv, int *pargc, char ***pargv)
sample.kw = (char*) ap->argv[0];
if (!alist) {
alist = xdico_list_create();
- dico_list_set_comparator (alist, list_alias_cmp);
+ dico_list_set_comparator (alist, list_alias_cmp, NULL);
}
xdico_list_append(alist, ap);
}
diff --git a/dicod/capa.c b/dicod/capa.c
index c89dcb3..f878115 100644
--- a/dicod/capa.c
+++ b/dicod/capa.c
@@ -28,7 +28,7 @@ struct dicod_capa {
static dico_list_t /* of struct dicod_capa */ capa_list;
static int
-_cmp_capa_name(const void *item, void *data)
+_cmp_capa_name(const void *item, const void *data, void *unused)
{
const struct dicod_capa *cp = item;
return strcmp(cp->name, (char*)data);
@@ -46,7 +46,7 @@ dicod_capa_register(const char *name, struct dicod_command *cmd,
cp->enabled = 0;
if (!capa_list) {
capa_list = xdico_list_create();
- dico_list_set_comparator(capa_list, _cmp_capa_name);
+ dico_list_set_comparator(capa_list, _cmp_capa_name, NULL);
}
xdico_list_append(capa_list, cp);
}
diff --git a/dicod/commands.c b/dicod/commands.c
index 1fa7655..d21ff74 100644
--- a/dicod/commands.c
+++ b/dicod/commands.c
@@ -304,7 +304,7 @@ struct locate_data {
};
static int
-_cmd_arg_cmp(const void *item, void *data)
+_cmd_arg_cmp(const void *item, const void *data, void *unused)
{
const struct dicod_command *p = item;
const struct locate_data *datptr = data;
@@ -333,13 +333,13 @@ dicod_add_command(struct dicod_command *cmd)
{
if (!command_list) {
command_list = xdico_list_create();
- dico_list_set_comparator(command_list, _cmd_arg_cmp);
+ dico_list_set_comparator(command_list, _cmd_arg_cmp, NULL);
}
xdico_list_append(command_list, cmd);
}
static int
-cmd_comp(const void *a, void *b)
+cmd_comp(const void *a, const void *b, void *closure)
{
const struct dicod_command *ca = a;
const struct dicod_command *cb = b;
@@ -351,7 +351,7 @@ dicod_remove_command(const char *name)
{
struct dicod_command cmd;
cmd.keyword = name;
- _dico_list_remove(command_list, &cmd, cmd_comp, NULL);
+ _dico_list_remove(command_list, &cmd, cmd_comp, NULL, NULL);
}
void
diff --git a/dicod/gsasl.c b/dicod/gsasl.c
index 78a02fc..d296c8a 100644
--- a/dicod/gsasl.c
+++ b/dicod/gsasl.c
@@ -29,7 +29,7 @@ dico_list_t sasl_anon_groups;
static Gsasl *ctx;
static int
-cmp_names(const void *item, void *data)
+cmp_names(const void *item, const void *data, void *closure)
{
return c_strcasecmp(item, data);
}
@@ -38,9 +38,9 @@ static int
disabled_mechanism_p(char *name)
{
if (sasl_enabled_mech
- && !_dico_list_locate(sasl_enabled_mech, name, cmp_names))
+ && !_dico_list_locate(sasl_enabled_mech, name, cmp_names, NULL))
return 1;
- return !!_dico_list_locate(sasl_disabled_mech, name, cmp_names);
+ return !!_dico_list_locate(sasl_disabled_mech, name, cmp_names, NULL);
}
static void
diff --git a/dicod/lang.c b/dicod/lang.c
index bb0b441..062d647 100644
--- a/dicod/lang.c
+++ b/dicod/lang.c
@@ -20,7 +20,7 @@ dico_list_t dicod_lang_lazy_prefs;
dico_list_t dicod_lang_prefs[2];
static int
-cmp_string_ci(const void *a, void *b)
+cmp_string_ci(const void *a, const void *b, void *closure)
{
return c_strcasecmp(a, b);
}
@@ -33,19 +33,21 @@ dicod_lang_check(dico_list_t list[2])
if (dicod_lang_lazy_prefs) {
if (list[0] && dico_list_intersect_p(dicod_lang_lazy_prefs, list[0],
- cmp_string_ci))
+ cmp_string_ci, NULL))
return 1;
if (list[1] && dico_list_intersect_p(dicod_lang_lazy_prefs, list[1],
- cmp_string_ci))
+ cmp_string_ci, NULL))
return 1;
return 0;
}
if (dicod_lang_prefs[0] && list[0]
- && !dico_list_intersect_p(dicod_lang_prefs[0], list[0], cmp_string_ci))
+ && !dico_list_intersect_p(dicod_lang_prefs[0], list[0],
+ cmp_string_ci, NULL))
return 0;
if (dicod_lang_prefs[1] && list[1]
- && !dico_list_intersect_p(dicod_lang_prefs[1], list[1], cmp_string_ci))
+ && !dico_list_intersect_p(dicod_lang_prefs[1], list[1],
+ cmp_string_ci, NULL))
return 0;
return 1;
}
diff --git a/dicod/main.c b/dicod/main.c
index 3bbd508..7eeb213 100644
--- a/dicod/main.c
+++ b/dicod/main.c
@@ -519,7 +519,7 @@ set_log_facility(enum grecs_callback_command cmd,
}
static int
-cmp_modinst_ident(const void *item, void *data)
+cmp_modinst_ident(const void *item, const void *data, void *closure)
{
const dicod_module_instance_t *inst = item;
if (!inst->ident)
@@ -589,7 +589,7 @@ load_module_cb(enum grecs_callback_command cmd,
}
static int
-cmp_database_name(const void *item, void *data)
+cmp_database_name(const void *item, const void *data, void *closure)
{
const dicod_database_t *db = item;
int rc;
@@ -635,7 +635,7 @@ set_database(enum grecs_callback_command cmd,
if (!database_list) {
database_list = xdico_list_create();
- dico_list_set_comparator (database_list, cmp_database_name);
+ dico_list_set_comparator (database_list, cmp_database_name, NULL);
}
if (dict->langlist[0] || dict->langlist[1])
/* Prevent dico_db_lang from being called */
@@ -1079,7 +1079,8 @@ strategy_cb(enum grecs_callback_command cmd,
if (!strat_forward) {
strat_forward = xdico_list_create();
dico_list_set_comparator (strat_forward,
- dico_strat_name_cmp);
+ dico_strat_name_cmp,
+ NULL);
dico_list_set_free_item(strat_forward,
dico_strat_free, NULL);
}
@@ -1434,7 +1435,7 @@ config_init(void)
grecs_parser_options = GRECS_OPTION_QUOTED_STRING_CONCAT;
modinst_list = xdico_list_create();
- dico_list_set_comparator(modinst_list, cmp_modinst_ident);
+ dico_list_set_comparator(modinst_list, cmp_modinst_ident, NULL);
dicod_builtin_module_init();
}
diff --git a/dicod/virtual.c b/dicod/virtual.c
index 08a6a6a..f884ce8 100644
--- a/dicod/virtual.c
+++ b/dicod/virtual.c
@@ -60,7 +60,7 @@ virtual_result_new(struct dico_handle_struct *vdb)
static int virtual_free_db(dico_handle_t hp);
static int
-db_name_cmp(const void *item, void *data)
+db_name_cmp(const void *item, const void *data, void *closure)
{
const dicod_database_t *db = item;
@@ -72,10 +72,12 @@ db_name_cmp(const void *item, void *data)
dicod_database_t *
find_database_all(const char *name)
{
- dico_list_comp_t oldcmp = dico_list_set_comparator(database_list,
- db_name_cmp);
- dicod_database_t *res = dico_list_locate(database_list, (void*) name);
- dico_list_set_comparator(database_list, oldcmp);
+ dicod_database_t *res;
+ dico_list_comp_t oldcmp = dico_list_get_comparator(database_list);
+ void *olddata = dico_list_get_comparator_data(database_list);
+ dico_list_set_comparator(database_list, db_name_cmp, NULL);
+ res = dico_list_locate(database_list, (void*) name);
+ dico_list_set_comparator(database_list, oldcmp, olddata);
return res;
}
diff --git a/include/dico/list.h b/include/dico/list.h
index ae6e3ab..8b8b938 100644
--- a/include/dico/list.h
+++ b/include/dico/list.h
@@ -26,7 +26,7 @@
#define DICO_LIST_COMPARE_TAIL 0x02
typedef int (*dico_list_iterator_t)(void *item, void *data);
-typedef int (*dico_list_comp_t)(const void *, void *);
+typedef int (*dico_list_comp_t)(const void *, const void *, void *);
dico_list_t dico_list_create(void);
void dico_list_destroy(dico_list_t *list);
@@ -36,9 +36,13 @@ int dico_list_get_flags(struct dico_list *list);
int dico_list_set_free_item(struct dico_list *list,
dico_list_iterator_t free_item, void *data);
-dico_list_comp_t dico_list_set_comparator(dico_list_t list,
- dico_list_comp_t comp);
+int dico_list_set_comparator(dico_list_t list,
+ dico_list_comp_t comp,
+ void *data);
+int dico_list_set_comparator_data(dico_list_t list, void *data);
dico_list_comp_t dico_list_get_comparator(dico_list_t list);
+void *dico_list_get_comparator_data(dico_list_t list);
+
void dico_list_iterate(dico_list_t list, dico_list_iterator_t itr, void *data);
void *dico_list_item(dico_list_t list, size_t n);
@@ -48,15 +52,18 @@ size_t dico_list_count(dico_list_t list);
int dico_list_append(dico_list_t list, void *data);
int dico_list_prepend(dico_list_t list, void *data);
int dico_list_insert_sorted(dico_list_t list, void *data);
-dico_list_t dico_list_intersect(dico_list_t a, dico_list_t b,
- dico_list_comp_t cmp);
-int dico_list_intersect_p(dico_list_t a, dico_list_t b, dico_list_comp_t cmp);
+dico_list_t dico_list_intersect(dico_list_t a, dico_list_t b,
+ dico_list_comp_t cmp, void *cmpdata);
+int dico_list_intersect_p(dico_list_t a, dico_list_t b,
+ dico_list_comp_t cmp, void *cmpdata);
#define dico_list_push dico_list_append
void *dico_list_pop(dico_list_t list);
-void *_dico_list_locate(dico_list_t list, void *data, dico_list_comp_t cmp);
-int _dico_list_remove(dico_list_t list, void *data, dico_list_comp_t cmp,
+void *_dico_list_locate(dico_list_t list, void *data,
+ dico_list_comp_t cmp, void *cmpdata);
+int _dico_list_remove(dico_list_t list, void *data,
+ dico_list_comp_t cmp, void *cmpdata,
void **pret);
void *dico_list_locate(dico_list_t list, void *data);
int dico_list_remove(dico_list_t list, void *data, void **pret);
diff --git a/include/dico/strat.h b/include/dico/strat.h
index 3356843..63e574d 100644
--- a/include/dico/strat.h
+++ b/include/dico/strat.h
@@ -36,7 +36,7 @@ struct dico_key {
int flags;
};
-int dico_strat_name_cmp(const void *item, void *data);
+int dico_strat_name_cmp(const void *item, const void *data, void *closure);
int dico_strat_free(void *item, void *data);
dico_strategy_t dico_strategy_create(const char *name, const char *descr);
diff --git a/include/dico/util.h b/include/dico/util.h
index 2c31e3e..d1bd731 100644
--- a/include/dico/util.h
+++ b/include/dico/util.h
@@ -21,5 +21,11 @@ char *dico_full_file_name(const char *dir, const char *file);
size_t dico_string_trim(char *buf, size_t len, int (*pred)(int c));
size_t dico_trim_nl(char *buf);
size_t dico_trim_ws(char *buf);
+int dico_sort(void *base, size_t nmemb, size_t size,
+ int (*comp)(const void *, const void *, void *),
+ void *closure);
+void *dico_bsearch(void *key, const void *base, size_t nelem, size_t elsize,
+ int (*comp) (const void *, const void *, void *),
+ void *closure);
#endif
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 1f1d1fc..03eee1c 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -27,6 +27,7 @@ libdico_la_SOURCES=\
argcv.c\
assoc.c\
base64.c\
+ bsearch.c\
crlfstr.c\
dbgstream.c\
diag.c\
@@ -43,6 +44,7 @@ libdico_la_SOURCES=\
logstream.c\
mapstream.c\
markup.c\
+ mergesort.c\
parseopt.c\
qp.c\
soundex.c\
@@ -57,7 +59,7 @@ libdico_la_SOURCES=\
util.c\
xlat.c
-libdico_la_LDFLAGS = -version-info 1:0:0
+libdico_la_LDFLAGS = -version-info 2:0:0
libdico_la_LIBADD = ../grecs/src/libgrecs.la
libxdico_a_SOURCES=\
diff --git a/lib/assoc.c b/lib/assoc.c
index 5f82898..dbff113 100644
--- a/lib/assoc.c
+++ b/lib/assoc.c
@@ -28,25 +28,26 @@ struct dico_assoc_list {
struct find_closure {
size_t count;
- const char *str;
};
static int
-assoc_key_cmp(const void *item, void *data)
+assoc_key_cmp(const void *item, const void *data, void *closure)
{
const struct dico_assoc *aptr = item;
- struct find_closure *clos = data;
- if (strcmp(aptr->key, clos->str) == 0 && --clos->count == 0)
+ char const *str = data;
+ struct find_closure *clos = closure;
+ if (strcmp(aptr->key, str) == 0 && --clos->count == 0)
return 0;
return 1;
}
static int
-assoc_key_cmp_ci(const void *item, void *data)
+assoc_key_cmp_ci(const void *item, const void *data, void *closure)
{
const struct dico_assoc *aptr = item;
- struct find_closure *clos = data;
- if (strcasecmp(aptr->key, clos->str) == 0 && --clos->count == 0)
+ char const *str = data;
+ struct find_closure *clos = closure;
+ if (strcasecmp(aptr->key, str) == 0 && --clos->count == 0)
return 0;
return 1;
}
@@ -75,7 +76,8 @@ dico_assoc_create(int flags)
} else {
dico_list_set_comparator(assoc->list,
(flags & DICO_ASSOC_CI) ?
- assoc_key_cmp_ci : assoc_key_cmp);
+ assoc_key_cmp_ci : assoc_key_cmp,
+ NULL);
dico_list_set_free_item(assoc->list, assoc_free, NULL);
}
}
@@ -119,11 +121,15 @@ struct dico_assoc *
_dico_assoc_find_n(dico_assoc_list_t assoc, const char *key, size_t n)
{
struct find_closure clos;
+ struct dico_assoc *res;
+
if (!assoc || n == 0)
return NULL;
clos.count = n;
- clos.str = key;
- return dico_list_locate(assoc->list, &clos);
+ dico_list_set_comparator_data(assoc->list, &clos);
+ res = dico_list_locate(assoc->list, (void*)key);
+ dico_list_set_comparator_data(assoc->list, NULL);
+ return res;
}
const char *
@@ -146,8 +152,9 @@ dico_assoc_remove_n(dico_assoc_list_t assoc, const char *key, size_t n)
if (n == 0)
return;
clos.count = n;
- clos.str = key;
- dico_list_remove(assoc->list, &clos, NULL);
+ dico_list_set_comparator_data(assoc->list, &clos);
+ dico_list_remove(assoc->list, (void*)key, NULL);
+ dico_list_set_comparator_data(assoc->list, NULL);
}
void
diff --git a/lib/bsearch.c b/lib/bsearch.c
new file mode 100644
index 0000000..0e07efd
--- /dev/null
+++ b/lib/bsearch.c
@@ -0,0 +1,61 @@
+/* This file is part of GNU Dico
+ Copyright (C) 2018 Sergey Poznyakoff
+
+ GNU Dico 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 3, or (at your option)
+ any later version.
+
+ GNU Dico 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 GNU Dico. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+#include "dico.h"
+
+/* Searches a sorted array of NELEM objects, the initial element being
+ pointed to by BASE, for a member that matches the object pointed to
+ by KEY. The size of each array member is given by ELSIZE. The array
+ must be sorted in ascending order according to the comparison function
+ COMP.
+
+ The COMP function is called with three arguments: pointer to the
+ key object, pointer to an array element, and CLOSURE. It should return
+ negative value, 0, or positive value, depending on whether the key is
+ found, respectively, to be less than, to match, or to be greater than
+ the array member. The CLOSURE argument can be used to supply additional
+ data to the COMP function. Its use is left to the discretion of the
+ programmer.
+
+ If the array contains one or more matching entries, the function
+ is guaranteed to return the address of the first one.
+ */
+void *
+dico_bsearch(void *key, const void *base, size_t nelem, size_t elsize,
+ int (*comp) (const void *, const void *, void *),
+ void *closure)
+{
+ char const *l = (char const*)base;
+ char const *r = l + nelem * elsize;
+ char const *s;
+ int found = 0;
+
+ while (l < r) {
+ s = l + (((r - l) / elsize) >> 1) * elsize;
+ int rc = comp(key, s, closure);
+ if (rc > 0)
+ l = s + elsize;
+ else {
+ if (rc == 0)
+ found = 1;
+ r = s;
+ }
+ }
+ return found ? (void*) l : NULL;
+}
diff --git a/lib/list.c b/lib/list.c
index df72da0..cbdb406 100644
--- a/lib/list.c
+++ b/lib/list.c
@@ -32,7 +32,8 @@ struct dico_list {
struct list_entry *head, *tail;
int flags;
struct iterator *itr;
- dico_list_comp_t comp;
+ dico_list_comp_t comp_fun;
+ void *comp_data;
dico_list_iterator_t free_item;
void *free_data;
};
@@ -46,7 +47,7 @@ struct iterator {
};
static int
-cmp_ptr(const void *a, void *b)
+cmp_ptr(const void *a, const void *b, void *data)
{
return a != b;
}
@@ -60,7 +61,8 @@ dico_list_create(void)
p->head = p->tail = NULL;
p->flags = 0;
p->itr = NULL;
- p->comp = cmp_ptr;
+ p->comp_fun = cmp_ptr;
+ p->comp_data = NULL;
p->free_item = NULL;
p->free_data = NULL;
}
@@ -331,21 +333,31 @@ dico_list_set_free_item(struct dico_list *list,
return 0;
}
-dico_list_comp_t
-dico_list_set_comparator(struct dico_list *list, dico_list_comp_t comp)
+int
+dico_list_set_comparator(struct dico_list *list, dico_list_comp_t comp,
+ void *data)
{
- dico_list_comp_t prev;
-
if (!list) {
errno = EINVAL;
- return NULL;
+ return -1;
}
- prev = list->comp;
- list->comp = comp;
- return prev;
+ list->comp_fun = comp;
+ list->comp_data = data;
+ return 0;
}
int
+dico_list_set_comparator_data(dico_list_t list, void *data)
+{
+ if (!list) {
+ errno = EINVAL;
+ return -1;
+ }
+ list->comp_data = data;
+ return 0;
+}
+
+int
dico_list_set_flags(struct dico_list *list, int flags)
{
if (!list) {
@@ -364,7 +376,6 @@ dico_list_get_flags(struct dico_list *list)
return 0;
}
-
dico_list_comp_t
dico_list_get_comparator(struct dico_list *list)
{
@@ -372,7 +383,17 @@ dico_list_get_comparator(struct dico_list *list)
errno = EINVAL;
return NULL;
}
- return list->comp;
+ return list->comp_fun;
+}
+
+void *
+dico_list_get_comparator_data(struct dico_list *list)
+{
+ if (!list) {
+ errno = EINVAL;
+ return NULL;
+ }
+ return list->comp_data;
}
int
@@ -417,8 +438,10 @@ dico_list_append(struct dico_list *list, void *data)
errno = EINVAL;
return 1;
}
- if ((list->flags & DICO_LIST_COMPARE_TAIL) && list->comp
- && list->tail && list->comp(list->tail->data, data) == 0) {
+ if ((list->flags & DICO_LIST_COMPARE_TAIL)
+ && list->comp_fun
+ && list->tail
+ && list->comp_fun(list->tail->data, data, list->comp_data) == 0) {
errno = EEXIST;
return 1;
}
@@ -432,8 +455,10 @@ dico_list_prepend(struct dico_list *list, void *data)
errno = EINVAL;
return 1;
}
- if ((list->flags & DICO_LIST_COMPARE_HEAD) && list->comp
- && list->head && list->comp(list->head->data, data) == 0) {
+ if ((list->flags & DICO_LIST_COMPARE_HEAD)
+ && list->comp_fun
+ && list->head
+ && list->comp_fun(list->head->data, data, list->comp_data) == 0) {
errno = EEXIST;
return 1;
}
@@ -469,7 +494,8 @@ _dico_list_remove_item(struct dico_list *list, struct list_entry *p,
}
int
-_dico_list_remove(struct dico_list *list, void *data, dico_list_comp_t cmp,
+_dico_list_remove(struct dico_list *list, void *data,
+ dico_list_comp_t cmp, void *cmpdata,
void **pptr)
{
struct list_entry *p;
@@ -482,7 +508,7 @@ _dico_list_remove(struct dico_list *list, void *data, dico_list_comp_t cmp,
if (!cmp)
cmp = cmp_ptr;
for (p = list->head; p; p = p->next)
- if (cmp(p->data, data) == 0)
+ if (cmp(p->data, data, cmpdata) == 0)
break;
if (!p) {
@@ -502,7 +528,7 @@ dico_list_remove(struct dico_list *list, void *data, void **pret)
errno = EINVAL;
return 1;
}
- return _dico_list_remove(list, data, list->comp, pret);
+ return _dico_list_remove(list, data, list->comp_fun, list->comp_data, pret);
}
void *
@@ -535,7 +561,8 @@ dico_list_iterate(struct dico_list *list, dico_list_iterator_t func,
}
void *
-_dico_list_locate(struct dico_list *list, void *data, dico_list_comp_t cmp)
+_dico_list_locate(struct dico_list *list, void *data,
+ dico_list_comp_t cmp, void *cmpdata)
{
struct list_entry *cur;
if (!list)
@@ -543,7 +570,7 @@ _dico_list_locate(struct dico_list *list, void *data, dico_list_comp_t cmp)
if (!cmp)
cmp = cmp_ptr;
for (cur = list->head; cur; cur = cur->next)
- if (cmp(cur->data, data) == 0)
+ if (cmp(cur->data, data, cmpdata) == 0)
break;
return cur ? cur->data : NULL;
}
@@ -553,12 +580,12 @@ dico_list_locate(struct dico_list *list, void *data)
{
if (!list)
return NULL;
- return _dico_list_locate(list, data, list->comp);
+ return _dico_list_locate(list, data, list->comp_fun, list->comp_data);
}
int
_dico_list_insert_sorted(struct dico_list *list, void *data,
- dico_list_comp_t cmp)
+ dico_list_comp_t cmp, void *cmpdata)
{
int rc;
struct list_entry *cur;
@@ -576,7 +603,7 @@ _dico_list_insert_sorted(struct dico_list *list, void *data,
return _dico_list_append(list, data);
for (cur = list->head, i = 0; cur; cur = cur->next, i++) {
- int res = cmp(cur->data, data);
+ int res = cmp(cur->data, data, cmpdata);
if (res > 0)
break;
else if (res == 0 && list->flags)
@@ -617,7 +644,8 @@ dico_list_insert_sorted(struct dico_list *list, void *data)
errno = EINVAL;
return 1;
}
- return _dico_list_insert_sorted(list, data, list->comp);
+ return _dico_list_insert_sorted(list, data,
+ list->comp_fun, list->comp_data);
}
/* Computes an intersection of the two lists. The resulting list
@@ -625,7 +653,8 @@ dico_list_insert_sorted(struct dico_list *list, void *data)
in the list B. Elements are compared using function CMP.
The resulting list preserves the ordering of A. */
dico_list_t
-dico_list_intersect(dico_list_t a, dico_list_t b, dico_list_comp_t cmp)
+dico_list_intersect(dico_list_t a, dico_list_t b,
+ dico_list_comp_t cmp, void *cmpdata)
{
dico_list_t res;
dico_iterator_t itr = dico_list_iterator(a);
@@ -637,7 +666,7 @@ dico_list_intersect(dico_list_t a, dico_list_t b, dico_list_comp_t cmp)
if (!res)
return NULL;
for (p = dico_iterator_first(itr); p; p = dico_iterator_next(itr)) {
- if (_dico_list_locate(b, p, cmp))
+ if (_dico_list_locate(b, p, cmp, cmpdata))
_dico_list_append(res, p); /* FIXME: check return, and? */
}
dico_iterator_destroy (&itr);
@@ -646,14 +675,15 @@ dico_list_intersect(dico_list_t a, dico_list_t b, dico_list_comp_t cmp)
/* Return true if there exists a non-empty intersection of lists A and B. */
int
-dico_list_intersect_p(dico_list_t a, dico_list_t b, dico_list_comp_t cmp)
+dico_list_intersect_p(dico_list_t a, dico_list_t b,
+ dico_list_comp_t cmp, void *cmpdata)
{
dico_iterator_t itr = dico_list_iterator(a);
void *p;
int rc = 0;
for (p = dico_iterator_first(itr); p; p = dico_iterator_next(itr)) {
- if (_dico_list_locate(b, p, cmp)) {
+ if (_dico_list_locate(b, p, cmp, cmpdata)) {
rc = 1;
break;
}
diff --git a/lib/markup.c b/lib/markup.c
index 8e5ffe2..714a74f 100644
--- a/lib/markup.c
+++ b/lib/markup.c
@@ -25,7 +25,7 @@ const char *dico_markup_type = "none";
dico_list_t dico_markup_list;
static int
-cmp_markup_name(const void *item, void *data)
+cmp_markup_name(const void *item, const void *data, void *ignored)
{
return strcasecmp((char*)item, (char*)data);
}
@@ -55,7 +55,7 @@ dico_markup_register(const char *name)
dico_markup_list = dico_list_create();
if (!dico_markup_list)
return ENOMEM;
- dico_list_set_comparator(dico_markup_list, cmp_markup_name);
+ dico_list_set_comparator(dico_markup_list, cmp_markup_name, NULL);
}
if (!dico_markup_lookup(name)) {
diff --git a/lib/mergesort.c b/lib/mergesort.c
new file mode 100644
index 0000000..6c35283
--- /dev/null
+++ b/lib/mergesort.c
@@ -0,0 +1,101 @@
+/* This file is part of GNU Dico
+ Copyright (C) 2018 Sergey Poznyakoff
+
+ GNU Dico 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 3, or (at your option)
+ any later version.
+
+ GNU Dico 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 GNU Dico. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+#include "dico.h"
+#include <string.h>
+
+static void *mergesort(void *a, void *b, size_t nmemb, size_t size,
+ int (*comp)(const void *, const void *, void *),
+ void *closure);
+static void merge(void *source, void *work, size_t size,
+ size_t left, size_t right, size_t end,
+ int (*comp)(const void *, const void *, void *),
+ void *closure);
+
+int
+dico_sort(void *base, size_t nmemb, size_t size,
+ int (*comp)(const void *, const void *, void *),
+ void *closure)
+{
+ void *tmp, *res;
+
+ tmp = calloc(nmemb, size);
+ if (!tmp)
+ return -1;
+ res = mergesort(base, tmp, nmemb, size, comp, closure);
+ if (res != base)
+ memcpy(base, res, nmemb * size);
+ free(tmp);
+ return 0;
+}
+
+static inline size_t
+min(size_t a, size_t b)
+{
+ return a < b ? a : b;
+}
+
+static void *
+mergesort(void *a, void *b, size_t nmemb, size_t size,
+ int (*comp)(const void *, const void *, void *),
+ void *closure)
+{
+ size_t width;
+
+ for (width = 1; width < nmemb; width <<= 1) {
+ size_t i;
+ void *t;
+
+ for (i = 0; i < nmemb; i += 2 * width) {
+ merge(a, b, size,
+ i, min(i + width, nmemb), min(i + 2 * width, nmemb),
+ comp, closure);
+ }
+ t = a;
+ a = b;
+ b = t;
+ }
+ return a;
+}
+
+static