Mercurial > hg > early-roguelike

annotate urogue/dict.c @ 281:4a3f4729257c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge the urogue and bugfix branches.
author John "Elwin" Edwards
date Fri, 15 Sep 2017 21:16:28 -0400
parents c495a4f288c6
children 13b482bd9e66
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
256
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
1 /*
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
2 dict.c
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
3
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
4 UltraRogue: The Ultimate Adventure in the Dungeons of Doom
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
5 Copyright (C) 1995 Herb Chong
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
6 All rights reserved.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
7
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
8 See the file LICENSE.TXT for full copyright and licensing information.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
9 */
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
10
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
11 /******************
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
12 ** Change history:
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
13 **
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
14 ** (AK:04/03/95) - In dict_create, initialize hook for extensions to dictionary structure.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
15 ** (AK:04/04/95) - In dict_insert, only set any_ptr when a new string entry is created.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
16 ** (AK:04/17/95) - Added dict_union and dict_merge.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
17 ** (AK:04/18/95) - In dict_create, added code to create signature,
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
18 ** table of contents, and parameter array.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
19 ** (AK:04/18/95) - Revised dict_load, dict_save
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
20 ** (AK:04/18/95) - Added dict_import
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
21 **
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
22 ******************/
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
23
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
24 static char sccsid[] = "%W% %G%";
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
25
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
26 #include <stdlib.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
27 #include <string.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
28 #if !defined(OS2) && !defined(_WIN32)
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
29 #include <unistd.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
30 #endif
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
31
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
32 #include "dict.h"
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
33 #include "dictutil.h"
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
34
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
35 #define BUFLEN 300
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
36
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
37 /*************************************************************************
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
38 * Generic dictionary and hash table functions for word and
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
39 * string storage.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
40 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
41 * Implements generic dictionary management by using a
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
42 * hash table with direct chaining. All terms are stored in a
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
43 * separate, unsorted, string table. When inserting into the
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
44 * hash table exceeds the current size, allocate a new hash table
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
45 * and rehash the old contents into the new table. When the string
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
46 * table fills, append more empty entries onto the old table and
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
47 * continue adding. Inserting a string that already exists increments
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
48 * the count for the string. Deleting a string only decrements the
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
49 * count to no less than 0. This will allow a 0 occurence string to be
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
50 * retrieved. To remove the 0 occurence string table entries, you must
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
51 * rebuild the dictionary. Merging from one dictionary to a new one will
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
52 * do this because it only copies nonzero occurences.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
53 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
54 * Assumptions:
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
55 * unsigned long >= 32 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
56 * int >= 16 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
57 * char == 8 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
58 * number of entries < 2^28
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
59 *************************************************************************/
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
60
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
61 /*************************************************************************
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
62 * hash_string: calculate hash value for string, modified
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
63 * version of hashpjw() from the new Dragon book.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
64 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
65 * s - string to calculate hash for
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
66 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
67 * Returns: hash value
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
68 *************************************************************************/
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
69 static unsigned long hash_string(const char *s)
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
70 {
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
71 unsigned long h = 0;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
72 unsigned long g = 0;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
73
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
74 while (*s) {
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
75 h <<= 4;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
76 h += *s++;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
77 if ((g = h & 0xf0000000) != 0)
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
78 h ^= g >> 24;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
79 }
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
80 return h ^ g;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
81 }
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
82
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
83 /*************************************************************************
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
84 * dict_create: create a dictionary and initialize its structures
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
85 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
86 * toc_size - number of entries in table of contents ( >= 4 )
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
87 * initial_string_count - number of strings to hold as initial allocation
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
88 * initial_hash_chains - size of hash table, must be power of 4
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
89 * max_chain_length - max number of elements in hash chain before signalling growth
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
90 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
91 * Returns: pointer to dictionary
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
92 * NULL - error creating dictionary
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards