1/******************************************************************* 2** d i c t . c 3** Forth Inspired Command Language - dictionary methods 4** Author: John Sadler (john_sadler@alum.mit.edu) 5** Created: 19 July 1997 6** $Id: dict.c,v 1.14 2001/12/05 07:21:34 jsadler Exp $ 7*******************************************************************/ 8/* 9** This file implements the dictionary -- FICL's model of 10** memory management. All FICL words are stored in the 11** dictionary. A word is a named chunk of data with its 12** associated code. FICL treats all words the same, even 13** precompiled ones, so your words become first-class 14** extensions of the language. You can even define new 15** control structures. 16** 17** 29 jun 1998 (sadler) added variable sized hash table support 18*/ 19/* 20** Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu) 21** All rights reserved. 22** 23** Get the latest Ficl release at http://ficl.sourceforge.net 24** 25** I am interested in hearing from anyone who uses ficl. If you have 26** a problem, a success story, a defect, an enhancement request, or 27** if you would like to contribute to the ficl release, please 28** contact me by email at the address above. 29** 30** L I C E N S E and D I S C L A I M E R 31** 32** Redistribution and use in source and binary forms, with or without 33** modification, are permitted provided that the following conditions 34** are met: 35** 1. Redistributions of source code must retain the above copyright 36** notice, this list of conditions and the following disclaimer. 37** 2. Redistributions in binary form must reproduce the above copyright 38** notice, this list of conditions and the following disclaimer in the 39** documentation and/or other materials provided with the distribution. 40** 41** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 42** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51** SUCH DAMAGE. 52*/ 53 54 55#ifdef TESTMAIN 56#include <stdio.h> 57#include <ctype.h> 58#else 59#include <stand.h> 60#endif 61#include <string.h> 62#include "ficl.h" 63 64/* Dictionary on-demand resizing control variables */ 65CELL dictThreshold; 66CELL dictIncrease; 67 68 69static char *dictCopyName(FICL_DICT *pDict, STRINGINFO si); 70 71/************************************************************************** 72 d i c t A b o r t D e f i n i t i o n 73** Abort a definition in process: reclaim its memory and unlink it 74** from the dictionary list. Assumes that there is a smudged 75** definition in process...otherwise does nothing. 76** NOTE: this function is not smart enough to unlink a word that 77** has been successfully defined (ie linked into a hash). It 78** only works for defs in process. If the def has been unsmudged, 79** nothing happens. 80**************************************************************************/ 81void dictAbortDefinition(FICL_DICT *pDict) 82{ 83 FICL_WORD *pFW; 84 ficlLockDictionary(TRUE); 85 pFW = pDict->smudge; 86 87 if (pFW->flags & FW_SMUDGE) 88 pDict->here = (CELL *)pFW->name; 89 90 ficlLockDictionary(FALSE); 91 return; 92} 93 94 95/************************************************************************** 96 a l i g n P t r 97** Aligns the given pointer to FICL_ALIGN address units. 98** Returns the aligned pointer value. 99**************************************************************************/ 100void *alignPtr(void *ptr) 101{ 102#if FICL_ALIGN > 0 103 char *cp; 104 CELL c; 105 cp = (char *)ptr + FICL_ALIGN_ADD; 106 c.p = (void *)cp; 107 c.u = c.u & (~FICL_ALIGN_ADD); 108 ptr = (CELL *)c.p; 109#endif 110 return ptr; 111} 112 113 114/************************************************************************** 115 d i c t A l i g n 116** Align the dictionary's free space pointer 117**************************************************************************/ 118void dictAlign(FICL_DICT *pDict) 119{ 120 pDict->here = alignPtr(pDict->here); 121} 122 123 124/************************************************************************** 125 d i c t A l l o t 126** Allocate or remove n chars of dictionary space, with 127** checks for underrun and overrun 128**************************************************************************/ 129int dictAllot(FICL_DICT *pDict, int n) 130{ 131 char *cp = (char *)pDict->here; 132#if FICL_ROBUST 133 if (n > 0) 134 { 135 if ((unsigned)n <= dictCellsAvail(pDict) * sizeof (CELL)) 136 cp += n; 137 else 138 return 1; /* dict is full */ 139 } 140 else 141 { 142 n = -n; 143 if ((unsigned)n <= dictCellsUsed(pDict) * sizeof (CELL)) 144 cp -= n; 145 else /* prevent underflow */ 146 cp -= dictCellsUsed(pDict) * sizeof (CELL); 147 } 148#else 149 cp += n; 150#endif 151 pDict->here = PTRtoCELL cp; 152 return 0; 153} 154 155 156/************************************************************************** 157 d i c t A l l o t C e l l s 158** Reserve space for the requested number of cells in the 159** dictionary. If nCells < 0 , removes space from the dictionary. 160**************************************************************************/ 161int dictAllotCells(FICL_DICT *pDict, int nCells) 162{ 163#if FICL_ROBUST 164 if (nCells > 0) 165 { 166 if (nCells <= dictCellsAvail(pDict)) 167 pDict->here += nCells; 168 else 169 return 1; /* dict is full */ 170 } 171 else 172 { 173 nCells = -nCells; 174 if (nCells <= dictCellsUsed(pDict)) 175 pDict->here -= nCells; 176 else /* prevent underflow */ 177 pDict->here -= dictCellsUsed(pDict); 178 } 179#else 180 pDict->here += nCells; 181#endif 182 return 0; 183} 184 185 186/************************************************************************** 187 d i c t A p p e n d C e l l 188** Append the specified cell to the dictionary 189**************************************************************************/ 190void dictAppendCell(FICL_DICT *pDict, CELL c) 191{ 192 *pDict->here++ = c; 193 return; 194} 195 196 197/************************************************************************** 198 d i c t A p p e n d C h a r 199** Append the specified char to the dictionary 200**************************************************************************/ 201void dictAppendChar(FICL_DICT *pDict, char c) 202{ 203 char *cp = (char *)pDict->here; 204 *cp++ = c; 205 pDict->here = PTRtoCELL cp; 206 return; 207} 208 209 210/************************************************************************** 211 d i c t A p p e n d W o r d 212** Create a new word in the dictionary with the specified 213** name, code, and flags. Name must be NULL-terminated. 214**************************************************************************/ 215FICL_WORD *dictAppendWord(FICL_DICT *pDict, 216 char *name, 217 FICL_CODE pCode, 218 UNS8 flags) 219{ 220 STRINGINFO si; 221 SI_SETLEN(si, strlen(name)); 222 SI_SETPTR(si, name); 223 return dictAppendWord2(pDict, si, pCode, flags); 224} 225 226 227/************************************************************************** 228 d i c t A p p e n d W o r d 2 229** Create a new word in the dictionary with the specified 230** STRINGINFO, code, and flags. Does not require a NULL-terminated 231** name. 232**************************************************************************/ 233FICL_WORD *dictAppendWord2(FICL_DICT *pDict, 234 STRINGINFO si, 235 FICL_CODE pCode, 236 UNS8 flags) 237{ 238 FICL_COUNT len = (FICL_COUNT)SI_COUNT(si); 239 char *pName; 240 FICL_WORD *pFW; 241 242 ficlLockDictionary(TRUE); 243 244 /* 245 ** NOTE: dictCopyName advances "here" as a side-effect. 246 ** It must execute before pFW is initialized. 247 */ 248 pName = dictCopyName(pDict, si); 249 pFW = (FICL_WORD *)pDict->here; 250 pDict->smudge = pFW; 251 pFW->hash = hashHashCode(si); 252 pFW->code = pCode; 253 pFW->flags = (UNS8)(flags | FW_SMUDGE); 254 pFW->nName = (char)len; 255 pFW->name = pName; 256 /* 257 ** Point "here" to first cell of new word's param area... 258 */ 259 pDict->here = pFW->param; 260 261 if (!(flags & FW_SMUDGE)) 262 dictUnsmudge(pDict); 263 264 ficlLockDictionary(FALSE); 265 return pFW; 266} 267 268 269/************************************************************************** 270 d i c t A p p e n d U N S 271** Append the specified FICL_UNS to the dictionary 272**************************************************************************/ 273void dictAppendUNS(FICL_DICT *pDict, FICL_UNS u) 274{ 275 *pDict->here++ = LVALUEtoCELL(u); 276 return; 277} 278 279 280/************************************************************************** 281 d i c t C e l l s A v a i l 282** Returns the number of empty cells left in the dictionary 283**************************************************************************/ 284int dictCellsAvail(FICL_DICT *pDict) 285{ 286 return pDict->size - dictCellsUsed(pDict); 287} 288 289 290/************************************************************************** 291 d i c t C e l l s U s e d 292** Returns the number of cells consumed in the dicionary 293**************************************************************************/ 294int dictCellsUsed(FICL_DICT *pDict) 295{ 296 return pDict->here - pDict->dict; 297} 298 299 300/************************************************************************** 301 d i c t C h e c k 302** Checks the dictionary for corruption and throws appropriate 303** errors. 304** Input: +n number of ADDRESS UNITS (not Cells) proposed to allot 305** -n number of ADDRESS UNITS proposed to de-allot 306** 0 just do a consistency check 307**************************************************************************/ 308void dictCheck(FICL_DICT *pDict, FICL_VM *pVM, int n) 309{ 310 if ((n >= 0) && (dictCellsAvail(pDict) * (int)sizeof(CELL) < n)) 311 { 312 vmThrowErr(pVM, "Error: dictionary full"); 313 } 314 315 if ((n <= 0) && (dictCellsUsed(pDict) * (int)sizeof(CELL) < -n)) 316 { 317 vmThrowErr(pVM, "Error: dictionary underflow"); 318 } 319 320 if (pDict->nLists > FICL_DEFAULT_VOCS) 321 { 322 dictResetSearchOrder(pDict); 323 vmThrowErr(pVM, "Error: search order overflow"); 324 } 325 else if (pDict->nLists < 0) 326 { 327 dictResetSearchOrder(pDict); 328 vmThrowErr(pVM, "Error: search order underflow"); 329 } 330 331 return; 332} 333 334 335/************************************************************************** 336 d i c t C o p y N a m e 337** Copy up to nFICLNAME characters of the name specified by si into 338** the dictionary starting at "here", then NULL-terminate the name, 339** point "here" to the next available byte, and return the address of 340** the beginning of the name. Used by dictAppendWord. 341** N O T E S : 342** 1. "here" is guaranteed to be aligned after this operation. 343** 2. If the string has zero length, align and return "here" 344**************************************************************************/ 345static char *dictCopyName(FICL_DICT *pDict, STRINGINFO si) 346{ 347 char *oldCP = (char *)pDict->here; 348 char *cp = oldCP; 349 char *name = SI_PTR(si); 350 int i = SI_COUNT(si); 351 352 if (i == 0) 353 { 354 dictAlign(pDict); 355 return (char *)pDict->here; 356 } 357 358 if (i > nFICLNAME) 359 i = nFICLNAME; 360 361 for (; i > 0; --i) 362 { 363 *cp++ = *name++; 364 } 365 366 *cp++ = '\0'; 367 368 pDict->here = PTRtoCELL cp; 369 dictAlign(pDict); 370 return oldCP; 371} 372 373 374/************************************************************************** 375 d i c t C r e a t e 376** Create and initialize a dictionary with the specified number 377** of cells capacity, and no hashing (hash size == 1). 378**************************************************************************/ 379FICL_DICT *dictCreate(unsigned nCells) 380{ 381 return dictCreateHashed(nCells, 1); 382} 383 384 385FICL_DICT *dictCreateHashed(unsigned nCells, unsigned nHash) 386{ 387 FICL_DICT *pDict; 388 size_t nAlloc; 389 390 nAlloc = sizeof (FICL_HASH) + nCells * sizeof (CELL) 391 + (nHash - 1) * sizeof (FICL_WORD *); 392 393 pDict = ficlMalloc(sizeof (FICL_DICT)); 394 assert(pDict); 395 memset(pDict, 0, sizeof (FICL_DICT)); 396 pDict->dict = ficlMalloc(nAlloc); 397 assert(pDict->dict); 398 399 pDict->size = nCells; 400 dictEmpty(pDict, nHash); 401 return pDict; 402} 403 404 405/************************************************************************** 406 d i c t C r e a t e W o r d l i s t 407** Create and initialize an anonymous wordlist 408**************************************************************************/ 409FICL_HASH *dictCreateWordlist(FICL_DICT *dp, int nBuckets) 410{ 411 FICL_HASH *pHash; 412 413 dictAlign(dp); 414 pHash = (FICL_HASH *)dp->here; 415 dictAllot(dp, sizeof (FICL_HASH) 416 + (nBuckets-1) * sizeof (FICL_WORD *)); 417 418 pHash->size = nBuckets; 419 hashReset(pHash); 420 return pHash; 421} 422 423 424/************************************************************************** 425 d i c t D e l e t e 426** Free all memory allocated for the given dictionary 427**************************************************************************/ 428void dictDelete(FICL_DICT *pDict) 429{ 430 assert(pDict); 431 ficlFree(pDict); 432 return; 433} 434 435 436/************************************************************************** 437 d i c t E m p t y 438** Empty the dictionary, reset its hash table, and reset its search order. 439** Clears and (re-)creates the hash table with the size specified by nHash. 440**************************************************************************/ 441void dictEmpty(FICL_DICT *pDict, unsigned nHash) 442{ 443 FICL_HASH *pHash; 444 445 pDict->here = pDict->dict; 446 447 dictAlign(pDict); 448 pHash = (FICL_HASH *)pDict->here; 449 dictAllot(pDict, 450 sizeof (FICL_HASH) + (nHash - 1) * sizeof (FICL_WORD *)); 451 452 pHash->size = nHash; 453 hashReset(pHash); 454 455 pDict->pForthWords = pHash; 456 pDict->smudge = NULL; 457 dictResetSearchOrder(pDict); 458 return; 459} 460 461 462/************************************************************************** 463 d i c t H a s h S u m m a r y 464** Calculate a figure of merit for the dictionary hash table based 465** on the average search depth for all the words in the dictionary, 466** assuming uniform distribution of target keys. The figure of merit 467** is the ratio of the total search depth for all keys in the table 468** versus a theoretical optimum that would be achieved if the keys 469** were distributed into the table as evenly as possible. 470** The figure would be worse if the hash table used an open 471** addressing scheme (i.e. collisions resolved by searching the 472** table for an empty slot) for a given size table. 473**************************************************************************/ 474#if FICL_WANT_FLOAT 475void dictHashSummary(FICL_VM *pVM) 476{ 477 FICL_DICT *dp = vmGetDict(pVM); 478 FICL_HASH *pFHash; 479 FICL_WORD **pHash; 480 unsigned size; 481 FICL_WORD *pFW; 482 unsigned i; 483 int nMax = 0; 484 int nWords = 0; 485 int nFilled; 486 double avg = 0.0; 487 double best; 488 int nAvg, nRem, nDepth; 489 490 dictCheck(dp, pVM, 0); 491 492 pFHash = dp->pSearch[dp->nLists - 1]; 493 pHash = pFHash->table; 494 size = pFHash->size; 495 nFilled = size; 496 497 for (i = 0; i < size; i++) 498 { 499 int n = 0; 500 pFW = pHash[i]; 501 502 while (pFW) 503 { 504 ++n; 505 ++nWords; 506 pFW = pFW->link; 507 } 508 509 avg += (double)(n * (n+1)) / 2.0; 510 511 if (n > nMax) 512 nMax = n; 513 if (n == 0) 514 --nFilled; 515 } 516 517 /* Calc actual avg search depth for this hash */ 518 avg = avg / nWords; 519 520 /* Calc best possible performance with this size hash */ 521 nAvg = nWords / size; 522 nRem = nWords % size; 523 nDepth = size * (nAvg * (nAvg+1))/2 + (nAvg+1)*nRem; 524 best = (double)nDepth/nWords; 525 526 sprintf(pVM->pad, 527 "%d bins, %2.0f%% filled, Depth: Max=%d, Avg=%2.1f, Best=%2.1f, Score: %2.0f%%", 528 size, 529 (double)nFilled * 100.0 / size, nMax, 530 avg, 531 best, 532 100.0 * best / avg); 533 534 ficlTextOut(pVM, pVM->pad, 1); 535 536 return; 537} 538#endif 539 540/************************************************************************** 541 d i c t I n c l u d e s 542** Returns TRUE iff the given pointer is within the address range of 543** the dictionary. 544**************************************************************************/ 545int dictIncludes(FICL_DICT *pDict, void *p) 546{ 547 return ((p >= (void *) &pDict->dict) 548 && (p < (void *)(&pDict->dict + pDict->size)) 549 ); 550} 551 552/************************************************************************** 553 d i c t L o o k u p 554** Find the FICL_WORD that matches the given name and length. 555** If found, returns the word's address. Otherwise returns NULL. 556** Uses the search order list to search multiple wordlists. 557**************************************************************************/ 558FICL_WORD *dictLookup(FICL_DICT *pDict, STRINGINFO si) 559{ 560 FICL_WORD *pFW = NULL; 561 FICL_HASH *pHash; 562 int i; 563 UNS16 hashCode = hashHashCode(si); 564 565 assert(pDict); 566 567 ficlLockDictionary(1); 568 569 for (i = (int)pDict->nLists - 1; (i >= 0) && (!pFW); --i) 570 { 571 pHash = pDict->pSearch[i]; 572 pFW = hashLookup(pHash, si, hashCode); 573 } 574 575 ficlLockDictionary(0); 576 return pFW; 577} 578 579 580/************************************************************************** 581 f i c l L o o k u p L o c 582** Same as dictLookup, but looks in system locals dictionary first... 583** Assumes locals dictionary has only one wordlist... 584**************************************************************************/ 585#if FICL_WANT_LOCALS 586FICL_WORD *ficlLookupLoc(FICL_SYSTEM *pSys, STRINGINFO si) 587{ 588 FICL_WORD *pFW = NULL; 589 FICL_DICT *pDict = pSys->dp; 590 FICL_HASH *pHash = ficlGetLoc(pSys)->pForthWords; 591 int i; 592 UNS16 hashCode = hashHashCode(si); 593 594 assert(pHash); 595 assert(pDict); 596 597 ficlLockDictionary(1); 598 /* 599 ** check the locals dict first... 600 */ 601 pFW = hashLookup(pHash, si, hashCode); 602 603 /* 604 ** If no joy, (!pFW) --------------------------v 605 ** iterate over the search list in the main dict 606 */ 607 for (i = (int)pDict->nLists - 1; (i >= 0) && (!pFW); --i) 608 { 609 pHash = pDict->pSearch[i]; 610 pFW = hashLookup(pHash, si, hashCode); 611 } 612 613 ficlLockDictionary(0); 614 return pFW; 615} 616#endif 617 618 619/************************************************************************** 620 d i c t R e s e t S e a r c h O r d e r 621** Initialize the dictionary search order list to sane state 622**************************************************************************/ 623void dictResetSearchOrder(FICL_DICT *pDict) 624{ 625 assert(pDict); 626 pDict->pCompile = pDict->pForthWords; 627 pDict->nLists = 1; 628 pDict->pSearch[0] = pDict->pForthWords; 629 return; 630} 631 632 633/************************************************************************** 634 d i c t S e t F l a g s 635** Changes the flags field of the most recently defined word: 636** Set all bits that are ones in the set parameter, clear all bits 637** that are ones in the clr parameter. Clear wins in case the same bit 638** is set in both parameters. 639**************************************************************************/ 640void dictSetFlags(FICL_DICT *pDict, UNS8 set, UNS8 clr) 641{ 642 assert(pDict->smudge); 643 pDict->smudge->flags |= set; 644 pDict->smudge->flags &= ~clr; 645 return; 646} 647 648 649/************************************************************************** 650 d i c t S e t I m m e d i a t e 651** Set the most recently defined word as IMMEDIATE 652**************************************************************************/ 653void dictSetImmediate(FICL_DICT *pDict) 654{ 655 assert(pDict->smudge); 656 pDict->smudge->flags |= FW_IMMEDIATE; 657 return; 658} 659 660 661/************************************************************************** 662 d i c t U n s m u d g e 663** Completes the definition of a word by linking it 664** into the main list 665**************************************************************************/ 666void dictUnsmudge(FICL_DICT *pDict) 667{ 668 FICL_WORD *pFW = pDict->smudge; 669 FICL_HASH *pHash = pDict->pCompile; 670 671 assert(pHash); 672 assert(pFW); 673 /* 674 ** :noname words never get linked into the list... 675 */ 676 if (pFW->nName > 0) 677 hashInsertWord(pHash, pFW); 678 pFW->flags &= ~(FW_SMUDGE); 679 return; 680} 681 682 683/************************************************************************** 684 d i c t W h e r e 685** Returns the value of the HERE pointer -- the address 686** of the next free cell in the dictionary 687**************************************************************************/ 688CELL *dictWhere(FICL_DICT *pDict) 689{ 690 return pDict->here; 691} 692 693 694/************************************************************************** 695 h a s h F o r g e t 696** Unlink all words in the hash that have addresses greater than or 697** equal to the address supplied. Implementation factor for FORGET 698** and MARKER. 699**************************************************************************/ 700void hashForget(FICL_HASH *pHash, void *where) 701{ 702 FICL_WORD *pWord; 703 unsigned i; 704 705 assert(pHash); 706 assert(where); 707 708 for (i = 0; i < pHash->size; i++) 709 { 710 pWord = pHash->table[i]; 711 712 while ((void *)pWord >= where) 713 { 714 pWord = pWord->link; 715 } 716 717 pHash->table[i] = pWord; 718 } 719 720 return; 721} 722 723 724/************************************************************************** 725 h a s h H a s h C o d e 726** 727** Generate a 16 bit hashcode from a character string using a rolling 728** shift and add stolen from PJ Weinberger of Bell Labs fame. Case folds 729** the name before hashing it... 730** N O T E : If string has zero length, returns zero. 731**************************************************************************/ 732UNS16 hashHashCode(STRINGINFO si) 733{ 734 /* hashPJW */ 735 UNS8 *cp; 736 UNS16 code = (UNS16)si.count; 737 UNS16 shift = 0; 738 739 if (si.count == 0) 740 return 0; 741 742 /* changed to run without errors under Purify -- lch */ 743 for (cp = (UNS8 *)si.cp; si.count && *cp; cp++, si.count--) 744 { 745 code = (UNS16)((code << 4) + tolower(*cp)); 746 shift = (UNS16)(code & 0xf000); 747 if (shift) 748 { 749 code ^= (UNS16)(shift >> 8); 750 code ^= (UNS16)shift; 751 } 752 } 753 754 return (UNS16)code; 755} 756 757 758 759 760/************************************************************************** 761 h a s h I n s e r t W o r d 762** Put a word into the hash table using the word's hashcode as 763** an index (modulo the table size). 764**************************************************************************/ 765void hashInsertWord(FICL_HASH *pHash, FICL_WORD *pFW) 766{ 767 FICL_WORD **pList; 768 769 assert(pHash); 770 assert(pFW); 771 772 if (pHash->size == 1) 773 { 774 pList = pHash->table; 775 } 776 else 777 { 778 pList = pHash->table + (pFW->hash % pHash->size); 779 } 780 781 pFW->link = *pList; 782 *pList = pFW; 783 return; 784} 785 786 787/************************************************************************** 788 h a s h L o o k u p 789** Find a name in the hash table given the hashcode and text of the name. 790** Returns the address of the corresponding FICL_WORD if found, 791** otherwise NULL. 792** Note: outer loop on link field supports inheritance in wordlists. 793** It's not part of ANS Forth - ficl only. hashReset creates wordlists 794** with NULL link fields. 795**************************************************************************/ 796FICL_WORD *hashLookup(FICL_HASH *pHash, STRINGINFO si, UNS16 hashCode) 797{ 798 FICL_UNS nCmp = si.count; 799 FICL_WORD *pFW; 800 UNS16 hashIdx; 801 802 if (nCmp > nFICLNAME) 803 nCmp = nFICLNAME; 804 805 for (; pHash != NULL; pHash = pHash->link) 806 { 807 if (pHash->size > 1) 808 hashIdx = (UNS16)(hashCode % pHash->size); 809 else /* avoid the modulo op for single threaded lists */ 810 hashIdx = 0; 811 812 for (pFW = pHash->table[hashIdx]; pFW; pFW = pFW->link) 813 { 814 if ( (pFW->nName == si.count) 815 && (!strincmp(si.cp, pFW->name, nCmp)) ) 816 return pFW; 817#if FICL_ROBUST 818 assert(pFW != pFW->link); 819#endif 820 } 821 } 822 823 return NULL; 824} 825 826 827/************************************************************************** 828 h a s h R e s e t 829** Initialize a FICL_HASH to empty state. 830**************************************************************************/ 831void hashReset(FICL_HASH *pHash) 832{ 833 unsigned i; 834 835 assert(pHash); 836 837 for (i = 0; i < pHash->size; i++) 838 { 839 pHash->table[i] = NULL; 840 } 841 842 pHash->link = NULL; 843 pHash->name = NULL; 844 return; 845} 846 847/************************************************************************** 848 d i c t C h e c k T h r e s h o l d 849** Verify if an increase in the dictionary size is warranted, and do it if 850** so. 851**************************************************************************/ 852 853void dictCheckThreshold(FICL_DICT* dp) 854{ 855 if( dictCellsAvail(dp) < dictThreshold.u ) { 856 dp->dict = ficlMalloc( dictIncrease.u * sizeof (CELL) ); 857 assert(dp->dict); 858 dp->here = dp->dict; 859 dp->size = dictIncrease.u; 860 dictAlign(dp); 861 } 862} 863 864