Mercurial > hg > early-roguelike

annotate urogue/dict.c @ 310:827441d05b3e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Advanced Rogue family: fix some potential buffer overflows. Some code for determining the score file location assumed that PATH_MAX would be less than 1024, which cannot be guaranteed. Advanced Rogue 5 and 7, and XRogue, have had the buffers for the file name enlarged. UltraRogue never called the functions, so the code has been deleted instead.
author John "Elwin" Edwards
date Mon, 03 May 2021 19:05:37 -0400
parents 13b482bd9e66
children
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 #include <stdlib.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
25 #include <string.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
26 #if !defined(OS2) && !defined(_WIN32)
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
27 #include <unistd.h>
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
28 #endif
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
29
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
30 #include "dict.h"
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
31 #include "dictutil.h"
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
32
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
33 #define BUFLEN 300
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 /*************************************************************************
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
36 * Generic dictionary and hash table functions for word and
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
37 * string storage.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
38 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
39 * Implements generic dictionary management by using a
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
40 * 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
41 * separate, unsorted, string table. When inserting into the
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
42 * 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
43 * 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
44 * 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
45 * continue adding. Inserting a string that already exists increments
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
46 * 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
47 * 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
48 * 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
49 * 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
50 * do this because it only copies nonzero occurences.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
51 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
52 * Assumptions:
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
53 * unsigned long >= 32 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
54 * int >= 16 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
55 * char == 8 bits
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
56 * number of entries < 2^28
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
57 *************************************************************************/
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
58
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 * hash_string: calculate hash value for string, modified
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
61 * version of hashpjw() from the new Dragon book.
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
62 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
63 * s - string to calculate hash for
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 * Returns: hash value
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 static unsigned long hash_string(const char *s)
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 unsigned long h = 0;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
70 unsigned long g = 0;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
71
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
72 while (*s) {
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
73 h <<= 4;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
74 h += *s++;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
75 if ((g = h & 0xf0000000) != 0)
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
76 h ^= g >> 24;
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
77 }
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
78 return h ^ g;
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
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 * dict_create: create a dictionary and initialize its structures
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 * 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
85 * 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
86 * 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
87 * 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
88 *
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
89 * Returns: pointer to dictionary
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
90 * NULL - error creating dictionary
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
91 * non-NULL - sucessful creation
c495a4f288c6 Import UltraRogue from the Roguelike Restoration Project (r1490)
John "Elwin" Edwards
parents:
diff changeset
92 *************************************************************************/