This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GNU Mailutils".
http://git.savannah.gnu.org/cgit/mailutils.git/commit/?id=da63ec15b4c8fb3084075730332a8d20a9af374f The branch, master has been updated via da63ec15b4c8fb3084075730332a8d20a9af374f (commit) from eae41894c2614ddc2c3732014cb62bf68ab4e16a (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit da63ec15b4c8fb3084075730332a8d20a9af374f Author: Sergey Poznyakoff <g...@gnu.org.ua> Date: Wed Dec 28 20:57:26 2016 +0200 Provide sort function for associative arrays. The mu_assoc_sort_r call sorts the elements of mu_assoc_t for subsequent iterative access. Random access facilities remain undistrurbed. * include/mailutils/assoc.h (mu_assoc_comparator_t): New typedef. (mu_assoc_sort_r): New proto. * libmailutils/base/assoc.c (mu_assoc_sort_r): New function. * libmailutils/tests/mimehdr.c: Sort assoc elements prior to iteration. ----------------------------------------------------------------------- Summary of changes: include/mailutils/assoc.h | 7 ++ libmailutils/base/assoc.c | 141 +++++++++++++++++++++++++++++++++++++---- libmailutils/tests/.gitignore | 2 + libmailutils/tests/mimehdr.c | 45 +++---------- 4 files changed, 144 insertions(+), 51 deletions(-) diff --git a/include/mailutils/assoc.h b/include/mailutils/assoc.h index 5db9f85..00514c0 100644 --- a/include/mailutils/assoc.h +++ b/include/mailutils/assoc.h @@ -46,6 +46,13 @@ int mu_assoc_is_empty (mu_assoc_t assoc); typedef int (*mu_assoc_action_t) (char const *, void *, void *); int mu_assoc_foreach (mu_assoc_t assoc, mu_assoc_action_t action, void *data); + +typedef int (*mu_assoc_comparator_t) (const char *, const void *, + const char *, const void *, + void *); + +int mu_assoc_sort_r (mu_assoc_t assoc, mu_assoc_comparator_t cmp, void *data); + #ifdef __cplusplus } diff --git a/libmailutils/base/assoc.c b/libmailutils/base/assoc.c index 8b42f82..d595ee8 100644 --- a/libmailutils/base/assoc.c +++ b/libmailutils/base/assoc.c @@ -625,20 +625,17 @@ mu_assoc_get_iterator (mu_assoc_t assoc, mu_iterator_t *piterator) int mu_assoc_count (mu_assoc_t assoc, size_t *pcount) { - mu_iterator_t itr; - int rc; - size_t count = 0; - - if (!assoc || !pcount) - return EINVAL; - rc = mu_assoc_get_iterator (assoc, &itr); - if (rc) - return rc; - for (mu_iterator_first (itr); !mu_iterator_is_done (itr); - mu_iterator_next (itr)) - count++; - mu_iterator_destroy (&itr); - *pcount = count; + size_t length = 0; + + if (!pcount) + return MU_ERR_OUT_PTR_NULL; + if (assoc) + { + struct _mu_assoc_elem *elt; + for (elt = assoc->head; elt; elt = elt->next) + length++; + } + *pcount = length; return 0; } @@ -676,3 +673,119 @@ mu_assoc_foreach (mu_assoc_t assoc, mu_assoc_action_t action, void *data) mu_iterator_destroy (&itr); return rc; } + +/* Merges the two NULL-terminated lists, LEFT and RIGHT, using CMP for + element comparison. DATA supplies call-specific data for CMP. + + Both LEFT and RIGHT are treated as singly-linked lists, with NEXT pointing + to the successive element. PREV pointers are ignored. + + Returns the resulting list. + */ +static struct _mu_assoc_elem * +merge (struct _mu_assoc_elem *left, struct _mu_assoc_elem *right, + mu_assoc_comparator_t cmp, void *data) +{ + struct _mu_assoc_elem *head = NULL, **tailptr = &head, *tmp; + + while (left && right) + { + if (cmp (left->name, left->data, right->name, right->data, data) < 0) + { + tmp = left->next; + *tailptr = left; + tailptr = &left->next; + left = tmp; + } + else + { + tmp = right->next; + *tailptr = right; + tailptr = &right->next; + right = tmp; + } + } + + *tailptr = left ? left : right; + + return head; +} + +/* Sort the singly-linked LIST of LENGTH elements using merge sort algorithm. + Elements are compared using the CMP function with DATA pointing to + call-specific data. + The elements of LIST are linked by the NEXT pointer. The NEXT pointer of + the last element (LIST[LENGTH], 1-based) must be NULL. + + Returns the resulting list. + + Side-effects: PREV pointers in the returned list are messed up. +*/ +static struct _mu_assoc_elem * +merge_sort (struct _mu_assoc_elem *list, size_t length, + mu_assoc_comparator_t cmp, void *data) +{ + struct _mu_assoc_elem *left, *right; + size_t left_len, right_len, i; + struct _mu_assoc_elem *elt; + + if (length == 1) + return list; + + if (length == 2) + { + elt = list->next; + if (cmp (list->name, list->data, elt->name, elt->data, cmp) > 0) + { + elt->next = list; + list->next = NULL; + return elt; + } + return list; + } + + left = list; + left_len = (length + 1) / 2; + + right_len = length / 2; + for (elt = list, i = left_len - 1; i; i--) + elt = elt->next; + + right = elt->next; + elt->next = NULL; + + left = merge_sort (left, left_len, cmp, data); + right = merge_sort (right, right_len, cmp, data); + + return merge (left, right, cmp, data); +} + +/* Sort the linked list of elements in ASSOC using merge sort. CMP points + to the function to use for comparing two elements. DATA supplies call- + specific data for CMP. +*/ +int +mu_assoc_sort_r (mu_assoc_t assoc, mu_assoc_comparator_t cmp, void *data) +{ + struct _mu_assoc_elem *head, *prev, *p; + size_t length; + + if (!assoc) + return EINVAL; + if (!cmp) + return 0; + + mu_assoc_count (assoc, &length); + head = merge_sort (assoc->head, length, cmp, data); + /* The above call leaves PREV pointers in inconsistent state. Fix them + up: */ + for (prev = NULL, p = head; p; prev = p, p = p->next) + p->prev = prev; + + /* Update list head and tail */ + assoc->head = head; + assoc->tail = prev; + + return 0; +} + diff --git a/libmailutils/tests/.gitignore b/libmailutils/tests/.gitignore index b8c5ee6..10ebd32 100644 --- a/libmailutils/tests/.gitignore +++ b/libmailutils/tests/.gitignore @@ -1,6 +1,7 @@ atconfig atlocal cidr +conttype package.m4 testsuite testsuite.dir @@ -14,6 +15,7 @@ fltst fsaf fsaftomod fsfolder +globtest imapio listop mailcap diff --git a/libmailutils/tests/mimehdr.c b/libmailutils/tests/mimehdr.c index 2564de6..67b4b42 100644 --- a/libmailutils/tests/mimehdr.c +++ b/libmailutils/tests/mimehdr.c @@ -33,27 +33,19 @@ #include <mailutils/error.h> #include <mailutils/errno.h> -struct named_param -{ - const char *name; - struct mu_mime_param const *param; -}; - static int -sort_names (void const *a, void const *b) +sort_names (char const *aname, void const *adata, + char const *bname, void const *bdata, void *data) { - struct named_param const *pa = a; - struct named_param const *pb = b; - return mu_c_strcasecmp (pa->name, pb->name); + return mu_c_strcasecmp (aname, bname); } static int -print_named_param (void *item, void *data) +print_param (const char *name, void *item, void *data) { - struct named_param const *p = item; - struct mu_mime_param const *param = p->param; + struct mu_mime_param *param = item; - mu_printf ("%s", p->name); + mu_printf ("%s", name); if (param->lang) mu_printf ("(lang:%s/%s)", param->lang, param->cset); mu_printf ("=%s\n", param->value); @@ -68,8 +60,6 @@ main (int argc, char **argv) mu_transport_t trans[2]; char *value; mu_assoc_t assoc; - mu_iterator_t itr; - mu_list_t list; char *charset = NULL; mu_set_program_name (argv[0]); @@ -108,27 +98,8 @@ main (int argc, char **argv) MU_ASSERT (mu_mime_header_parse ((char*)trans[0], charset, &value, &assoc)); mu_printf ("%s\n", value); - MU_ASSERT (mu_list_create (&list)); - MU_ASSERT (mu_assoc_get_iterator (assoc, &itr)); - for (mu_iterator_first (itr); !mu_iterator_is_done (itr); - mu_iterator_next (itr)) - { - const char *name; - struct mu_mime_param *p; - struct named_param *np; - - mu_iterator_current_kv (itr, (const void **)&name, (void**)&p); - np = malloc (sizeof (*np)); - if (!np) - abort (); - np->name = name; - np->param = p; - MU_ASSERT (mu_list_append (list, np)); - } - mu_iterator_destroy (&itr); - - mu_list_sort (list, sort_names); - mu_list_foreach (list, print_named_param, NULL); + mu_assoc_sort_r (assoc, sort_names, NULL); + mu_assoc_foreach (assoc, print_param, NULL); return 0; } hooks/post-receive -- GNU Mailutils _______________________________________________ Commit-mailutils mailing list Commit-mailutils@gnu.org https://lists.gnu.org/mailman/listinfo/commit-mailutils
