| dict.c (77443) | dict.c (94290) |
|---|---|
| 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 | 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.6 2000-06-17 07:43:44-07 jsadler Exp jsadler $ | 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** | 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** |
|
| 25** L I C E N S E and D I S C L A I M E R 26** 27** Redistribution and use in source and binary forms, with or without 28** modification, are permitted provided that the following conditions 29** are met: 30** 1. Redistributions of source code must retain the above copyright 31** notice, this list of conditions and the following disclaimer. 32** 2. Redistributions in binary form must reproduce the above copyright --- 6 unchanged lines hidden (view full) --- 39** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 40** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 41** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 42** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 43** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 44** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 45** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 46** SUCH DAMAGE. | 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 --- 6 unchanged lines hidden (view full) --- 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. |
| 47** 48** I am interested in hearing from anyone who uses ficl. If you have 49** a problem, a success story, a defect, an enhancement request, or 50** if you would like to contribute to the ficl release, please send 51** contact me by email at the address above. 52** 53** $Id: dict.c,v 1.8 2001-04-26 21:41:45-07 jsadler Exp jsadler $ | |
| 54*/ 55 | 52*/ 53 |
| 56/* $FreeBSD: head/sys/boot/ficl/dict.c 77443 2001-05-29 23:44:12Z dcs $ */ | 54/* $FreeBSD: head/sys/boot/ficl/dict.c 94290 2002-04-09 17:45:28Z dcs $ */ |
| 57 58#ifdef TESTMAIN 59#include <stdio.h> | 55 56#ifdef TESTMAIN 57#include <stdio.h> |
| 60#include <stdlib.h> | |
| 61#include <ctype.h> 62#else 63#include <stand.h> 64#endif 65#include <string.h> 66#include "ficl.h" 67 68/* Dictionary on-demand resizing control variables */ --- 230 unchanged lines hidden (view full) --- 299{ 300 return pDict->here - pDict->dict; 301} 302 303 304/************************************************************************** 305 d i c t C h e c k 306** Checks the dictionary for corruption and throws appropriate | 58#include <ctype.h> 59#else 60#include <stand.h> 61#endif 62#include <string.h> 63#include "ficl.h" 64 65/* Dictionary on-demand resizing control variables */ --- 230 unchanged lines hidden (view full) --- 296{ 297 return pDict->here - pDict->dict; 298} 299 300 301/************************************************************************** 302 d i c t C h e c k 303** Checks the dictionary for corruption and throws appropriate |
| 307** errors | 304** errors. 305** Input: +n number of ADDRESS UNITS (not Cells) proposed to allot 306** -n number of ADDRESS UNITS proposed to de-allot 307** 0 just do a consistency check |
| 308**************************************************************************/ | 308**************************************************************************/ |
| 309void dictCheck(FICL_DICT *pDict, FICL_VM *pVM, int nCells) | 309void dictCheck(FICL_DICT *pDict, FICL_VM *pVM, int n) |
| 310{ | 310{ |
| 311 if ((nCells >= 0) && (dictCellsAvail(pDict) < nCells)) | 311 if ((n >= 0) && (dictCellsAvail(pDict) * (int)sizeof(CELL) < n)) |
| 312 { 313 vmThrowErr(pVM, "Error: dictionary full"); 314 } 315 | 312 { 313 vmThrowErr(pVM, "Error: dictionary full"); 314 } 315 |
| 316 if ((nCells <= 0) && (dictCellsUsed(pDict) < -nCells)) | 316 if ((n <= 0) && (dictCellsUsed(pDict) * (int)sizeof(CELL) < -n)) |
| 317 { 318 vmThrowErr(pVM, "Error: dictionary underflow"); 319 } 320 321 if (pDict->nLists > FICL_DEFAULT_VOCS) 322 { 323 dictResetSearchOrder(pDict); 324 vmThrowErr(pVM, "Error: search order overflow"); --- 66 unchanged lines hidden (view full) --- 391 nAlloc = sizeof (FICL_HASH) + nCells * sizeof (CELL) 392 + (nHash - 1) * sizeof (FICL_WORD *); 393 394 pDict = ficlMalloc(sizeof (FICL_DICT)); 395 assert(pDict); 396 memset(pDict, 0, sizeof (FICL_DICT)); 397 pDict->dict = ficlMalloc(nAlloc); 398 assert(pDict->dict); | 317 { 318 vmThrowErr(pVM, "Error: dictionary underflow"); 319 } 320 321 if (pDict->nLists > FICL_DEFAULT_VOCS) 322 { 323 dictResetSearchOrder(pDict); 324 vmThrowErr(pVM, "Error: search order overflow"); --- 66 unchanged lines hidden (view full) --- 391 nAlloc = sizeof (FICL_HASH) + nCells * sizeof (CELL) 392 + (nHash - 1) * sizeof (FICL_WORD *); 393 394 pDict = ficlMalloc(sizeof (FICL_DICT)); 395 assert(pDict); 396 memset(pDict, 0, sizeof (FICL_DICT)); 397 pDict->dict = ficlMalloc(nAlloc); 398 assert(pDict->dict); |
| 399 |
|
| 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 --- 48 unchanged lines hidden (view full) --- 455 pDict->pForthWords = pHash; 456 pDict->smudge = NULL; 457 dictResetSearchOrder(pDict); 458 return; 459} 460 461 462/************************************************************************** | 400 pDict->size = nCells; 401 dictEmpty(pDict, nHash); 402 return pDict; 403} 404 405 406/************************************************************************** 407 d i c t C r e a t e W o r d l i s t --- 48 unchanged lines hidden (view full) --- 456 pDict->pForthWords = pHash; 457 pDict->smudge = NULL; 458 dictResetSearchOrder(pDict); 459 return; 460} 461 462 463/************************************************************************** |
| 464 d i c t H a s h S u m m a r y 465** Calculate a figure of merit for the dictionary hash table based 466** on the average search depth for all the words in the dictionary, 467** assuming uniform distribution of target keys. The figure of merit 468** is the ratio of the total search depth for all keys in the table 469** versus a theoretical optimum that would be achieved if the keys 470** were distributed into the table as evenly as possible. 471** The figure would be worse if the hash table used an open 472** addressing scheme (i.e. collisions resolved by searching the 473** table for an empty slot) for a given size table. 474**************************************************************************/ 475#if FICL_WANT_FLOAT 476void dictHashSummary(FICL_VM *pVM) 477{ 478 FICL_DICT *dp = vmGetDict(pVM); 479 FICL_HASH *pFHash; 480 FICL_WORD **pHash; 481 unsigned size; 482 FICL_WORD *pFW; 483 unsigned i; 484 int nMax = 0; 485 int nWords = 0; 486 int nFilled; 487 double avg = 0.0; 488 double best; 489 int nAvg, nRem, nDepth; 490 491 dictCheck(dp, pVM, 0); 492 493 pFHash = dp->pSearch[dp->nLists - 1]; 494 pHash = pFHash->table; 495 size = pFHash->size; 496 nFilled = size; 497 498 for (i = 0; i < size; i++) 499 { 500 int n = 0; 501 pFW = pHash[i]; 502 503 while (pFW) 504 { 505 ++n; 506 ++nWords; 507 pFW = pFW->link; 508 } 509 510 avg += (double)(n * (n+1)) / 2.0; 511 512 if (n > nMax) 513 nMax = n; 514 if (n == 0) 515 --nFilled; 516 } 517 518 /* Calc actual avg search depth for this hash */ 519 avg = avg / nWords; 520 521 /* Calc best possible performance with this size hash */ 522 nAvg = nWords / size; 523 nRem = nWords % size; 524 nDepth = size * (nAvg * (nAvg+1))/2 + (nAvg+1)*nRem; 525 best = (double)nDepth/nWords; 526 527 sprintf(pVM->pad, 528 "%d bins, %2.0f%% filled, Depth: Max=%d, Avg=%2.1f, Best=%2.1f, Score: %2.0f%%", 529 size, 530 (double)nFilled * 100.0 / size, nMax, 531 avg, 532 best, 533 100.0 * best / avg); 534 535 ficlTextOut(pVM, pVM->pad, 1); 536 537 return; 538} 539#endif 540 541/************************************************************************** |
|
| 463 d i c t I n c l u d e s 464** Returns TRUE iff the given pointer is within the address range of 465** the dictionary. 466**************************************************************************/ 467int dictIncludes(FICL_DICT *pDict, void *p) 468{ 469 return ((p >= (void *) &pDict->dict) 470 && (p < (void *)(&pDict->dict + pDict->size)) 471 ); 472} 473 | 542 d i c t I n c l u d e s 543** Returns TRUE iff the given pointer is within the address range of 544** the dictionary. 545**************************************************************************/ 546int dictIncludes(FICL_DICT *pDict, void *p) 547{ 548 return ((p >= (void *) &pDict->dict) 549 && (p < (void *)(&pDict->dict + pDict->size)) 550 ); 551} 552 |
| 474 | |
| 475/************************************************************************** 476 d i c t L o o k u p 477** Find the FICL_WORD that matches the given name and length. 478** If found, returns the word's address. Otherwise returns NULL. 479** Uses the search order list to search multiple wordlists. 480**************************************************************************/ 481FICL_WORD *dictLookup(FICL_DICT *pDict, STRINGINFO si) 482{ --- 13 unchanged lines hidden (view full) --- 496 } 497 498 ficlLockDictionary(0); 499 return pFW; 500} 501 502 503/************************************************************************** | 553/************************************************************************** 554 d i c t L o o k u p 555** Find the FICL_WORD that matches the given name and length. 556** If found, returns the word's address. Otherwise returns NULL. 557** Uses the search order list to search multiple wordlists. 558**************************************************************************/ 559FICL_WORD *dictLookup(FICL_DICT *pDict, STRINGINFO si) 560{ --- 13 unchanged lines hidden (view full) --- 574 } 575 576 ficlLockDictionary(0); 577 return pFW; 578} 579 580 581/************************************************************************** |
| 504 d i c t L o o k u p L o c | 582 f i c l L o o k u p L o c |
| 505** Same as dictLookup, but looks in system locals dictionary first... 506** Assumes locals dictionary has only one wordlist... 507**************************************************************************/ 508#if FICL_WANT_LOCALS | 583** Same as dictLookup, but looks in system locals dictionary first... 584** Assumes locals dictionary has only one wordlist... 585**************************************************************************/ 586#if FICL_WANT_LOCALS |
| 509FICL_WORD *dictLookupLoc(FICL_DICT *pDict, STRINGINFO si) | 587FICL_WORD *ficlLookupLoc(FICL_SYSTEM *pSys, STRINGINFO si) |
| 510{ 511 FICL_WORD *pFW = NULL; | 588{ 589 FICL_WORD *pFW = NULL; |
| 512 FICL_HASH *pHash = ficlGetLoc()->pForthWords; | 590 FICL_DICT *pDict = pSys->dp; 591 FICL_HASH *pHash = ficlGetLoc(pSys)->pForthWords; |
| 513 int i; 514 UNS16 hashCode = hashHashCode(si); 515 516 assert(pHash); 517 assert(pDict); 518 519 ficlLockDictionary(1); 520 /* --- 265 unchanged lines hidden --- | 592 int i; 593 UNS16 hashCode = hashHashCode(si); 594 595 assert(pHash); 596 assert(pDict); 597 598 ficlLockDictionary(1); 599 /* --- 265 unchanged lines hidden --- |