-
Notifications
You must be signed in to change notification settings - Fork 2
/
webpage.cpp
109 lines (102 loc) · 2.14 KB
/
webpage.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//Homework 1
//Name: Parth Patel
//CPSC 2120
//09/21/2015
#include <iostream>
#include <string.h>
#include <assert.h>
#include "webpage.h"
using namespace std;
/* Return a hash for the string s in the range 0..table_size-1 */
int hash(string s, int table_size)
{
unsigned int i, h = 0;
for (i=0; i<s.length(); i++)
h = (h * 2917 + (unsigned int)s[i]) % table_size;
return h;
}
/* Allocate a table of pointers to Page structs */
Page **allocate_table(int size)
{
Page **table = new Page *[size];
for (int i=0; i<size; i++)
table[i] = NULL;
return table;
}
webPage::webPage(int tablesize)
{
size=tablesize;
table = allocate_table(size);
num_elements=0;
}
webPage::~webPage()
{
for (int i=0; i<size; i++) {
while (table[i] != NULL) {
Page *temp = table[i];
table[i] = table[i]->next;
delete temp;
}
}
delete[] table;
}
int webPage::find(string key)
{
int h = hash(key, size);
Page *n = table[h];
while (n != NULL) {
if (n->name == key) return(h);
h++;
if(h==size){
h=0;
}
n = table[h];
}
return -1;
}
// checks how full the hash table is, allocating a new table and rehashing if necessary
// (only used for the words hash table)
void webPage::checksize()
{
num_elements++;
if (num_elements == 0.5*size) {
Page **newtable = allocate_table(size*2);
int i;
Page *newwrd;
for(i=0;i<size;i++)
{
if(table[i]!=NULL)
{
int h = hash(table[i]->name,size*2);
while(newtable[h]!=NULL)
{
h++;
if(h==size*2)
{
h=0;
}
}
newwrd = new Page(table[i]->name,NULL);
newtable[h]=newwrd;
table[i]=table[i]->next;
while(table[i]!=NULL)
{
Page *newpage = new Page(table[i]->name,NULL);
newwrd->next=newpage;
newwrd=newpage;
table[i]=table[i]->next;
}
}
}
for (int i=0; i<size; i++) {
while (table[i] != NULL) {
Page *deleter = table[i];
table[i] = table[i]->next;
delete deleter;
}
}
delete[] table;
size=size*2;
table=newtable;
}
}