|
1 /* |
|
2 * Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * Hash class for imgcheck tool. All the executable names of ROM/ROFS |
|
16 * are stored into this hash table. After gathering the dependencies |
|
17 * for those executables, dependencies existence is checked very |
|
18 * efficiently using this table. |
|
19 * |
|
20 */ |
|
21 |
|
22 |
|
23 /** |
|
24 @file |
|
25 @internalComponent |
|
26 @released |
|
27 */ |
|
28 |
|
29 #include "common.h" |
|
30 #include "hash.h" |
|
31 |
|
32 /** |
|
33 Constructor, intializes the table size |
|
34 |
|
35 @internalComponent |
|
36 @released |
|
37 |
|
38 @param aSize - Hash table size (Number of dissimilar data can stored) |
|
39 */ |
|
40 HashTable::HashTable(int aSize) |
|
41 :iSize(aSize) |
|
42 { |
|
43 } |
|
44 |
|
45 /** |
|
46 Destructor |
|
47 |
|
48 @internalComponent |
|
49 @released |
|
50 */ |
|
51 HashTable::~HashTable() |
|
52 { |
|
53 } |
|
54 |
|
55 /** |
|
56 Function responsible to return the Hash value for the received string. |
|
57 |
|
58 @internalComponent |
|
59 @released |
|
60 |
|
61 @param aString - String on which Hash value calcualtion to be done |
|
62 */ |
|
63 int HashTable::Hash(String aString) |
|
64 { |
|
65 unsigned int hashVal = 0; |
|
66 int length = aString.length(); |
|
67 /* we start our hash out at 0 */ |
|
68 |
|
69 /* for each character, we multiply the old hash by 31 and add the current |
|
70 * character. Remember that shifting a number left is equivalent to |
|
71 * multiplying it by 2 raised to the number of places shifted. So we |
|
72 * are in effect multiplying hashval by 32 and then subtracting hashval. |
|
73 * Why do we do this? Because shifting and subtraction are much more |
|
74 * efficient operations than multiplication. |
|
75 */ |
|
76 for(int strIter = 0; strIter < length ; strIter++) |
|
77 { |
|
78 hashVal = aString[strIter] + (hashVal << 5) - hashVal; |
|
79 } |
|
80 /* we then return the hash value mod the hashtable size so that it will |
|
81 * fit into the necessary range |
|
82 */ |
|
83 return hashVal % iSize; |
|
84 |
|
85 } |
|
86 |
|
87 /** |
|
88 Function returns ture or false based on the String availability in Hash |
|
89 |
|
90 @internalComponent |
|
91 @released |
|
92 |
|
93 @param aString - String which needs to be searched |
|
94 */ |
|
95 bool HashTable::IsAvailable(String aString) |
|
96 { |
|
97 unsigned int hashVal = Hash(aString); |
|
98 if (iTable[hashVal].size() > 0) |
|
99 { |
|
100 StringList nameList = iTable[hashVal]; |
|
101 StringList::iterator listIter = nameList.begin(); |
|
102 while(listIter != nameList.end()) |
|
103 { |
|
104 if ((*listIter) == aString) |
|
105 { |
|
106 return true; |
|
107 } |
|
108 ++listIter; |
|
109 } |
|
110 } |
|
111 return false; |
|
112 } |
|
113 |
|
114 /** |
|
115 Function responsible to insert a single string into Hash table |
|
116 |
|
117 @internalComponent |
|
118 @released |
|
119 |
|
120 @param aString - String which needs to be inserted |
|
121 */ |
|
122 void HashTable::Insert(String aString) |
|
123 { |
|
124 unsigned int hashVal = Hash(aString); |
|
125 if(!IsAvailable(aString)) //Is exists |
|
126 { |
|
127 iTable[hashVal].push_back(aString); |
|
128 } |
|
129 } |
|
130 |
|
131 /** |
|
132 Function responsible to insert list of strings into Hash table |
|
133 |
|
134 @internalComponent |
|
135 @released |
|
136 |
|
137 @param aString - String which needs to be inserted |
|
138 */ |
|
139 void HashTable::InsertStringList(StringList& aList) |
|
140 { |
|
141 StringList::iterator beginIter = aList.begin(); |
|
142 StringList::iterator endIter = aList.end(); |
|
143 while(beginIter != endIter) |
|
144 { |
|
145 Insert((*beginIter)); |
|
146 ++beginIter; |
|
147 } |
|
148 } |
|
149 |
|
150 /** |
|
151 Function to delete an entry from Hash |
|
152 |
|
153 @internalComponent |
|
154 @released |
|
155 |
|
156 @param aString - String which needs to be deleted |
|
157 */ |
|
158 void HashTable::Delete(String aString) |
|
159 { |
|
160 unsigned int hashVal = Hash(aString); |
|
161 if(iTable[hashVal].size() > 0) |
|
162 { |
|
163 StringList list = iTable[hashVal]; |
|
164 StringList::iterator beginIter = list.begin(); |
|
165 StringList::iterator endIter = list.end(); |
|
166 while(beginIter != endIter) |
|
167 { |
|
168 if((*beginIter) == aString) |
|
169 { |
|
170 list.erase(beginIter); |
|
171 iTable[hashVal] = list; |
|
172 return; |
|
173 } |
|
174 ++beginIter; |
|
175 } |
|
176 } |
|
177 } |