dict.c

一些常用的数据结构库

}

int dnode_is_in_a_dict(dnode_t *dnode)
{
    return (dnode->parent && dnode->left && dnode->right);
}

void dict_process(dict_t *dict, void *context, dnode_process_t function)
{
    dnode_t *node = dict_first(dict), *next;

    while (node != NULL) {
	/* check for callback function deleting	*/
	/* the next node from under us		*/
	assert (dict_contains(dict, node));
	next = dict_next(dict, node);
	function(dict, node, context);
	node = next;
    }
}

static void load_begin_internal(dict_load_t *load, dict_t *dict)
{
    load->dictptr = dict;
    load->nilnode.left = &load->nilnode;
    load->nilnode.right = &load->nilnode;
}

void dict_load_begin(dict_load_t *load, dict_t *dict)
{
    assert (dict_isempty(dict));
    load_begin_internal(load, dict);
}

void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
{
    dict_t *dict = load->dictptr;
    dnode_t *nil = &load->nilnode;
   
    assert (!dnode_is_in_a_dict(newnode));
    assert (dict->nodecount < dict->maxcount);

    #ifndef NDEBUG
    if (dict->nodecount > 0) {
	if (dict->dupes)
	    assert (dict->compare(nil->left->key, key) <= 0);
	else
	    assert (dict->compare(nil->left->key, key) < 0);
    }
    #endif

    newnode->key = key;
    nil->right->left = newnode;
    nil->right = newnode;
    newnode->left = nil;
    dict->nodecount++;
}

void dict_load_end(dict_load_t *load)
{
    dict_t *dict = load->dictptr;
    dnode_t *tree[DICT_DEPTH_MAX] = { 0 };
    dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
    dnode_t *complete = 0;
    dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
    dictcount_t botrowcount;
    unsigned baselevel = 0, level = 0, i;

    assert (dnode_red == 0 && dnode_black == 1);

    while (fullcount >= nodecount && fullcount)
	fullcount >>= 1;

    botrowcount = nodecount - fullcount;

    for (curr = loadnil->left; curr != loadnil; curr = next) {
	next = curr->left;

	if (complete == NULL && botrowcount-- == 0) {
	    assert (baselevel == 0);
	    assert (level == 0);
	    baselevel = level = 1;
	    complete = tree[0];

	    if (complete != 0) {
		tree[0] = 0;
		complete->right = dictnil;
		while (tree[level] != 0) {
		    tree[level]->right = complete;
		    complete->parent = tree[level];
		    complete = tree[level];
		    tree[level++] = 0;
		}
	    }
	}

	if (complete == NULL) {
	    curr->left = dictnil;
	    curr->right = dictnil;
	    curr->color = level % 2;
	    complete = curr;

	    assert (level == baselevel);
	    while (tree[level] != 0) {
		tree[level]->right = complete;
		complete->parent = tree[level];
		complete = tree[level];
		tree[level++] = 0;
	    }
	} else {
	    curr->left = complete;
	    curr->color = (level + 1) % 2;
	    complete->parent = curr;
	    tree[level] = curr;
	    complete = 0;
	    level = baselevel;
	}
    }

    if (complete == NULL)
	complete = dictnil;

    for (i = 0; i < DICT_DEPTH_MAX; i++) {
	if (tree[i] != 0) {
	    tree[i]->right = complete;
	    complete->parent = tree[i];
	    complete = tree[i];
	}
    }

    dictnil->color = dnode_black;
    dictnil->right = dictnil;
    complete->parent = dictnil;
    complete->color = dnode_black;
    dict_root(dict) = complete;

    assert (dict_verify(dict));
}

void dict_merge(dict_t *dest, dict_t *source)
{
    dict_load_t load;
    dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);

    assert (dict_similar(dest, source));	

    if (source == dest)
	return;

    dest->nodecount = 0;
    load_begin_internal(&load, dest);

    for (;;) {
	if (leftnode != NULL && rightnode != NULL) {
	    if (dest->compare(leftnode->key, rightnode->key) < 0)
		goto copyleft;
	    else
		goto copyright;
	} else if (leftnode != NULL) {
	    goto copyleft;
	} else if (rightnode != NULL) {
	    goto copyright;
	} else {
	    assert (leftnode == NULL && rightnode == NULL);
	    break;
	}

    copyleft:
	{
	    dnode_t *next = dict_next(dest, leftnode);
	    #ifndef NDEBUG
	    leftnode->left = NULL;	/* suppress assertion in dict_load_next */
	    #endif
	    dict_load_next(&load, leftnode, leftnode->key);
	    leftnode = next;
	    continue;
	}
	
    copyright:
	{
	    dnode_t *next = dict_next(source, rightnode);
	    #ifndef NDEBUG
	    rightnode->left = NULL;
	    #endif
	    dict_load_next(&load, rightnode, rightnode->key);
	    rightnode = next;
	    continue;
	}
    }

    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