1 /*******************************************************/
2 /* "C" Language Integrated Production System */
3 /* */
4 /* CLIPS Version 6.30 08/16/14 */
5 /* */
6 /* FACT HASHING MODULE */
7 /*******************************************************/
8
9 /*************************************************************/
10 /* Purpose: Provides routines for maintaining a fact hash */
11 /* table so that duplication of facts can quickly be */
12 /* determined. */
13 /* */
14 /* Principal Programmer(s): */
15 /* Gary D. Riley */
16 /* */
17 /* Contributing Programmer(s): */
18 /* */
19 /* Revision History: */
20 /* */
21 /* 6.24: Removed LOGICAL_DEPENDENCIES compilation flag. */
22 /* */
23 /* Renamed BOOLEAN macro type to intBool. */
24 /* */
25 /* 6.30: Fact hash table is resizable. */
26 /* */
27 /* Changed integer type/precision. */
28 /* */
29 /* Added FactWillBeAsserted. */
30 /* */
31 /* Converted API macros to function calls. */
32 /* */
33 /*************************************************************/
34
35 #define _FACTHSH_SOURCE_
36
37 #include <stdio.h>
38 #define _STDIO_INCLUDED_
39 #include <stdlib.h>
40
41 #include "setup.h"
42
43 #if DEFTEMPLATE_CONSTRUCT
44
45 #include "constant.h"
46 #include "memalloc.h"
47 #include "router.h"
48 #include "sysdep.h"
49 #include "envrnmnt.h"
50
51 #if DEFRULE_CONSTRUCT
52 #include "lgcldpnd.h"
53 #endif
54
55 #include "facthsh.h"
56
57 /***************************************/
58 /* LOCAL INTERNAL FUNCTION DEFINITIONS */
59 /***************************************/
60
61 static struct fact *FactExists(void *,struct fact *,unsigned long);
62 static struct factHashEntry **CreateFactHashTable(void *,unsigned long);
63 static void ResizeFactHashTable(void *);
64 static void ResetFactHashTable(void *);
65
66 /************************************************/
67 /* HashFact: Returns the hash value for a fact. */
68 /************************************************/
HashFact(struct fact * theFact)69 unsigned long HashFact(
70 struct fact *theFact)
71 {
72 unsigned long count = 0;
73
74 /*============================================*/
75 /* Get a hash value for the deftemplate name. */
76 /*============================================*/
77
78 count += (unsigned long) theFact->whichDeftemplate->header.name->bucket * 73981;
79
80 /*=================================================*/
81 /* Add in the hash value for the rest of the fact. */
82 /*=================================================*/
83
84 count += HashMultifield(&theFact->theProposition,0);
85
86 /*================================*/
87 /* Make sure the hash value falls */
88 /* in the appropriate range. */
89 /*================================*/
90
91 theFact->hashValue = count;
92
93 /*========================*/
94 /* Return the hash value. */
95 /*========================*/
96
97 return(count);
98 }
99
100 /**********************************************/
101 /* FactExists: Determines if a specified fact */
102 /* already exists in the fact hash table. */
103 /**********************************************/
FactExists(void * theEnv,struct fact * theFact,unsigned long hashValue)104 static struct fact *FactExists(
105 void *theEnv,
106 struct fact *theFact,
107 unsigned long hashValue)
108 {
109 struct factHashEntry *theFactHash;
110
111 hashValue = (hashValue % FactData(theEnv)->FactHashTableSize);
112
113 for (theFactHash = FactData(theEnv)->FactHashTable[hashValue];
114 theFactHash != NULL;
115 theFactHash = theFactHash->next)
116 {
117 if (theFact->hashValue != theFactHash->theFact->hashValue)
118 { continue; }
119
120 if ((theFact->whichDeftemplate == theFactHash->theFact->whichDeftemplate) ?
121 MultifieldsEqual(&theFact->theProposition,
122 &theFactHash->theFact->theProposition) : FALSE)
123 { return(theFactHash->theFact); }
124 }
125
126 return(NULL);
127 }
128
129 /************************************************************/
130 /* AddHashedFact: Adds a fact entry to the fact hash table. */
131 /************************************************************/
AddHashedFact(void * theEnv,struct fact * theFact,unsigned long hashValue)132 globle void AddHashedFact(
133 void *theEnv,
134 struct fact *theFact,
135 unsigned long hashValue)
136 {
137 struct factHashEntry *newhash, *temp;
138
139 if (FactData(theEnv)->NumberOfFacts > FactData(theEnv)->FactHashTableSize)
140 { ResizeFactHashTable(theEnv); }
141
142 newhash = get_struct(theEnv,factHashEntry);
143 newhash->theFact = theFact;
144
145 hashValue = (hashValue % FactData(theEnv)->FactHashTableSize);
146
147 temp = FactData(theEnv)->FactHashTable[hashValue];
148 FactData(theEnv)->FactHashTable[hashValue] = newhash;
149 newhash->next = temp;
150 }
151
152 /******************************************/
153 /* RemoveHashedFact: Removes a fact entry */
154 /* from the fact hash table. */
155 /******************************************/
RemoveHashedFact(void * theEnv,struct fact * theFact)156 globle intBool RemoveHashedFact(
157 void *theEnv,
158 struct fact *theFact)
159 {
160 unsigned long hashValue;
161 struct factHashEntry *hptr, *prev;
162
163 hashValue = HashFact(theFact);
164 hashValue = (hashValue % FactData(theEnv)->FactHashTableSize);
165
166 for (hptr = FactData(theEnv)->FactHashTable[hashValue], prev = NULL;
167 hptr != NULL;
168 hptr = hptr->next)
169 {
170 if (hptr->theFact == theFact)
171 {
172 if (prev == NULL)
173 {
174 FactData(theEnv)->FactHashTable[hashValue] = hptr->next;
175 rtn_struct(theEnv,factHashEntry,hptr);
176 if (FactData(theEnv)->NumberOfFacts == 1)
177 { ResetFactHashTable(theEnv); }
178 return(1);
179 }
180 else
181 {
182 prev->next = hptr->next;
183 rtn_struct(theEnv,factHashEntry,hptr);
184 if (FactData(theEnv)->NumberOfFacts == 1)
185 { ResetFactHashTable(theEnv); }
186 return(1);
187 }
188 }
189 prev = hptr;
190 }
191
192 return(0);
193 }
194
195 /****************************************************/
196 /* FactWillBeAsserted: Determines if a fact will be */
197 /* asserted based on the duplication settings. */
198 /****************************************************/
FactWillBeAsserted(void * theEnv,void * theFact)199 globle intBool FactWillBeAsserted(
200 void *theEnv,
201 void *theFact)
202 {
203 struct fact *tempPtr;
204 unsigned long hashValue;
205
206 if (FactData(theEnv)->FactDuplication) return(TRUE);
207
208 hashValue = HashFact((struct fact *) theFact);
209
210 tempPtr = FactExists(theEnv,(struct fact *) theFact,hashValue);
211 if (tempPtr == NULL) return(TRUE);
212
213 return(FALSE);
214 }
215
216 /*****************************************************/
217 /* HandleFactDuplication: Determines if a fact to be */
218 /* added to the fact-list is a duplicate entry and */
219 /* takes appropriate action based on the current */
220 /* setting of the fact-duplication flag. */
221 /*****************************************************/
HandleFactDuplication(void * theEnv,void * theFact,intBool * duplicate)222 globle unsigned long HandleFactDuplication(
223 void *theEnv,
224 void *theFact,
225 intBool *duplicate)
226 {
227 struct fact *tempPtr;
228 unsigned long hashValue;
229 *duplicate = FALSE;
230
231 hashValue = HashFact((struct fact *) theFact);
232
233 if (FactData(theEnv)->FactDuplication) return(hashValue);
234
235 tempPtr = FactExists(theEnv,(struct fact *) theFact,hashValue);
236 if (tempPtr == NULL) return(hashValue);
237
238 ReturnFact(theEnv,(struct fact *) theFact);
239 #if DEFRULE_CONSTRUCT
240 AddLogicalDependencies(theEnv,(struct patternEntity *) tempPtr,TRUE);
241 #endif
242 *duplicate = TRUE;
243 return(0);
244 }
245
246 /*******************************************/
247 /* EnvGetFactDuplication: C access routine */
248 /* for the get-fact-duplication command. */
249 /*******************************************/
EnvGetFactDuplication(void * theEnv)250 globle intBool EnvGetFactDuplication(
251 void *theEnv)
252 {
253 return(FactData(theEnv)->FactDuplication);
254 }
255
256 /*******************************************/
257 /* EnvSetFactDuplication: C access routine */
258 /* for the set-fact-duplication command. */
259 /*******************************************/
EnvSetFactDuplication(void * theEnv,int value)260 globle intBool EnvSetFactDuplication(
261 void *theEnv,
262 int value)
263 {
264 int ov;
265
266 ov = FactData(theEnv)->FactDuplication;
267 FactData(theEnv)->FactDuplication = value;
268 return(ov);
269 }
270
271 /**************************************************/
272 /* InitializeFactHashTable: Initializes the table */
273 /* entries in the fact hash table to NULL. */
274 /**************************************************/
InitializeFactHashTable(void * theEnv)275 globle void InitializeFactHashTable(
276 void *theEnv)
277 {
278 FactData(theEnv)->FactHashTable = CreateFactHashTable(theEnv,SIZE_FACT_HASH);
279 FactData(theEnv)->FactHashTableSize = SIZE_FACT_HASH;
280 }
281
282 /*******************************************************************/
283 /* CreateFactHashTable: Creates and initializes a fact hash table. */
284 /*******************************************************************/
CreateFactHashTable(void * theEnv,unsigned long tableSize)285 static struct factHashEntry **CreateFactHashTable(
286 void *theEnv,
287 unsigned long tableSize)
288 {
289 unsigned long i;
290 struct factHashEntry **theTable;
291
292 theTable = (struct factHashEntry **)
293 gm3(theEnv,sizeof (struct factHashEntry *) * tableSize);
294
295 if (theTable == NULL) EnvExitRouter(theEnv,EXIT_FAILURE);
296
297 for (i = 0; i < tableSize; i++) theTable[i] = NULL;
298
299 return(theTable);
300 }
301
302 /*******************************************************************/
303 /* ResizeFactHashTable: */
304 /*******************************************************************/
ResizeFactHashTable(void * theEnv)305 static void ResizeFactHashTable(
306 void *theEnv)
307 {
308 unsigned long i, newSize, newLocation;
309 struct factHashEntry **theTable, **newTable;
310 struct factHashEntry *theEntry, *nextEntry;
311
312 theTable = FactData(theEnv)->FactHashTable;
313
314 newSize = (FactData(theEnv)->FactHashTableSize * 2) + 1;
315 newTable = CreateFactHashTable(theEnv,newSize);
316
317 /*========================================*/
318 /* Copy the old entries to the new table. */
319 /*========================================*/
320
321 for (i = 0; i < FactData(theEnv)->FactHashTableSize; i++)
322 {
323 theEntry = theTable[i];
324 while (theEntry != NULL)
325 {
326 nextEntry = theEntry->next;
327
328 newLocation = theEntry->theFact->hashValue % newSize;
329 theEntry->next = newTable[newLocation];
330 newTable[newLocation] = theEntry;
331
332 theEntry = nextEntry;
333 }
334 }
335
336 /*=====================================================*/
337 /* Replace the old hash table with the new hash table. */
338 /*=====================================================*/
339
340 rm3(theEnv,theTable,sizeof(struct factHashEntry *) * FactData(theEnv)->FactHashTableSize);
341 FactData(theEnv)->FactHashTableSize = newSize;
342 FactData(theEnv)->FactHashTable = newTable;
343 }
344
345 /*******************************************************************/
346 /* ResetFactHashTable: */
347 /*******************************************************************/
ResetFactHashTable(void * theEnv)348 static void ResetFactHashTable(
349 void *theEnv)
350 {
351 struct factHashEntry **newTable;
352
353 /*=============================================*/
354 /* Don't reset the table unless the hash table */
355 /* has been expanded from its original size. */
356 /*=============================================*/
357
358 if (FactData(theEnv)->FactHashTableSize == SIZE_FACT_HASH)
359 { return; }
360
361 /*=======================*/
362 /* Create the new table. */
363 /*=======================*/
364
365 newTable = CreateFactHashTable(theEnv,SIZE_FACT_HASH);
366
367 /*=====================================================*/
368 /* Replace the old hash table with the new hash table. */
369 /*=====================================================*/
370
371 rm3(theEnv,FactData(theEnv)->FactHashTable,sizeof(struct factHashEntry *) * FactData(theEnv)->FactHashTableSize);
372 FactData(theEnv)->FactHashTableSize = SIZE_FACT_HASH;
373 FactData(theEnv)->FactHashTable = newTable;
374 }
375
376 #if DEVELOPER
377
378 /*****************************************************/
379 /* ShowFactHashTable: Displays the number of entries */
380 /* in each slot of the fact hash table. */
381 /*****************************************************/
ShowFactHashTable(void * theEnv)382 globle void ShowFactHashTable(
383 void *theEnv)
384 {
385 int i, count;
386 struct factHashEntry *theEntry;
387 char buffer[20];
388
389 for (i = 0; i < FactData(theEnv)->FactHashTableSize; i++)
390 {
391 for (theEntry = FactData(theEnv)->FactHashTable[i], count = 0;
392 theEntry != NULL;
393 theEntry = theEntry->next)
394 { count++; }
395
396 if (count != 0)
397 {
398 gensprintf(buffer,"%4d: %4d\n",i,count);
399 EnvPrintRouter(theEnv,WDISPLAY,buffer);
400 }
401 }
402 }
403
404 #endif /* DEVELOPER */
405
406 /*#####################################*/
407 /* ALLOW_ENVIRONMENT_GLOBALS Functions */
408 /*#####################################*/
409
410 #if ALLOW_ENVIRONMENT_GLOBALS
411
GetFactDuplication()412 globle intBool GetFactDuplication()
413 {
414 return EnvGetFactDuplication(GetCurrentEnvironment());
415 }
416
SetFactDuplication(int value)417 globle intBool SetFactDuplication(
418 int value)
419 {
420 return EnvSetFactDuplication(GetCurrentEnvironment(),value);
421 }
422
423 #endif /* ALLOW_ENVIRONMENT_GLOBALS */
424
425 #endif /* DEFTEMPLATE_CONSTRUCT */
426
427