1 /***************************************************************************
2 hash.cpp - description
3 -------------------
4 begin : Thu Aug 17 2000
5 copyright : (C) 2000 by Waldemar Baraldi
6 email : baraldi@lacasilla.com.ar
7 ***************************************************************************/
8
9 /***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include "hash.h"
21 #include <stdio.h>
22
Bucket(Str * str,Object * obj)23 Hash::Bucket::Bucket(Str * str, Object * obj){
24 this->str=str;
25 this->obj=obj;
26 }
27
~Bucket()28 Hash::Bucket::~Bucket(){
29 delete str;
30 }
31
setStr(Str * str)32 void Hash::Bucket::setStr(Str * str){
33 if (this->str) delete this->str;
34 this->str=str;
35 }
36
setObject(Object * obj)37 void Hash::Bucket::setObject(Object * obj){
38 this->obj=obj;
39 }
40
getStr()41 Str * Hash::Bucket::getStr(){
42 return str;
43 }
44
getObject()45 Object * Hash::Bucket::getObject(){
46 return obj;
47 }
48
function(Str * str)49 int Hash::function(Str * str){
50 int i=0, sum=0;
51 const char * aux=str->get();
52
53 while (aux[i]!='\0') sum+=aux[i++];
54
55 return(sum % nbuckets);
56 }
57
58 typedef List *ListPtr;
59
Hash(int bs)60 Hash::Hash(int bs){
61 int i;
62 nbuckets=bs;
63 lbuckets=new ListPtr[nbuckets];
64
65 for (i=0;i<nbuckets;i++)
66 lbuckets[i]=new List();
67 }
68
~Hash()69 Hash::~Hash(){
70 int i;
71 List * list;
72 for (i=0;i<nbuckets;i++){
73 list=lbuckets[i];
74 list->empty(false);
75 delete list;
76 }
77 delete[] lbuckets;
78 }
79
add(Str * str,Object * obj)80 Hash::Result Hash::add(Str * str, Object * obj){
81 if (str){
82 // Index * i;
83 List * list;
84 list=lbuckets[function(str)];
85 if (list->nObjects()>0){
86 /*
87 for (i=list->getFirst();i!=list->getEnd();i=list->getNext(i)){
88 if (((Bucket*)list->getObject(i))->getStr()->isEqual(str)){
89 ((Bucket*)list->getObject(i))->setObject(obj);
90 return AddedOverwrite;
91 }
92 }
93 */
94 list->insert(list->getFirst(), new Bucket(str, obj));
95 return AddedCollision;
96 }else{
97 list->insert(list->getFirst(), new Bucket(str, obj));
98 return AddedNoCollision;
99 }
100 }
101 return NotAdded;
102 }
103
remove(Str * str,bool del)104 Hash::Result Hash::remove(Str * str, bool del){
105 if (str){
106 Index * i;
107 List * list=lbuckets[function(str)];
108
109 for (i=list->getFirst();i!=list->getEnd();i=list->getNext(i))
110 if (((Bucket *)list->getObject(i))->getStr()->isEqual(str)){
111 if (del)
112 delete ((Bucket *)list->getObject(i))->getObject();
113 list->remove(i, true);
114 delete str;
115 return Removed;
116 }
117 delete str;
118 }
119 return NotFound;
120 }
121
find(Str * str)122 Object * Hash::find(Str * str){
123 if (str){
124 Index * i;
125 List * list=lbuckets[function(str)];
126
127 i=list->getFirst();
128 while (i!=list->getEnd()){
129 if (((Bucket *)list->getObject(i))->getStr()->isEqual(str)){
130 delete str;
131 return ((Bucket *)list->getObject(i))->getObject();
132 }
133 i=list->getNext(i);
134 }
135 delete str;
136 }
137 return NULL;
138 }
139
empty(bool del)140 void Hash::empty(bool del){
141 int i;
142 List * list;
143 for (i=0;i<nbuckets;i++){
144 list=lbuckets[i];
145 if (del){
146 Index * idx=list->getFirst();
147 while (idx!=list->getEnd()){
148 delete ((Bucket*)list->getObject(idx))->getObject();
149 idx=list->getNext(idx);
150 }
151 }
152 list->empty(del);
153 }
154 }
155
156