Web Browser History - DLL, C++ (gcc)

Web Browser History - DLL

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

#define MAX 20005
#define ull unsigned long long int
struct node{
	string name;
	node *prev, *next;
};

struct HashNode{
	node *n;
	HashNode *next;

};
node nodePool[MAX];
int nodeCount;
HashNode hashNodePool[MAX];
int hashNodeCount;

node *getNewNode(string name)
{
	node *newNode = &nodePool[nodeCount++];
	newNode->name = name;
	newNode->prev = newNode->next = NULL;
	return newNode;
}

class Hash{
public:
	HashNode *hashTable[MAX];
	Hash(){
		hashNodeCount = 0;
		for(int i=0;i<MAX;i++)
			hashTable[i] = NULL;
	}

HashNode *getNewHashNode(node *newNode)
	{
		HashNode *newHashNode = &hashNodePool[hashNodeCount++];
		newHashNode->n = newNode;
		newHashNode->next = NULL;
		return newHashNode;
	}
	ull calHash(string key)
	{
		ull hash = 5381;
		int i = 0;
		for(int i=0;i<key.length();i++)
			hash = (hash << 5) + key[i];
		
		return hash % MAX;
	}
	void insert(node *newNode)
	{
		if( contains(newNode->name)!=NULL )
			return;
		int hashVal = calHash(newNode->name);
		HashNode *newHashNode = getNewHashNode(newNode);

newHashNode->next = hashTable[hashVal];
		hashTable[hashVal] = newHashNode;

}
	node *contains(string key)
	{
		int hashVal = calHash(key);
		HashNode *cur = hashTable[hashVal];
		while(cur!=NULL)
		{
			if( cur->n->name == key )
				return cur->n;
			cur = cur->next;
		}
		return NULL;
	}
	void remove(string key)
	{
		int hashVal = calHash(key);
		
		if( hashTable[hashVal] && hashTable[hashVal]->n->name == key )
		{
			hashTable[hashVal] = hashTable[hashVal]->next;
			return;
		}
		HashNode *cur = hashTable[hashVal], *prev = NULL;
		while(cur &&  cur->n->name != key )
		{
			prev = cur;
			cur = cur->next;
		}
		if(cur==NULL)
			return;
		
		prev->next = cur->next;

}

};

node *history;
Hash myHash;

node *removeLinks(node *cur)
{
	if(cur == NULL)
		return NULL;

// delete from history DLL
	if(history && history->name == cur->name)
	{
		history = history->next;
		if(history)
			history->prev = NULL;
	}
	if(cur->next)
		cur->next->prev = cur->prev;
	if(cur->prev)
		cur->prev->next = cur->next;

cur->prev = cur->next = NULL;
	return cur;
}
// ================================================================
void init(){
	nodeCount = 0;
	myHash = Hash();
	history = NULL;
}

void access(string link){

node *cur = myHash.contains(link);
	if(cur == NULL)
		return;
	
	// remove links
	node *dNode = removeLinks(cur);

if(history == NULL)
		history = dNode;
	else
	{
		// now add to front
		dNode->next = history;
		history->prev = dNode;
		history = dNode;
	}
	
	return;

}

void visit(string link){
	if(myHash.contains(link)!=NULL)
	{
		access(link);
		return;
	}

// new node will be added at front
	node *newNode = getNewNode(link);
	
	if(history == NULL)
		history = newNode;
	else
	{
		// insert at front
		newNode->next = history;
		history->prev = newNode;
		history = newNode;
	}
	
	
	myHash.insert(newNode);
}

void deleteLink(string link){
	node *cur = myHash.contains(link);
	if(cur==NULL)
		return;
	
	node *dNode = removeLinks(cur);
	
	// delete from hash
	myHash.remove(link);
}

vector<string> last5(){
	vector<string> ans;
	// get the recent 5 fron histroy LL
	node *cur = history;
	while(cur)
	{
		ans.push_back(cur->name);
		if(ans.size() == 5)
			break;
		cur = cur->next;
	}
	return ans;
}


run \| edit \| history \| help	0