simple suffix base and add only patricia trie

list.h

#ifndef __LIST_H
#define __LIST_H

#define offset_of(type,member) ((size_t)&(((type*)0)->member))

//#define LIST_POISON1	0xdeaddead
//#define LIST_POISON2	0xbedeadbe
#define LIST_POISON1	0
#define LIST_POISON2	0

#define container_of(pointer,type,member)\
(type*)((char*)(pointer) - offset_of(type,member))

struct list_head {
        struct list_head *prev,*next;
};

static inline void INIT_LIST_HEAD(struct list_head *list)
{
        list->next = list;
        list->prev = list;
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}
static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
        __list_add(new, head->prev, head);
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
        next->prev = prev;
        prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
}

static inline void list_move(struct list_head *list, struct list_head *head)
{
        __list_del(list->prev, list->next);
        list_add(list, head);
}

static inline void list_move_tail(struct list_head *list,
                                  struct list_head *head)
{
        __list_del(list->prev, list->next);
        list_add_tail(list, head);
}

static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}

static inline void list_del_init(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
        INIT_LIST_HEAD(entry);
}

#define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)

#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

#endif /*__LIST_H*/

ssap_trie.c

/* simple suffix base and add only patricia trie */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#include "list.h"

struct ssap_trie {
	struct list_head next;
	struct list_head sibling;

	char ch;
	void * data;
};

struct ssap_trie *
ssap_trie_new (char ch) {

	struct ssap_trie * trie;

	trie = (struct ssap_trie *) malloc (sizeof (struct ssap_trie));
	memset (trie, 0, sizeof (struct ssap_trie));
	INIT_LIST_HEAD (&trie->next);
	INIT_LIST_HEAD (&trie->sibling);
	trie->ch = ch;

	return trie;
}


int
ssap_trie_search (struct ssap_trie * root, char * word)
{
	int n;
	struct ssap_trie * trie;
	struct list_head * tmp_head, * cur, * next;

	tmp_head = &root->next;
	
	for (n = strlen (word); n >= 0; n--) {

		if (tmp_head != &root->next && list_empty (tmp_head)) {
			/* longest matched! */
			return 1;
		}

		list_for_each_safe (cur, next, tmp_head) {
			trie = list_entry (cur, struct ssap_trie, sibling);

			if (trie->ch == word[n]) {
				/* match! next character! */
				tmp_head = &trie->next;
				goto next_depth;
			}

		}

		/* there is no next character leaf. not found!  */
		return 0;

	next_depth:;
	}

	if (n < 0 && list_empty (tmp_head)) {
		/* perfect match. query = match name !! */
		return 1;
	}

	return 0;
}

int
ssap_trie_walk (struct ssap_trie * root, void (*func)(void *))
{
	struct ssap_trie * trie;
	struct list_head * tmp_head, * cur, * next;

	tmp_head = &root->next;

	if (root->data) {
		func (root->data);
	}

	list_for_each_safe (cur, next, tmp_head) {
		trie = list_entry (cur, struct ssap_trie, sibling);
		ssap_trie_walk (trie, func);
	}

	return 0;
}

int
ssap_trie_add (struct ssap_trie * root, char * word, void * data)
{
	int n;
	struct ssap_trie * trie, * parent;
	struct list_head * tmp_head, * cur, * next;

	parent = root;
	tmp_head = &root->next;
	
	for (n = strlen (word); n >= 0; n--) {

		list_for_each_safe (cur, next, tmp_head) {
			trie = list_entry (cur, struct ssap_trie, sibling);

			if (trie->ch == word[n]) {
				/* match! next character! */
				goto next_depth;
			}
		}

		/* there is no next character. add new node! */
		trie = ssap_trie_new (word[n]);
		if (n == 0) {
			/* edge leaf. add data. */
			trie->data = data;
		}
		list_add_tail (&trie->sibling, &parent->next);

	next_depth:
		tmp_head = &trie->next;
		parent = trie;
	}

	return 1;
}


void
walk (void * data)
{
	char * word = data;
	printf ("%s\n", word);
}

int
main (int argc, char ** argv)
{
	int n, m = 5;
	char * examples[] = { "hoge", "huga", "asdf", "a.net", "b.net" };
	struct ssap_trie * trie;

	trie = ssap_trie_new ('X');

	for (n = 0; n < m; n++) {
		ssap_trie_add (trie, examples[n], examples[n]);
	}

	for (n = 0; n < m; n++) {
		if (ssap_trie_search (trie, examples[n])) {
			printf ("%s present!\n", examples[n]);
		} else {
			printf ("%s does not present!\n", examples[n]);
		}
	}

	printf ("\n");

	char * target = "hoge.huga";
	if (ssap_trie_search (trie, target)) {
		printf ("%s present!\n", target);
	} else {
		printf ("%s does not present!\n", target);
	}

	printf ("walk!\n");
	ssap_trie_walk (trie, walk);
	
	return 0;
}