ARM processor at a glance (from 100ft above!)

ARM cores are found in billions of electronic devices viz. Mobiles, TVs, Set top Boxes, cameras, portable gaming machines etc. This article lists the basic and advanced features of many versions of ARM cores and describes how an OS can use its features.

This article doesn't provide a comprehensive study. I'm planning to describe that in a number of subsequent articles.

ARM (Generic)

- 37 registers
- 30 general purpose +1 cpsr_user + 5 spsr(_irq, _fiq, _svc, _undef, _abort) + 1 pc
- States – ARM, Thumb, Jazzle
- 7 Cpu modes
o User
o SVC
o FIQ
o IRQ
o Undef
o Abort
o System

- 7 Exceptions
o Reset
o Data abort - to return SUBS pc, lr, #8 @execute stage
o FIQ @decode stage
o IRQ @decode stage
o Prefetch abort - to return SUBS pc, lr, #4 @decode stage
o SWI - to return MOVS pc, lr
o Undef



ARM7

- 3 stage pipeline
o Fetch, Decode, Execute
- Von Neumann architecture, Single Instrcution / Data bus only one is active at a time

ARM9

- 5 stage pipeline
o Fetch, decode, execute, memory, writeback
o Fetch – fetch instruction
o Decode – decode instr, read register
o Execute instruction – ALU, shift
o Memory –memory access
o Writeback – register write/ cache write
- Instr / data TCM interface support
- Harvard architecture. Separate instr/ data bus

S – Synthesizable
- Instruction / data cache can be configured


ARM10E

- 6 stage pipeline
o Fetch, issue, decode, execute, memory, write
o Fetch – instr fetch
o Issue – arm/ thumb ins decode
o Decode – register read
o Exec – ALU, shift
o Memory – mem access
o Write – reg write
- Static branch prediction at fetch stage
o Conditional backward is taken
- Fetch stage can fetch 2 instr from inst cache

ARM11 (ARMv6 architecture)

- 8 stage pipeline
o Predicted fetch1
o Predicted fetch2
o Decode
o issue
o ALU / MAC / Data Cache access
o Writeback

Cache
- Data copy a line at a time
- 4 / 64 way set associative cache
- PA tag RAM stores the PA for the cache line

MMU
- VA to PA translation
- TLB stores PA for a VA


OS – MMU

ARMv5 picture (virtually indexed virtually tagged Cache)

1 VA having 2 PA for 2 different processes

In context switch
- The TLB needs to be flushed
- The VA and data must be removed from cache

2 VA having 1 PA for 2 different processes (shared memory)

In context switch
- Different VA are present in cache, confusing effect
- Cache must be flushed

Hence process contex switch is slower than thread switch


ARMv6 picture (virtually indexed physically tagged Cache)

MMU splitted into 2 parts of address map
- TTBR0 and TTBR1
- 8-bit ASID used besides the TLB so TLB flushing is not required during a Context switch
- Page tables has “never execute” bit, that protects from buffer overrun attacks etc.

Symbian EKA2 uses this in multiple memory model
- One mapping for kernel (2GB)
- Remaing for user processes (2GB)
- ASID protects TLB flush during context switch(hence 256 max concurrent processes in Symbian is allowed)
- Physically tagged protects cache flush during context switch

reverse a list recursively and nonrecursively

reverse(h)
{

/*

* 1->2->p ...

* 2->1->p ...

*/

if(!h && !h->next)
return

t = h->next
h->next = NULL
while(t)
{
next = t->next
t->next = h
h = t
t = next
}
}



reverse(h)
{
/*
* 1->2->3->4
* 4->3, 1->2->3
* 4->3->2, 1->2
* 4->3->2->1
*/
if(!h && !h->next)
return

first = h
next = first->next

reverse(next)

first->next->next = first
fisrt->next = 0
h = next
}

remove a given node from a list

remove(h, a)
{
if(h == 0 || a== 0)
return ;

if(h == a)
{
a = a->next
delete h
h = a
return
}

t=h
while(t->next)
{
if(t->next == a)
{
k = t->next->next
delete t->next
t->next = k
return
}

t = t->next
}

}

construct mirror of a given binary tree

mirror(a)

if(!a)
return 0

mirror(a->left)
mirror(a->right)

swap(a->left, a->right)

check if a tree is a binary search tree (BST)

