forked from sysprog21/phonebook
-
Notifications
You must be signed in to change notification settings - Fork 0
/
phonebook_opt.c
89 lines (75 loc) · 1.83 KB
/
phonebook_opt.c
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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "phonebook_opt.h"
/* TODO: FILL YOUR OWN IMPLEMENTATION HERE! */
entry *findNameHash(char lastName[], nameEntry **hashTable)
{
size_t key = djb2(lastName);
nameEntry *pHead = hashTable[key];
while(pHead != NULL) {
if(!strcasecmp(lastName,pHead->pBook->lastName)) {
return pHead->pBook;
}
pHead = pHead->pNext;
}
return NULL;
}
void appendHash(char lastName[], nameEntry **hashTable, memPool *mp)
{
unsigned int key = djb2(lastName);
nameEntry *ne = (nameEntry *)pool_alloc(mp, sizeof(nameEntry));
entry *e = (entry *)pool_alloc(mp, sizeof(entry));
strcpy(e->lastName, lastName);
ne->pBook = e;
ne->pNext = hashTable[key];
hashTable[key] = ne;
return;
}
unsigned int djb2(char *str)
{
unsigned int hash = TABLE_SIZE;
unsigned int c;
while(c = *str) {
hash = ((hash << 5) + hash) + c;
++str;
}
return hash % TABLE_SIZE;
}
nameEntry **InitHashTable()
{
unsigned int table_size = TABLE_SIZE;
nameEntry **pt = malloc(table_size * sizeof(nameEntry *));
for(int i=0; i<table_size; ++i) {
pt[i] = NULL;
}
return pt;
}
entry *append(char lastName[], entry *e)
{
/* allocate memory for the new entry and put lastName */
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
void pool_init(memPool *mp, unsigned size)
{
size = size + (8 - size % 8);
mp->next = mp->head = malloc(size);
mp->size = size;
}
void *pool_alloc(memPool *mp, unsigned size)
{
if(size > mp->size) return NULL;
mp->size -= size;
void *tmp = mp->next;
mp->next += size;
return tmp;
}
void pool_free(memPool *mp)
{
free(mp->head);
}