1 /* hash.c by Adam Rogoyski <apoc@laker.net> Temperanc on EFNet irc
2  * Copyright (C) 1998, 1999 Adam Rogoyski
3  * --- GNU General Public License Disclamer ---
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11  * GNU General Public License for more details.
12  */
13 
14 
15 /* This file contains a simple hash for looking up changes we may have
16  * made to specific offsets in the file.  When we are editing a large
17  * file that cannot fit in memory, when we reread a portion of the file
18  * from disk, it will be the original, and not the changed, so we need
19  * to lookup changes and add them to the current buffer in memory.
20  * The Hash function is just a mod 1009 into the hash table of 0-1008
21  * entries.  Collisions are handled with just a list of entries for
22  * that index in the hash.  The key/pair is offset/byte-value.
23  */
24 
25 #include "hexedit.h"
26 
27 
28    /* All the books say this should usually be a prime number */
29 #define HASH_TABLE_SIZE   1009
30 
31    /* The really complex and thought out hash function.  */
32 #define HASH(x)    (x % HASH_TABLE_SIZE)
33 
34 
35    /* list of chained collisions */
36 struct hash_list
37 {
38    unsigned long offset;
39    unsigned char value;
40    struct hash_list *next;
41 };
42 
43 struct hash_table
44 {
45    struct hash_list *chain;
46 };
47 
48    /* hash table */
49 static struct hash_table *table = NULL;
50 
51 
52 
53 void
init_hash()54 init_hash ()
55    /* set each location empty by setting *next chain to -1 */
56 {
57    int i = 0;
58 
59    if (table)
60    {
61       struct hash_list *p = NULL;
62 
63       for (i = 0; i < HASH_TABLE_SIZE; i++)
64       {
65          while (table[i].chain)
66          {
67             p = table[i].chain->next;
68             free (table[i].chain);
69             table[i].chain = p;
70          }
71       }
72 
73       free (table);
74    }
75 
76    table = malloc (HASH_TABLE_SIZE * sizeof (struct hash_table));
77    if (!table)
78       die_horribly ("Not enough memory to create hash table\n", NULL);
79 
80    for (i = 0; i < HASH_TABLE_SIZE; i++)
81    {
82       table[i].chain = NULL;
83    }
84 }
85 
86 
87 void
clear_hash()88 clear_hash ()
89 {
90    int i = 0;
91    struct hash_list *p = NULL;
92 
93    for (i = 0; i < HASH_TABLE_SIZE; i++)
94    {
95       while (table[i].chain)
96       {
97          p = table[i].chain;
98          table[i].chain = table[i].chain->next;
99          free (p);
100       }
101    }
102 }
103 
104 
105 void
insert_hash_entry(unsigned long offset,unsigned char value)106 insert_hash_entry (unsigned long offset, unsigned char value)
107 {
108    int i = HASH(offset);
109 
110    if (!table[i].chain)
111       /* empty location in table */
112    {
113       table[i].chain = malloc (sizeof (struct hash_list));
114       if (!table[i].chain)
115          die_horribly (NOT_ENOUGH_MEMORY, NULL);
116 
117       table[i].chain->offset = offset;
118       table[i].chain->value  = value;
119       table[i].chain->next   = NULL;
120    }
121    else
122       /* Has at least one element in table.  Insert the new collision
123        * into the front of the chain.
124        */
125    {
126       struct hash_list *p = table[i].chain;
127 
128          /* First, make sure entry isn't already here, if it is, we
129           * change it to the new value.
130           */
131       while (p)
132       {
133          if (p->offset == offset)
134          {
135             p->value = value;
136             break;
137          }
138          p = p->next;
139       }
140       if (p)
141          return;       /* already in hash */
142 
143       p = malloc (sizeof (struct hash_list));
144       if (!p)
145          die_horribly (NOT_ENOUGH_MEMORY, NULL);
146 
147          /* build the new entry */
148       p->offset = offset;
149       p->value  = value;
150       p->next   = table[i].chain;
151 
152          /* now put entry in the front of the list */
153       table[i].chain = p;
154    }
155 }
156 
157 
158 void
delete_hash_entry(unsigned long offset)159 delete_hash_entry (unsigned long offset)
160 {
161    int i = HASH(offset);
162    struct hash_list *p = table[i].chain;
163 
164       /* hash entry not here */
165    if (!p)
166       return;
167 
168       /* one or more at this index */
169    else
170    {
171       struct hash_list *last = NULL;
172       while (p)
173       {
174          if (p->offset == offset)
175             break;
176          last = p;
177          p = p->next;
178       }
179          /* if we found it delete it */
180       if (p)
181       {
182             /* if item isn't first element */
183          if (last)
184          {
185             last->next = p->next;   /* skip over p */
186             free (p);               /* then delete it */
187          }
188          else
189          {
190             table[i].chain = p->next;  /* skip over p */
191             free (p);                   /* then delete it */
192          }
193       }
194    }
195 }
196 
197 
198 int
hash_lookup(unsigned long offset,unsigned char * c)199 hash_lookup (unsigned long offset, unsigned char *c)
200    /* return -1 on lookup failure.  Store value in *c if successful */
201 {
202    int i = HASH(offset);
203    struct hash_list *p = table[i].chain;
204 
205    while (p)
206    {
207       if (p->offset == offset)
208          break;
209       p = p->next;
210    }
211 
212    if (p)
213    {
214       if (c)
215          *c = p->value;
216       return 0;
217    }
218 
219    return -1;
220 }
221 
222 
223 #ifdef DEBUG_HASH
224 void
print_hash_table()225 print_hash_table ()
226 {
227    int i = 0;
228 
229    for (i = 0; i < HASH_TABLE_SIZE; i++)
230    {
231       fprintf (stderr, "%d: ", i);
232          /* empty entry */
233       if (!table[i].chain)
234          fprintf (stderr, "empty\n");
235       else
236       {
237          struct hash_list *p = table[i].chain;
238          while (p)
239          {
240             fprintf (stderr, "(%ld,%d) ", p->offset, p->value);
241             p = p->next;
242          }
243          fprintf (stderr, "\n");
244       }
245    }
246 }
247 #endif
248 
249 
250 void
commit_changes_in_hash(FILE * fp)251 commit_changes_in_hash (FILE *fp)
252    /* cycle through the hash and write back all the entries, and clear
253     * the hash while we're at it.
254     */
255 {
256    int i = 0;
257    int result = 0;
258    struct hash_list *p = NULL;
259 
260    for (i = 0; i < HASH_TABLE_SIZE; i++)
261    {
262       p = table[i].chain;
263       while (table[i].chain)
264       {
265          result = fseek (fp, table[i].chain->offset, SEEK_SET);
266          if (result)
267             die_horribly ("Cannot write new file correctly", "fseek");
268 
269          result = fwrite (&table[i].chain->value, 1, 1, fp);
270          if (!result && ferror (fp))
271             die_horribly ("File writing error", "ferror");
272          else if (!result && feof (fp))
273             die_horribly ("End of File Reached?", "feof");
274 
275          p = table[i].chain->next;
276          free (table[i].chain);
277          table[i].chain = p;
278       }
279    }
280 }
281