isBST(a)
{
if(!a)
return true

if( a->left && minVal(a->left) > a->num)
return false

if( a->right && maxVal(a->right) < a->num)
return false

if(!isBST(a->left) && !isBST(a->right))
return false

return true

}

serialize and deserialize a binary tree

serialize(a, list)
{
static int level = 0;
if(!a)
{
list[level++] = -1;
return
}

list[level++] = a->num;

serialize(a->left, list)
serialize(a->right, list)
}

deserialize(a, list)
{
static int level = 0;

if(list[level] == -1)
{
level++
return 0
}

a = createNode()
a->num = list[level++]
a->left = deserialize(a, list)
a->right = deserialize(a, list)
}

reverse a binary tree such that the child's left points to parent

reverse(a)
{
if(!a)
return 0

if(!a->left && !a->right)
return a

l = reverse(a->left)
if(l)
l->left = a

r = reverse(a->right)
if(r)

r->left = a;

return a
}

print all root to leaf path of a binary tree

printpath(a)
{
int path[MaxLength]
printpathrec(a, path, 0)
}

printpathrec(a, path, pathlen)
{
if(!a)
{
for i 1 to pathlen
print path[i]
}

path[pathlen] = a->num

printpathrec(a->left, path, pathlen+1)
printpathrec(a->right, path, pathlen+1)
}

count unique binary trees those can be formed from n numbers

counttrees(n)
if(n <= 1)
return 1

sum = 0

for i 1 to n
{
l = counttrees(i-1)
r = counttrees(n-i)
sum += l + r
}
return sum

find least common ancestor of a binary tree

lca(a, p, q)

if(!a)
return 0

if(a == p || a == q)
return a

l = lca(a->left, p, q)
r = lca(a->right, p, q)

if(l && r)
return a

if(l)
return l

if(r)
return r

return 0

find the maximum depth of a binary tree

maxdepth(a)
if(!a)
return 0

return 1 + max(maxdepth(a->left), maxdepth(a->right)

find the size of a tree

size(a)
if(!a)
return 0

return 1+size(a->left)+size(a->right)

remove duplicate characters from a sorted string

void removeDup(int a[], int& len)
{
int j=1;
for(int i=0, k=1; i< len && k< len; i++, k++)
{
//cout << a[i] << " " ;
if(a[i] != a[k])
{
a[j] = a[k];
j++;
}
}

len =j;
}

print a matrix in spiral order

void printSpiral(int a[][10], int rows, int columns)
{
int count = rows * columns;

int columnMax = columns-1;
int columnMin = 0;
int rowMax = rows - 1;
int rowMin = 0;

while(count)
{
for(int i=columnMin; i<=columnMax; i++, count--)
cout << a[rowMin][i] << "->";

rowMin++;

for(int i=rowMin; i<=rowMax; i++, count--)
cout << a[i][columnMax] << "|";

columnMax--;

for(int i=columnMax; i>=columnMin; i--, count--)
cout << a[rowMax][i] << "<-";

rowMax--;

for(int i=rowMax; i>=rowMin; i--, count--)
cout << a[i][columnMin] << "^";

columnMin++;

}
}

create a binary search tree and add a node, traverse inoder, breadth first search, find fourth smallest

const int MaxN = 50;

class node;

class queue
{
public:
queue() {begin = end = -1;}
void enque(node* n)
{
if(empty())
begin = 0;
elem[++end] = n;
}

node* deque()
{
node* t;
if(begin == -1)
return 0;

if(begin == end)
{
t=elem[begin];
begin = end = -1;
}
else
t=elem[begin++];
return t;
}

int empty() { return (begin == -1)? 1: 0;}

private:
node* elem[MaxN];
int begin;
int end;
};

class node
{
public:
int n;
node* l;
node* r;
};

class bst
{
public:
bst() {r= NULL;}
void addnode(int n);
void traverseinorder() {traverseinorder(r);}
void bfs() {bfs(r); }
void fourthsmallest() {fourthsmallest(r);}
private:
void addnode(node* p, int n);
void traverseinorder(node* r);
void bfs(node* r);
void fourthsmallest(node* p);
node* r; //root
};

void bst::addnode(int n)
{
if(!r)
{
r = new node();
r->n = n;
r->l = NULL;
r->r = NULL;
return;
}
addnode(r, n);
}

void bst::addnode(node* p, int n)
{
if(n < p->n)
{
if(p->l)
addnode(p->l, n);
else
{
p->l = new node();
p->l->n = n;
p->l->l = NULL;
p->l->r = NULL;
return;
}
}
else
{
if(p->r)
addnode(p->r, n);
else
{
p->r = new node();
p->r->n = n;
p->r->l = NULL;
p->r->r = NULL;
return;
}
}
}

void bst::traverseinorder(node* p)
{
if(!p)
return;
traverseinorder(p->l);
cout << p->n << " ";
traverseinorder(p->r);
}

void bst::fourthsmallest(node* p)
{
static int count=0;
if(!p)
return;
fourthsmallest(p->l);
count++;
if(count == 4)
cout << "4th smallest = " << p->n < fourthsmallest(p->r);

}

void bst::bfs(node* p)
{
if(!p)
return;

queue t;
t.enque(p);

node dummy;
dummy.n = -1;

cout << "\n\n breadth first traverse\n";
t.enque(&dummy);

while(!t.empty())
{
node* k = t.deque();
while(k && k->n == -1)
{
cout << endl;
k = t.deque();
}

cout << k->n << " ";
if(k->l)
t.enque(k->l);
if(k->r)
t.enque(k->r);

t.enque(&dummy);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
bst tr;
cout << "enter numbers to create a BST (-1 as end of input)\n";
while(1)
{
int n;
cin >> n;
if(n < 0)
break;
tr.addnode(n);
}

cout << "inorder: ";
tr.traverseinorder();

tr.bfs();

tr.fourthsmallest();
return 0;
}

reverse a linked list

/*
* A NDROID -> NA DROID -> DNA ROID -> RDNA OID -> ORDNA ID -> IORDNA D -> DIORDNA
* temp = head2->next // D
* head2->next = temp->next // A->ROID
* temp->next = head1 // D->NAROID
* head1 = temp; //(DNA)ROID
*/
List* rev_list(List* head)
{
List* head1 = head;
List* head2 = head;

List* temp;
while(head2->next)
{
temp = head2->next;
head2->next = temp->next;
temp->next = head1;
head1 = temp;
//print_list(head1);
}

return head1;
}

find maximum sum of a sub arrary

void maxsumsubarray(int a[], int n)
{
int sum=0;
int maxsofar = 0;
int start =0;
int end=0;
int count =0;
for(int i=0;i< n;i++)
{
if(maxsofar + a[i] > 0)
{
maxsofar += a[i];
count++;
}
else
{
maxsofar = 0;
count =0;
}

if(sum < maxsofar)
{
sum = maxsofar;
end = i;
start = end - count + 1;
}
}
cout << "maxsum = " << sum ;
cout << " start = a[" << start << "] = " << a[start] << " end = a[" << end << "] = " << a[end] << endl;
}

sort an array using heapsort

void max_heapify(int* u, int i, int size)
{
//push down the ith element in the max tree
int l = 2*i+1;
int r = 2*i+2;
int largest =i;
if(l<=size && u[l]>u[largest])
largest = l;
else
largest = i;
if(r<=size && u[r]>u[largest])
largest = r;
if(i != largest)
{
//exchange i and largest and call recurse max_heapify
int t=u[i];
u[i] = u[largest];
u[largest] = t;
max_heapify(u, largest, size);
}
}

void build_max_heap(int* u, int size)
{
for(int i=size/2; i>=0; i--)
{
max_heapify(u, i, size);
}
}

void heap_sort(int* u, int size)
{
build_max_heap(u, size);

cout << "max heap: ";
print_arr(size);

int hsize = size;
for(int i=0; i< size; i++)
{
hsize--;
int t= u[0];
u[0] = u[hsize];
u[hsize] = t;
max_heapify(u, 0, hsize-1);
}
}

sort an array using mergesort

void merge_sort(int* u, int size)
{
if(size==1)
{
return;
}
//divide the array into 2
//sort each
merge_sort(u, size/2);
merge_sort(u+(size/2), size-(size/2));

int* t=(int*)malloc(sizeof(int)*(size));

for(int i=0,anext=0,bnext=0; i< size; i++)
{
if(anext==size/2)
{
t[i] = *(u+(size/2)+bnext);
bnext++;
}
else if(bnext == size-(size/2))
{
t[i] = *(u+anext);
anext++;
}
else
{
if(*(u+anext) < *(u+(size/2)+bnext))
{
t[i] = *(u+anext);
anext++;
}
else
{

t[i] = *(u+(size/2)+bnext);
bnext++;
}
}
}

//copy back to org array
for(int i=0;i< size;i++)
{
*(u+i) = *(t+i);
}


delete t;
}

find kth smallest element in an array

void kthsmallest(int k, int l, int u)
{
if(l>= u)
return;

//partition
int m=l;
for(int i=l+1; i<= u; i++)
{
if(arr[i] < arr[l])
{
//swap them
int t=arr[i];
arr[i]=arr[m+1];
arr[m+1]=t;
m++;
}
for(int j=0;j< 8;j++)
cout << " " << arr[j];
cout << " m= " << m << " i= " << i << endl;
}
//swap l, m
int t=arr[m];
arr[m]=arr[l];
arr[l]=t;

for(int i=0;i< 8;i++)
cout << " " << arr[i];
cout << " [" << arr[m] << "] is now correctly placed at position " << m ;
cout << endl;
/*
if(m==k)
cout << k << "th smallest element is " << arr[m] << endl;
*/
//recursively call qsort
if(k< m)
kthsmallest(k, l, m-1);
if(k> m)
kthsmallest(k, m+1, u);
}

//program end

sort an array using quicksort

#include <iostream>
using namespace std;

void mquicksort(int A[], int l, int u)
{
    if(l>=u)
        return;
        
    int m=l;
    
    for(int i=l+1; i<u; i++)
    {
        if(A[i] < A[l])
        {
            int t=A[i];
            A[i] = A[m+1];
            A[m+1]=t;
            m++;
        }
    }

    int t=A[l];
    A[l] = A[m];
    A[m]=t;

    mquicksort(A, l, m-1);
    mquicksort(A, m+1, u);
}

int main() {
    // your code goes here
    int A[20];
    int n;
    cout << "enter number of elements(<=20) to be sorted:";
    cin >> n;
    cout << "\nenter " << n << " elements now\n";
    for(int i=0;i<n;i++)
    {
        cin >> A[i];
    }
    mquicksort(A, 0, n);
    
    cout << "\n\nsorted numbers: ";
    for(int i=0;i<n;i++)
    {
        cout << A[i] << " ";
    }

    return 0;
}

Reverse the order of words in a sentence

int index[20] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

//output: word by word sentence this reverse
//order : O(n/2) + O(n) + O(w)*O(wlen/2)

//find indexes of words' start
void revsentence(char* src, int len)
{
for(int i=0; i< len/2; i++)
{
char temp = src[i];
src[i] = src[len-i-1];
src[len-i-1] = temp;
}

int j=1;
for(int i=0; i< len; i++)
{
if(src[i] == ' ')
index[j++] = i;

}
index[j++] = len; //last index = src:'\0'

//reverse the words

for(int i=0; i< j; i++)
{
int startindex = index[i] + 1;
int endindex = index[i+1]-1;
int wlen = endindex - startindex +1;
for(int k=0; k< wlen/2; k++)
{
char temp = src[startindex+k];
src[startindex+k] = src[endindex-k];
src[endindex-k] = temp;
}

}

}
int _tmain(int argc, _TCHAR* argv[])
{
char src[200];
cout << "enter a string to reverse word by word: " ;
cin.getline(src,200);
revsentence(src, strlen(src));

cout << "\noutput: " << src << endl;
return 0;
}

Generate k unique random numbers ranging from 1 to n

void genrandomnum(int k, int n)
{
cout << "algo1: ";
int arr[100];
for(int i=0;i < 100;i++)
arr[i] = 0;

int i=0;
while(i!=k)
{

int rnd = (rand()%n) + 1; //random num in 1,n
if(arr[rnd] == 0)
{
arr[rnd] = -1;
arr[i] = rnd;
i++;
}
else
{
if(arr[rnd] > 0)
{
arr[rnd] = -arr[rnd]; //mark
arr[i] = rnd;
i++;
}
}

}

for(int i=0;i < k;i++)
if(arr[i]<0)
arr[i]=-arr[i];

for(int i=0;i < k;i++)
cout << " " << arr[i];

cout << endl << endl;
}

//Knuth's Algo

void genrandomnum1(int k, int n)
{
cout << "algo2: " ;
for(int i=0; i < n; i++)
{
if((rand()%(n-i)) < k)
{
cout << i << " ";
k--;
}
}

cout << endl << endl;
}

move largest node to the end of a linked list

class list
{
public:
int n;
list* next;
};

void movelargesttoend(list*& p)
{
if(!p)
return;

if(!p->next)
return;

list* l = p;
list* cur = p;

list* prev = p;

while(cur->next)
{
if(l->n < cur->next->n)
{
l = cur->next;
prev = cur;
}
cur = cur->next;
}

//head is largest
if(l == p)
{
cur->next = p;
p = p->next;
cur->next->next = NULL;
}
else if(l != cur)
{
prev->next = l->next;
cur->next = l;
l->next = NULL;
}
}

insertion sort of a linked list

void insertionsort(list*& p)
{
cout << "sorting...\n"; list* res = NULL; while(p) { list* next = p->next;
sortedinsert(res, p);
p = next;
}

p = res;
}

insert a node in sorted order into a sorted linked list

void sortedinsert(list*& head, list* p)
{
//case for head node
if((!head) || (p->n < head->n))
{
p->next = head;
head = p;
return;
}

//intermediate case
list* cur = head->next;
list* prev = head;
while(cur)
{
if(p->n > cur->n)
{
prev= cur;
cur = cur->next;
}
else
break;
}

//tail case
if(!cur)
{
prev->next = p;
p->next = NULL;
}
else
{
p->next = cur;
prev->next = p;
}

}

Merge two sorted linked lists

class list
{
public:
int n;
list* next;
};

list* merge_sorted_lists(list* a, list* b)
{
list* t1;
list* t2;
list* head;
if(!a || !b)
return NULL;

// t1 points to the smallest number
if(a->n < b->n)
{
t1 = a;
t2 = b;

head = a;
}
else
{
t1=b;
t2=a;

head =b;
}

while(t1 && t2)
{
cout << t1 << " " << t2 << endl;
if(t1->next && (t1->next->n < t2->n))
{
t1 = t1->next; //move to next element in smaller list
}
else
{
list* t=t1->next;
list* k=t2->next;
t1->next = t2;
t2->next = t;
t2 = k;
t1 = t1->next;
}
}

return head;
}

find maximum length of space in given text

void maxlenofspaces(char a[])
{
int count = 0;
int maxcount = 0;
int start = 0;
for(int i=0; a[i] != '\0'; i++)
{
if(a[i] == ' ')
{
if(!count)
start = i;
count++;
if(count > maxcount)
maxcount = count;
}
else
{
start = i-count-1;
count = 0;
}

}

cout << "\nstart index=" << start << " max spaces length=" << maxcount << endl;
}

Delete a character set present in a given string

char* strdel(char* s1, int len1, char* s2, int len2)
{
int bitmapvec[8]; //bit[n] = 1 if s1[i] == n else 0
for(int i=0; i<8; i++)
bitmapvec[i] = 0;

for(int i=0; i {
bitmapvec[ (s1[i] / 32) ] |= (1 << (s1[i] % 32)) ;
}

int j=0;
for(int i=0; i< len2; i++)
{
if(!(bitmapvec[s2[i]/32] & (1 << (s2[i] % 32))))
{
s2[j] = s2[i];
j++;
}
}

s2[j] = '\0';

return s2;
}

Find Substring in a given String

int findsubstr(char* src, char* trg, int srclen, int trglen)
{
if((srclen < trglen) (srclen < 1) (trglen < 1) (!src) (!trg))
return -1;

for(int i=0; i < srclen-trglen+1; i++)
{
//now compare the src with trg
int j=0;
for(; j < trglen; j++)
{
if(src[i+j] != trg[j])
break; //not found, restart with next src character
}
if(j==trglen)
return i;
}

return -1;
}

An Implementation of Dictionary Using TRIE Data Stucture using C++

Recently I was asked this question in an interview and was asked to implement it in a short time. Unfortunately I couldn't do that and lost that opportunity. I took it as a challenge to myself and implemented it in C++. Have a look at it.

Comments and corrections are welcome.
Enjoy



// dictionary.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include
#include

using namespace std;

//TRIE data structure implementation
//every valid node contains a character and a pointer to other nodes
// e.g. root->a->p->p->l->e
class Edge;

class Word
{
public:
Word()
{
for(int i=0;i<26;i++) edge[i] = NULL;
}
~Word()
{
for(int i=0;i<26;i++)
{
if(edge[i])
delete edge[i];
}
}
string word;
string desc; //description

Edge* edge[26]; //the index corresponds to the character in alphabetic order
};

class Edge
{
public:
Edge() {word=NULL;}
~Edge() {if(word) delete word;}
Word* word;
};

class Dictionary
{
public:
Dictionary();
~Dictionary();
void AddWord(char* w, char* des);
void RemWord(char* w);
int Search(char* w);
void SearchWild(char* w);

private:
int TryRemWord(Word* wrd, char* w);
void TraverseAllEdges(Word* wrd);
Word* Root; //stores the pointer to Root Word

};

Dictionary::Dictionary()
{
Root = new Word();
}

Dictionary::~Dictionary()
{
delete Root;
}


/* adds a word w to the dicitionary with description des*/
void Dictionary::AddWord(char* w, char* des)
{
Word* node = Root;

for(int i=0; w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
//cout << "edge for " << w[i] << " found\n";
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '\0')
{
//add the word dscription here given that the tree node already exists for this word
node->word = w;
node->desc = des;
}
}
else
{
//cout << "edge for " << w[i] << " created\n";
node->edge[w[i]-'a'] = new Edge();
node = node->edge[w[i]-'a']->word = new Word();
node->word.assign(w, i+1);

//cout << "word " << node->word.c_str() << " stored\n";
if(w[i+1] == '\0')
{
node->desc = des;
//cout << "description for word " << w << " stored\n";
}
}
}

}

/* removed a word w from the dictionary*/
void Dictionary::RemWord(char* w)
{
TryRemWord(Root, w);

}

int Dictionary::TryRemWord(Word* wrd, char* w)
{
int ret = -1;
int istargetword = 0;

//Traverse to reach the word
if(*w != '\0')
{
if(wrd->edge[*w-'a'])
{
if(*(w+1) != '\0')
{
//word found, now try removing the word and its predecessors
ret = TryRemWord(wrd->edge[*w-'a']->word, w+1);
}
else
{
ret = 0;
istargetword = 1;
}
}
else
ret = -1;
}

if(ret == 0)
{
//check if the current node has edges
int i;
for(i=0;i<26;i++)
{
if(wrd->edge[*w-'a']->word->edge[i])
{
ret = -1;
break;
}
}
if(i==26)
{
//there is no edge to it, check if it is the target word to be deleted
if(istargetword)
{
cout << "removing " << wrd->edge[*w-'a']->word->word.c_str() << endl;
delete (wrd->edge[*w-'a']);
wrd->edge[*w-'a'] = NULL;
ret = 0;
}
else
{
//there is no edge to it, now check for any valid word description
if(wrd->edge[*w-'a']->word->desc.empty())
{
cout << "removing " << wrd->edge[*w-'a']->word->word.c_str() << endl;
delete (wrd->edge[*w-'a']);
wrd->edge[*w-'a'] = NULL;
ret = 0;
}
else
ret = -1; //can't delete it because it is a valid word
}
}
else
{
if(istargetword)
wrd->edge[*w-'a']->word->desc.clear(); //can't delete it because it is not leaf node, so just remove the description
}
}

return ret;
}

/* searches a word w from the dictionary and prints the description*/
int Dictionary::Search(char* w)
{
//traverse the tree and find the match
Word* node = Root;

for(int i=0; w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '\0' && !node->desc.empty())
{
cout << w << ": " << node->desc.c_str() << endl;
return 0;
}
}
else
break;
}
cout << "meaning of " << w << " not found!\n";
return -1;

}

/* searches all the words with starting string as "w" and prints them */
void Dictionary::SearchWild(char* w)
{
Word* node = Root;
for(int i=0; w[i] != '*' && w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '*')
{
TraverseAllEdges(node);
return;
}
}

}

}

/* traverses all the edges of a word recursively */
void Dictionary::TraverseAllEdges(Word* wrd)
{
if(!wrd->desc.empty())
cout << wrd->word.c_str() << endl;

for(int i=0;i<26;i++)
{
if(wrd->edge[i])
{
TraverseAllEdges(wrd->edge[i]->word);
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
Dictionary MDict;

MDict.AddWord("apple","it is a fruit");
MDict.AddWord("table","it is a furniture");
MDict.AddWord("earth","it is a planet");
MDict.AddWord("car","it is a vehicle");
MDict.AddWord("computer","it is an electronic device");
MDict.AddWord("ape","it is an animal");
MDict.AddWord("apex","the highest");

MDict.Search("apple");

MDict.SearchWild("c*");

MDict.RemWord("ape");

MDict.Search("apex");

MDict.AddWord("ape", "it is an animal");

MDict.Search("ape");

return 0;
}