Mercurial > hg > early-roguelike

annotate urogue/dict.c @ 292:ebf49a933e51

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
UltraRogue: ask about unidentified magic items by default.
author John "Elwin" Edwards
date Fri, 29 Dec 2017 14:16:24 -0500
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