Re: [MoM] Re: kmer-tools
[CCing libkaz maintainer
Balint, the Debian Med team wants to build a package that contains
a libkaz code copy with a patch]
Hi,
On Fri, May 15, 2015 at 11:06:18PM -0700, Afif Elghraoui wrote:
> >>>OK, feel free to discuss the diff here in case you might be in doubt.
>
> I'm not sure how useful this patch of kazlib (attached) is for
> forwarding. It seems to me too much like a workaround. According to
> the comments and what I see in the diff, all it does is make the
> data structure work with a pointer rather than the object itself
> (also represented by a pointer). The stated objective of this is to
> maintain compatibility with qsort, but I don't know why the result
> could not have been taken as is and passed as an address to qsort.
>
> This also seems like something that would break the code if it is
> not included, so I'm not sure how tests would have passed using the
> Debian packaged version of kazlib. I should probably check the build
> logs for anything suspicious that may have been ignored.
>
> I think the next step would be to bring this up with kmer upstream
> and consider patching the kmer source to work with kazlib the way it
> is. What do you think? Offhand I don't think patching kmer to
> achieve the same ends would be very difficult.
I personally would try to convince kmer upstream to adapt to official
kazlib.
Kind regards
Andreas.
> --- ../../../kazlib-1.20/dict.c 2000-11-12 17:36:44.000000000 -0800
> +++ dict.c 2006-12-17 21:51:28.000000000 -0800
> @@ -14,19 +14,21 @@
> * into proprietary software; there is no requirement for such software to
> * contain a copyright notice related to this source.
> *
> - * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
> - * $Name: kazlib_1_20 $
> */
>
> +#define NDEBUG
> +
> +#include <stdio.h>
> #include <stdlib.h>
> #include <stddef.h>
> #include <assert.h>
> #define DICT_IMPLEMENTATION
> #include "dict.h"
>
> -#ifdef KAZLIB_RCSID
> -static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
> -#endif
> +// bpw 20050309 define this to use a qsort(3) compatible sort function,
> +// requiring two dereferences to get the data instead of one.
> +//
> +#define BE_QSORT_COMPATIBLE
>
> /*
> * These macros provide short convenient names for structure members,
> @@ -153,14 +155,24 @@
>
> if (dict->dupes) {
> while (first && (next = dict_next(dict, first))) {
> +#ifdef BE_QSORT_COMPATIBLE
> + if (dict->compare(&first->key, &next->key) > 0)
> + return 0;
> +#else
> if (dict->compare(first->key, next->key) > 0)
> return 0;
> +#endif
> first = next;
> }
> } else {
> while (first && (next = dict_next(dict, first))) {
> +#ifdef BE_QSORT_COMPATIBLE
> + if (dict->compare(&first->key, &next->key) >= 0)
> + return 0;
> +#else
> if (dict->compare(first->key, next->key) >= 0)
> return 0;
> +#endif
> first = next;
> }
> }
> @@ -383,22 +395,22 @@
>
> /* check that the sentinel node and root node are black */
> if (root->color != dnode_black)
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Root node not black!\n"));
> if (nil->color != dnode_black)
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Nil node not black!\n"));
> if (nil->right != nil)
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Nul->right not Nil!\n"));
> /* nil->left is the root node; check that its parent pointer is nil */
> if (nil->left->parent != nil)
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Nul->left->parent is not Nil!\n"));
> /* perform a weak test that the tree is a binary search tree */
> if (!verify_bintree(dict))
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Not a binary search tree!\n"));
> /* verify that the tree is a red-black tree */
> if (!verify_redblack(nil, root))
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Not a red-black tree!\n"));
> if (verify_node_count(nil, root) != dict_count(dict))
> - return 0;
> + return(0 * fprintf(stderr, "dict_verify()-- Node count is wrong!\n"));
> return 1;
> }
>
> @@ -444,7 +456,11 @@
> /* simple binary search adapted for trees that contain duplicate keys */
>
> while (root != nil) {
> +#ifdef BE_QSORT_COMPATIBLE
> + result = dict->compare(&key, &root->key);
> +#else
> result = dict->compare(key, root->key);
> +#endif
> if (result < 0)
> root = root->left;
> else if (result > 0)
> @@ -456,8 +472,13 @@
> do {
> saved = root;
> root = root->left;
> +#ifdef BE_QSORT_COMPATIBLE
> + while (root != nil && dict->compare(&key, &root->key))
> + root = root->right;
> +#else
> while (root != nil && dict->compare(key, root->key))
> root = root->right;
> +#endif
> } while (root != nil);
> return saved;
> }
> @@ -479,7 +500,11 @@
> dnode_t *tentative = 0;
>
> while (root != nil) {
> +#ifdef BE_QSORT_COMPATIBLE
> + int result = dict->compare(&key, &root->key);
> +#else
> int result = dict->compare(key, root->key);
> +#endif
>
> if (result > 0) {
> root = root->right;
> @@ -511,7 +536,11 @@
> dnode_t *tentative = 0;
>
> while (root != nil) {
> +#ifdef BE_QSORT_COMPATIBLE
> + int result = dict->compare(&key, &root->key);
> +#else
> int result = dict->compare(key, root->key);
> +#endif
>
> if (result < 0) {
> root = root->left;
> @@ -555,7 +584,11 @@
>
> while (where != nil) {
> parent = where;
> +#ifdef BE_QSORT_COMPATIBLE
> + result = dict->compare(&key, &where->key);
> +#else
> result = dict->compare(key, where->key);
> +#endif
> /* trap attempts at duplicate key insertion unless it's explicitly allowed */
> assert (dict->dupes || result != 0);
> if (result < 0)
> @@ -1038,14 +1071,21 @@
> assert (!dnode_is_in_a_dict(newnode));
> assert (dict->nodecount < dict->maxcount);
>
> - #ifndef NDEBUG
> +#ifndef NDEBUG
> if (dict->nodecount > 0) {
> +#ifdef BE_QSORT_COMPATIBLE
> + if (dict->dupes)
> + assert (dict->compare(&nil->left->key, &key) <= 0);
> + else
> + assert (dict->compare(&nil->left->key, &key) < 0);
> +#else
> if (dict->dupes)
> assert (dict->compare(nil->left->key, key) <= 0);
> else
> assert (dict->compare(nil->left->key, key) < 0);
> +#endif
> }
> - #endif
> +#endif
>
> newnode->key = key;
> nil->right->left = newnode;
> @@ -1150,10 +1190,17 @@
>
> for (;;) {
> if (leftnode != NULL && rightnode != NULL) {
> +#ifdef BE_QSORT_COMPATIBLE
> + if (dest->compare(&leftnode->key, &rightnode->key) < 0)
> + goto copyleft;
> + else
> + goto copyright;
> +#else
> if (dest->compare(leftnode->key, rightnode->key) < 0)
> goto copyleft;
> else
> goto copyright;
> +#endif
> } else if (leftnode != NULL) {
> goto copyleft;
> } else if (rightnode != NULL) {
> @@ -1166,9 +1213,9 @@
> copyleft:
> {
> dnode_t *next = dict_next(dest, leftnode);
> - #ifndef NDEBUG
> + #ifndef NDEBUG
> leftnode->left = NULL; /* suppress assertion in dict_load_next */
> - #endif
> + #endif
> dict_load_next(&load, leftnode, leftnode->key);
> leftnode = next;
> continue;
> @@ -1177,9 +1224,9 @@
> copyright:
> {
> dnode_t *next = dict_next(source, rightnode);
> - #ifndef NDEBUG
> +#ifndef NDEBUG
> rightnode->left = NULL;
> - #endif
> +#endif
> dict_load_next(&load, rightnode, rightnode->key);
> rightnode = next;
> continue;
> @@ -1189,308 +1236,3 @@
> dict_clear(source);
> dict_load_end(&load);
> }
> -
> -#ifdef KAZLIB_TEST_MAIN
> -
> -#include <stdio.h>
> -#include <string.h>
> -#include <ctype.h>
> -#include <stdarg.h>
> -
> -typedef char input_t[256];
> -
> -static int tokenize(char *string, ...)
> -{
> - char **tokptr;
> - va_list arglist;
> - int tokcount = 0;
> -
> - va_start(arglist, string);
> - tokptr = va_arg(arglist, char **);
> - while (tokptr) {
> - while (*string && isspace((unsigned char) *string))
> - string++;
> - if (!*string)
> - break;
> - *tokptr = string;
> - while (*string && !isspace((unsigned char) *string))
> - string++;
> - tokptr = va_arg(arglist, char **);
> - tokcount++;
> - if (!*string)
> - break;
> - *string++ = 0;
> - }
> - va_end(arglist);
> -
> - return tokcount;
> -}
> -
> -static int comparef(const void *key1, const void *key2)
> -{
> - return strcmp(key1, key2);
> -}
> -
> -static char *dupstring(char *str)
> -{
> - int sz = strlen(str) + 1;
> - char *new = malloc(sz);
> - if (new)
> - memcpy(new, str, sz);
> - return new;
> -}
> -
> -static dnode_t *new_node(void *c)
> -{
> - static dnode_t few[5];
> - static int count;
> -
> - if (count < 5)
> - return few + count++;
> -
> - return NULL;
> -}
> -
> -static void del_node(dnode_t *n, void *c)
> -{
> -}
> -
> -static int prompt = 0;
> -
> -static void construct(dict_t *d)
> -{
> - input_t in;
> - int done = 0;
> - dict_load_t dl;
> - dnode_t *dn;
> - char *tok1, *tok2, *val;
> - const char *key;
> - char *help =
> - "p turn prompt on\n"
> - "q finish construction\n"
> - "a <key> <val> add new entry\n";
> -
> - if (!dict_isempty(d))
> - puts("warning: dictionary not empty!");
> -
> - dict_load_begin(&dl, d);
> -
> - while (!done) {
> - if (prompt)
> - putchar('>');
> - fflush(stdout);
> -
> - if (!fgets(in, sizeof(input_t), stdin))
> - break;
> -
> - switch (in[0]) {
> - case '?':
> - puts(help);
> - break;
> - case 'p':
> - prompt = 1;
> - break;
> - case 'q':
> - done = 1;
> - break;
> - case 'a':
> - if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
> - puts("what?");
> - break;
> - }
> - key = dupstring(tok1);
> - val = dupstring(tok2);
> - dn = dnode_create(val);
> -
> - if (!key || !val || !dn) {
> - puts("out of memory");
> - free((void *) key);
> - free(val);
> - if (dn)
> - dnode_destroy(dn);
> - }
> -
> - dict_load_next(&dl, dn, key);
> - break;
> - default:
> - putchar('?');
> - putchar('\n');
> - break;
> - }
> - }
> -
> - dict_load_end(&dl);
> -}
> -
> -int main(void)
> -{
> - input_t in;
> - dict_t darray[10];
> - dict_t *d = &darray[0];
> - dnode_t *dn;
> - int i;
> - char *tok1, *tok2, *val;
> - const char *key;
> -
> - char *help =
> - "a <key> <val> add value to dictionary\n"
> - "d <key> delete value from dictionary\n"
> - "l <key> lookup value in dictionary\n"
> - "( <key> lookup lower bound\n"
> - ") <key> lookup upper bound\n"
> - "# <num> switch to alternate dictionary (0-9)\n"
> - "j <num> <num> merge two dictionaries\n"
> - "f free the whole dictionary\n"
> - "k allow duplicate keys\n"
> - "c show number of entries\n"
> - "t dump whole dictionary in sort order\n"
> - "m make dictionary out of sorted items\n"
> - "p turn prompt on\n"
> - "s switch to non-functioning allocator\n"
> - "q quit";
> -
> - for (i = 0; i < sizeof darray / sizeof *darray; i++)
> - dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
> -
> - for (;;) {
> - if (prompt)
> - putchar('>');
> - fflush(stdout);
> -
> - if (!fgets(in, sizeof(input_t), stdin))
> - break;
> -
> - switch(in[0]) {
> - case '?':
> - puts(help);
> - break;
> - case 'a':
> - if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
> - puts("what?");
> - break;
> - }
> - key = dupstring(tok1);
> - val = dupstring(tok2);
> -
> - if (!key || !val) {
> - puts("out of memory");
> - free((void *) key);
> - free(val);
> - }
> -
> - if (!dict_alloc_insert(d, key, val)) {
> - puts("dict_alloc_insert failed");
> - free((void *) key);
> - free(val);
> - break;
> - }
> - break;
> - case 'd':
> - if (tokenize(in+1, &tok1, (char **) 0) != 1) {
> - puts("what?");
> - break;
> - }
> - dn = dict_lookup(d, tok1);
> - if (!dn) {
> - puts("dict_lookup failed");
> - break;
> - }
> - val = dnode_get(dn);
> - key = dnode_getkey(dn);
> - dict_delete_free(d, dn);
> -
> - free(val);
> - free((void *) key);
> - break;
> - case 'f':
> - dict_free(d);
> - break;
> - case 'l':
> - case '(':
> - case ')':
> - if (tokenize(in+1, &tok1, (char **) 0) != 1) {
> - puts("what?");
> - break;
> - }
> - dn = 0;
> - switch (in[0]) {
> - case 'l':
> - dn = dict_lookup(d, tok1);
> - break;
> - case '(':
> - dn = dict_lower_bound(d, tok1);
> - break;
> - case ')':
> - dn = dict_upper_bound(d, tok1);
> - break;
> - }
> - if (!dn) {
> - puts("lookup failed");
> - break;
> - }
> - val = dnode_get(dn);
> - puts(val);
> - break;
> - case 'm':
> - construct(d);
> - break;
> - case 'k':
> - dict_allow_dupes(d);
> - break;
> - case 'c':
> - printf("%lu\n", (unsigned long) dict_count(d));
> - break;
> - case 't':
> - for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
> - printf("%s\t%s\n", (char *) dnode_getkey(dn),
> - (char *) dnode_get(dn));
> - }
> - break;
> - case 'q':
> - exit(0);
> - break;
> - case '\0':
> - break;
> - case 'p':
> - prompt = 1;
> - break;
> - case 's':
> - dict_set_allocator(d, new_node, del_node, NULL);
> - break;
> - case '#':
> - if (tokenize(in+1, &tok1, (char **) 0) != 1) {
> - puts("what?");
> - break;
> - } else {
> - int dictnum = atoi(tok1);
> - if (dictnum < 0 || dictnum > 9) {
> - puts("invalid number");
> - break;
> - }
> - d = &darray[dictnum];
> - }
> - break;
> - case 'j':
> - if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
> - puts("what?");
> - break;
> - } else {
> - int dict1 = atoi(tok1), dict2 = atoi(tok2);
> - if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) {
> - puts("invalid number");
> - break;
> - }
> - dict_merge(&darray[dict1], &darray[dict2]);
> - }
> - break;
> - default:
> - putchar('?');
> - putchar('\n');
> - break;
> - }
> - }
> -
> - return 0;
> -}
> -
> -#endif
--
http://fam-tille.de
Reply to: