Re: [MoM] Re: kmer-tools
Hi, Andreas,
On الإثنين 11 أيار 2015 00:47, Andreas Tille wrote:
>>>So to be sure you can at least check the diff whether kmer
>>>upstream has patched the lib to some extend. If there is no diff you
>>>are done - if not it might be worth inspecting it more deeply.
>>>
>>
>>I will check. Like I said before, while grepping the source I found some
>>signs that this is likely the case.
>
>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.
Thanks and regards
Afif
--
Afif Elghraoui | عفيف الغراوي
http://afif.ghraoui.name
--- ../../../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
Reply to: