On 03/18/2011 06:06 PM, Olivier Guilyardi wrote:
> Hi!
>
> On 03/11/2011 07:22 PM, David Robillard wrote:
>
>> On Fri, 2011-03-11 at 12:08 +0100, Olivier Guilyardi wrote:
>
>>> I will try and submit a patch to remove glib. It'll take some time because I
>>> have dozens of other things to do, but I will work on this. I had a quick
>>> look
>>> at sord, it seems it only needs glib's sequence and hash table. Is this
>>> correct,
>>> or will you need some more utilities?
>> Overall I need sequence, hash table (or hash table like thing, I'll
>> probably use a radix tree)
>
> Alright, attached is a minimal radix tree implementation. I just wrote it from
> scratch. Would that work for sord?
>
> If so, I'll try and benchmark it and do some more tests.
Attached is an updated version with a couple of fixes and optimizations.
--
Olivier
/*
* Copyright (c) 2011 Samalyse
* Author: Olivier Guilyardi
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice immediately at the beginning of the file, without modification,
* this list of conditions, and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "radix_tree.h"
typedef struct Node Node;
struct Node {
char *leaf;
Node *branches;
int nbranches;
void *data;
};
struct RadixTree {
Node root;
RadixTreeFreeData free_data;
};
RadixTree *
radix_tree_new(RadixTreeFreeData free_data) {
RadixTree *self = calloc(1, sizeof(*self));
self->free_data = free_data;
return self;
}
static void
destroy_branches(Node *node, RadixTreeFreeData free_data) {
Node *child, *end = node->branches + node->nbranches;
for (child = node->branches; child < end; child++) {
if (child->nbranches) {
destroy_branches(child, free_data);
}
free(child->leaf);
if (free_data)
free_data(child->data);
}
if (node->branches)
free(node->branches);
}
void
radix_tree_destroy(RadixTree *self) {
destroy_branches(&self->root, self->free_data);
free(self);
}
static Node *
lookup_node(const Node *node, const char *key, int *matched, int *split, Node **parent) {
int common, consumed = 0;
Node *child, *result = NULL, *end = node->branches + node->nbranches;
if (parent)
*parent = (Node *) node;
char *leaf, *k;
for (child = node->branches; child < end; child++) {
leaf = child->leaf;
if (*leaf == *key) {
// printf("%s\t%s\n", key, child->leaf);
k = (char *) key;
for (k++, leaf++, common = 1; *k && *k == *leaf; common++, k++, leaf++)
;
if (*leaf == '\0') {
key += common;
consumed = common;
*split = 0;
if (*key == '\0') {
result = child;
} else {
result = child->nbranches ? lookup_node(child, key, matched, split, parent) : NULL;
if (!result) {
result = child;
*split = common;
}
}
break;
} else if (common > consumed) {
result = child;
*split = common;
consumed = common;
}
}
}
*matched += consumed;
return result;
}
void *
radix_tree_lookup(const RadixTree *self, const char *key) {
int matched = 0, split = 0;
Node *node = lookup_node(&self->root, key, &matched, &split, NULL);
return node && split == 0 ? node->data : NULL;
}
static inline void
add_node(Node *parent, const char *leaf, const void *data, const Node *branches,
int nbranches) {
parent->branches = realloc(parent->branches,
(parent->nbranches + 1) * sizeof(*parent->branches));
Node *node = parent->branches + parent->nbranches++;
node->leaf = strdup(leaf);
node->data = (void *) data;
node->branches = (Node *) branches;
node->nbranches = nbranches;
}
static inline void
replace_node_data(Node * node, const void *data, RadixTreeFreeData free_data) {
if (node->data && free_data) {
free_data(node->data);
}
node->data = (void *) data;
}
void
radix_tree_insert(RadixTree *self, const char *key, const void *data) {
int matched = 0, split = 0;
Node *node = lookup_node(&self->root, key, &matched, &split, NULL);
if (!node) {
add_node(&self->root, key, data, NULL, 0);
} else if (split > 0) {
if (node->leaf[split] != '\0') {
Node oldnode = *node;
node->branches = NULL;
node->nbranches = 0;
add_node(node, node->leaf + split, node->data,
oldnode.branches, oldnode.nbranches);
node->leaf = realloc(node->leaf, split + 1);
node->leaf[split] = '\0';
node->data = NULL;
}
if (key[matched] == '\0') {
replace_node_data(node, data, self->free_data);
} else {
add_node(node, key + matched, data, NULL, 0);
}
} else {
replace_node_data(node, data, self->free_data);
}
}
void
radix_tree_remove(RadixTree *self, const char *key) {
int matched = 0, split = 0;
Node *parent;
Node *node = lookup_node(&self->root, key, &matched, &split, &parent);
if (node && split == 0) {
if (self->free_data)
self->free_data(node->data);
node->data = NULL;
if (!node->nbranches) {
free(node->leaf);
if (parent->nbranches == 1) {
free(parent->branches);
parent->branches = NULL;
parent->nbranches = 0;
} else {
*node = parent->branches[--parent->nbranches];
parent->branches = realloc(parent->branches,
parent->nbranches * sizeof(*parent->branches));
if (parent->nbranches == 1 && parent->leaf &&
(!parent->data || !parent->branches->data)) {
Node *single = parent->branches;
parent->leaf = realloc(parent->leaf,
strlen(parent->leaf) + strlen(single->leaf) + 1);
strcat(parent->leaf, single->leaf);
if (!parent->data) {
parent->data = single->data;
}
parent->branches = single->branches;
parent->nbranches = single->nbranches;
free(single);
}
}
}
}
}
static void
dump_branches(const Node *node, int string_data, int pad) {
Node *child, *end = node->branches + node->nbranches;
int i;
for (child = node->branches; child < end; child++) {
for (i = 0; i < pad; i++)
printf(" ");
printf("[%s] ", child->leaf);
if (string_data && child->data) {
printf("%s", (char *) child->data);
}
printf("\n");
dump_branches(child, string_data, pad + strlen(child->leaf));
}
}
void
radix_tree_dump(const RadixTree *self, int string_data) {
dump_branches(&self->root, string_data, 0);
}
/*
* Copyright (c) 2011 Samalyse
* Author: Olivier Guilyardi
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice immediately at the beginning of the file, without modification,
* this list of conditions, and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#ifndef RADIX_TREE_H
#define RADIX_TREE_H
#ifdef __cplusplus
extern "C" {
#endif
typedef struct RadixTree RadixTree;
typedef void (* RadixTreeFreeData) (void *data);
RadixTree * radix_tree_new(RadixTreeFreeData free_data);
void radix_tree_destroy(RadixTree *self);
void radix_tree_insert(RadixTree *self, const char *key, const void *data);
void radix_tree_remove(RadixTree *self, const char *key);
void * radix_tree_lookup(const RadixTree *self, const char *key);
void radix_tree_dump(const RadixTree *self, int string_data);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* RADIX_TREE_H */
_______________________________________________
Linux-audio-dev mailing list
[email protected]
http://lists.linuxaudio.org/listinfo/linux-audio-dev
