diff options
author | Sergey Poznyakoff <gray@gnu.org> | 2018-09-15 17:47:49 +0300 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org> | 2018-09-15 18:17:59 +0300 |
commit | a7be650dc0b3528f1ca75bcb03fc4a94c2d65c49 (patch) | |
tree | 3094570ed3e59c628a123a92281ea3ae0a4a6a87 | |
parent | 1cf9d2d93642283bf7a338d2541eb5a5b396dd0c (diff) | |
download | dico-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.c | 4 | ||||
-rw-r--r-- | dicod/acl.c | 4 | ||||
-rw-r--r-- | dicod/alias.c | 4 | ||||
-rw-r--r-- | dicod/capa.c | 4 | ||||
-rw-r--r-- | dicod/commands.c | 8 | ||||
-rw-r--r-- | dicod/gsasl.c | 6 | ||||
-rw-r--r-- | dicod/lang.c | 12 | ||||
-rw-r--r-- | dicod/main.c | 11 | ||||
-rw-r--r-- | dicod/virtual.c | 12 | ||||
-rw-r--r-- | include/dico/list.h | 23 | ||||
-rw-r--r-- | include/dico/strat.h | 2 | ||||
-rw-r--r-- | include/dico/util.h | 6 | ||||
-rw-r--r-- | lib/Makefile.am | 4 | ||||
-rw-r--r-- | lib/assoc.c | 31 | ||||
-rw-r--r-- | lib/bsearch.c | 61 | ||||
-rw-r--r-- | lib/list.c | 90 | ||||
-rw-r--r-- | lib/markup.c | 4 | ||||
-rw-r--r-- | lib/mergesort.c | 101 | ||||
-rw-r--r-- | lib/strat.c | 4 | ||||
-rw-r--r-- | lib/tests/listop.c | 4 | ||||
-rw-r--r-- | lib/udb.c | 4 | ||||
-rw-r--r-- | modules/dict.org/dictorg.c | 95 | ||||
-rw-r--r-- | modules/gcide/gcide.c | 5 | ||||
-rw-r--r-- | modules/wordnet/wordnet.c | 6 |
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; +} @@ -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 |