In this blog we will learn how to use memory pool for trie data structure. If you do not know about trie data structure follow the link  http://wikistack.com/how-to-write-c-program-for-trie-data-structure/ .

memory pool means allocating required number of memory in advance. This makes a program faster.

how to use memory pool for trie data structure

Let us look at the data structure of trie for storing strings.

struct trie
{
   struct trie* children[26];
   int isEndOfString;
}

Each node of a trie points to 26 children.¬† To insert a string , for example if the string is “aabk” , we make a insert function as

struct trie *makeNode() {
    struct trie *p = (struct trie*) malloc(sizeof(struct trie));
    if (p) {
        p->isEndOfString = false;
        int i = 0;
        for (i; i < 26; i++) {
            p->children[i] = NULL;
        }
    }
    return p;
}

int getIndex(char ch) {
    return ch - 'a';
}

void insert(struct trie * root, char *str, int str_len) {
    struct trie *tmp = root;
    int i = 0;
    for (i; i < str_len; i++) {
        int index_of_char = getIndex(str[i]);
        if (tmp->children[index_of_char] == NULL) {
            tmp->children[index_of_char] = makeNode();
        }
        tmp = tmp->children[index_of_char];
    }
    // after traversing all char of str,mark
    // last trie node's flag isEndOfString true
    tmp->isEndOfString = true;
}

Calling make_node() function , to create new trie node each time , will take some cpu time. if we can allocate memory for trie node in advance , we can get faster program execution.

how to use memory pool for trie data structure

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

#define true 1
#define false 0

typedef struct trie
{
  int child[26];
  int isEndOfString;
} trie;

// memory pool for trie
trie t[1048576];
int gIndex = 0;			// memory tracker

int makeNode ()
{
  t[gIndex].isEndOfString = false;
  int i = 0;
  for (i; i < 26; i++)
    {
      t[gIndex].child[i] = 0;
    }
  gIndex++;
  return gIndex;
}

int getIndex (char ch)
{
  return ch - 'a';
}

void insert (char *str, int str_len)
{

  int i = 0;
  int rootIndex = 0;
  for (i; i < str_len; i++)
    {

      int index_of_char = getIndex (str[i]);

      if (t[rootIndex].child[index_of_char] == 0)
    {
      t[rootIndex].child[index_of_char] = makeNode ();
    }
      rootIndex = t[rootIndex].child[index_of_char];
    }
  // after traversing all char of str,mark
  // last trie node's flag isEndOfString true
  t[rootIndex].isEndOfString = true;
}

int search (char *str, int len)
{

  int i = 0;
  int rootIndex = 0;

  for (i; i < len; i++)
    {
      int index = getIndex (str[i]);

      if (!t[rootIndex].child[index])
    return false;

      rootIndex = t[rootIndex].child[index];
    }

  return (rootIndex && t[rootIndex].isEndOfString);
}

int main ()
{
  // root trie node
  makeNode ();
  char *str = "als";
  int len = strlen (str);
  insert (str, len);

  if (search (str, len))
    printf ("string is present in trie\n");
  else
    printf ("string is not present in trie\n");

  char *strr = "wiki";
  if (search (strr, len))
    printf ("string is present in trie\n");
  else
    printf ("string is not present in trie\n");

  return 0;
}

 

Ref:

https://stackoverflow.com/questions/30508183/what-are-the-usual-im-ple-men-ta-tion-de-tails-be-hind-mem-ory-pools



Related Contents to follow