Skip to content

Instantly share code, notes, and snippets.

@raphaelrk
Last active October 22, 2015 16:51
Show Gist options
  • Save raphaelrk/af99b20de4e4531bfb44 to your computer and use it in GitHub Desktop.
Save raphaelrk/af99b20de4e4531bfb44 to your computer and use it in GitHub Desktop.
#define LETTERS_HASHED 4
// a word is short if it is <= LETTERS_HASHED letters long
struct ll_node
ll_node* next
char str[LENGTH]
ll_node* tofree;
ll_node hashtable[32 ** LETTERS_HASHED];
char* dict_string
arr to32[127] = {...} // maps a-z -> 1-26, ' -> 27
arr tolower[127] = {...} // maps A-Z -> a-z, a-z -> a-z, ' -> '
load(char* dictionary_filename):
dict_string = malloc(fstate(dict));
char* arr_ptr = dict_string;
mmap(dict) -> dict_string;
// create hashtable
// loop every \n-terminated word:
while(*arr_ptr):
int word = arr_ptr;
// hash is just base-32 of first 4/5 letters of word
calculate hash(word)
also calculates index of suffix
if word is short, hashtable[hashnum] = 1
int suffix = word + LETTERS_HASHED;
if(!hashtable[hashnum])
ll_node node = hashtable[hashnum];
char* sptr = &(node.str[0])
while(suffix != '\n')
sptr++ = suffix++
sptr = '\0'
else
ll_node* new_node = malloc(sizeof(ll_node));
ll_node* old_node = hashtable[hashnum]->next;
new_node->next = old_node;
new_node->str = suff_start;
hashtable[hashnum].next = new_node;
tofree.push(new_node)
dict_size++;
bool check(char* word):
calculate hash(word)
if word is short, return whether hashtable[hashnum] == 1
node = hashtable[hashnum]
while(node != NULL)
// if suffixes match, return true
char* word_suffix = word + LETTERS_HASHED
char* dict_suffix = node->str
if(*word_suffix == *dict_suffix)
while(*++word_suffix == *++dict_suffix);
if(*word_suffix == '\0' && *dict_suffix == '\n')
return true;
return false;
unload:
curr = tofree
while(curr)
next = curr->next
free(curr)
curr = next
size:
return dict_size
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment