Skip to content

Instantly share code, notes, and snippets.

@beoliver
Last active November 7, 2015 01:07
Show Gist options
  • Save beoliver/963ae6ac7248c89a4860 to your computer and use it in GitHub Desktop.
Save beoliver/963ae6ac7248c89a4860 to your computer and use it in GitHub Desktop.
basic trie
//
// tries.c
// chitchat
//
// Created by Ben Oliver on 06/11/15.
// Copyright © 2015 Ben Oliver. All rights reserved.
//
// assume that we allow 8 char sequences from an alphabet of 26 characters
// there are 26 ^ 8 possible sequences 208,827,064,576
// if a trie had 208,827,064,576 entries
// the worst case lookup would be (26 * 8) + 1 = 209
// average case (13 * 8) + 1 = 105
// best case 8 + 1 = 9
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "tries.h"
typedef struct ascii_trie_s {
char key;
int val;
unsigned short weight;
struct ascii_trie_s* child;
struct ascii_trie_s* next;
} ascii_trie ;
void free_ascii_trie(ascii_trie* node) {
if (node != NULL) {
free_ascii_trie(node->next);
free_ascii_trie(node->child);
free(node);
}
}
void print_weights(ascii_trie* node) {
if (node != NULL) {
printf("node: %c weight: %d\n", node->key, node->weight);
print_weights(node->next);
print_weights(node->child);
}
}
static ascii_trie* unsafe_trie_insert(char* key, int val, ascii_trie* node) {
// element must not allready exist in trie
while (1) {
// move right untill we find a match OR reach the end of the row
while ((*key != node->key) && (node->next != NULL)) {
node = node->next;
}
if (*key == node->key) {
node->weight += 1 ;
node = node->child ;
key = key+1 ;
} else {
node->next = malloc(sizeof(ascii_trie));
node = node->next;
node->weight = 1;
node->key = *key;
node->next = NULL;
node->child = NULL;
while (*key != '\0') {
key = key+1;
node->child = malloc(sizeof(ascii_trie));
node = node->child;
node->weight = 1;
node->key = *key;
node->next = NULL;
node->child = NULL;
}
node->weight = 0;
node->val = val;
return node;
}
}
}
static void unsafe_trie_delete(char* key, ascii_trie* node, ascii_trie* parent) {
ascii_trie* prev = NULL;
while ((node->key != *key) && (node->next != NULL)) {
prev = node;
node = node->next;
}
// we have now found the node that we need to use
if (node->weight < 2) {
if (prev == NULL) {
assert(parent != NULL);
parent->child = node->next;
} else {
prev->next = node->next;
}
// only one string uses this node
// thus only one string uses the children of the node
// use < 2 as we might allready be at the terminal node
// which has weight 0
// remember that we might not be at the end of a row
// so we use prev->next to join the previous node with node->next
// which is either a node or NULL
free_ascii_trie(node->child);
free(node);
} else {
// node weight is > 1
node->weight--;
unsafe_trie_delete(key+1, node->child, node);
}
}
ascii_trie* ascii_trie_lookup(char* key, int* valp, ascii_trie* node) {
while (1) {
while ((*key != node->key) && (node->next != NULL)) {
node = node->next;
}
if (*key != node->key) {
return NULL;
}
if (*key == 0x00) {
*valp = node->val;
return node;
}
key = key+1;
node = node->child;
}
}
int main(int argc, char** argv) {
printf("%lu\n", sizeof(ascii_trie));
ascii_trie* root = malloc(sizeof(ascii_trie));
root->weight = 0;
root->key = 0x00;
root->child = NULL;
root->next = NULL;
char* ben = "ben";
char* benjamin = "benjamin";
char* cat = "cat";
char* dog = "dog";
unsafe_trie_insert(ben, 10, root);
unsafe_trie_insert(benjamin, 20, root);
unsafe_trie_insert(cat, 30, root);
unsafe_trie_insert(dog, 40, root);
print_weights(root);
int val;
if (ascii_trie_lookup(ben, &val, root) != NULL) {
printf("%s exists with key: %d\n", ben, val);
} else {
printf("%s does not exist\n", ben);
}
printf("deleting: %s\n", ben);
unsafe_trie_delete(ben, root, NULL);
if (ascii_trie_lookup(ben, &val, root) != NULL) {
printf("%s exists with key: %d\n", ben, val);
} else {
printf("%s does not exist\n", ben);
}
print_weights(root);
free_ascii_trie(root);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment