From 156d925f39c0caaf6f3ca1c03e22314a3027edeb Mon Sep 17 00:00:00 2001 From: "Arnold D. Robbins" Date: Sun, 21 Mar 2021 11:34:51 +0200 Subject: Add FNV1-A hash function support. --- ChangeLog | 6 + NEWS | 3 + doc/ChangeLog | 5 + doc/gawk.info | 1098 ++++++++++++++++++++++++++++--------------------------- doc/gawk.texi | 5 +- doc/gawktexi.in | 5 +- str_array.c | 38 +- 7 files changed, 608 insertions(+), 552 deletions(-) diff --git a/ChangeLog b/ChangeLog index 89767c0f..56deef6b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2021-03-21 Arnold D. Robbins + + * str_array.c (fnv1a_hash_string): New function. + (str_array_init): Use fnv1a_hash_string if AWK_HASH env var + set to "fnv1a". + 2021-02-13 Arnold D. Robbins * io.c (nextfile): Use the value of ARGC directly in the for diff --git a/NEWS b/NEWS index 65f25a2d..85062216 100644 --- a/NEWS +++ b/NEWS @@ -12,6 +12,9 @@ operators. Comparison order for sorting has not changed. This only makes a difference when comparing Infinity and NaN values with regular numbers; it should not be noticeable most of the time. +2. If the AWK_HASH environment variable is set to "fnv1a" gawk will +use the FNV1-A hash function for associative arrays. + Changes from 5.1.0 to 5.1.1 --------------------------- diff --git a/doc/ChangeLog b/doc/ChangeLog index 36abffc0..3dd82e08 100644 --- a/doc/ChangeLog +++ b/doc/ChangeLog @@ -1,3 +1,8 @@ +2021-03-21 Arnold D. Robbins + + * gawktexi.in (Other Environment Variables): Document "fnv1a" + possible value for AWK_HASH environment variable. + 2021-03-18 Arnold D. Robbins * texinfo.tex: Updated from GNULIB. diff --git a/doc/gawk.info b/doc/gawk.info index fd56f412..445d06dd 100644 --- a/doc/gawk.info +++ b/doc/gawk.info @@ -3216,7 +3216,9 @@ change. The variables are: 'AWK_HASH' If this variable exists with a value of 'gst', 'gawk' switches to using the hash function from GNU Smalltalk for managing arrays. - This function may be marginally faster than the standard function. + With a value of 'fnv1a', 'gawk' uses the FNV1-A hash function + (http://www.isthe.com/chongo/tech/comp/fnv/index.html). These + functions may be marginally faster than the standard function. 'AWKREADFUNC' If this variable exists, 'gawk' switches to reading source files @@ -38122,553 +38124,553 @@ Ref: AWKPATH Variable-Footnote-2147851 Node: AWKLIBPATH Variable148222 Ref: AWKLIBPATH Variable-Footnote-1149919 Node: Other Environment Variables150294 -Node: Exit Status154115 -Node: Include Files154792 -Node: Loading Shared Libraries158482 -Node: Obsolete159910 -Node: Undocumented160602 -Node: Invoking Summary160899 -Node: Regexp163740 -Node: Regexp Usage165194 -Node: Escape Sequences167231 -Node: Regexp Operators173472 -Node: Regexp Operator Details173957 -Ref: Regexp Operator Details-Footnote-1180389 -Node: Interval Expressions180536 -Ref: Interval Expressions-Footnote-1181957 -Node: Bracket Expressions182055 -Ref: table-char-classes184531 -Node: Leftmost Longest187857 -Node: Computed Regexps189160 -Node: GNU Regexp Operators192587 -Node: Case-sensitivity196324 -Ref: Case-sensitivity-Footnote-1199190 -Ref: Case-sensitivity-Footnote-2199425 -Node: Regexp Summary199533 -Node: Reading Files200999 -Node: Records203268 -Node: awk split records204343 -Node: gawk split records209043 -Ref: gawk split records-Footnote-1214117 -Node: Fields214154 -Node: Nonconstant Fields216895 -Ref: Nonconstant Fields-Footnote-1219131 -Node: Changing Fields219335 -Node: Field Separators225366 -Node: Default Field Splitting228064 -Node: Regexp Field Splitting229182 -Node: Single Character Fields232859 -Node: Command Line Field Separator233919 -Node: Full Line Fields237137 -Ref: Full Line Fields-Footnote-1238659 -Ref: Full Line Fields-Footnote-2238705 -Node: Field Splitting Summary238806 -Node: Constant Size240880 -Node: Fixed width data241612 -Node: Skipping intervening245079 -Node: Allowing trailing data245877 -Node: Fields with fixed data246914 -Node: Splitting By Content248432 -Ref: Splitting By Content-Footnote-1252215 -Node: More CSV252378 -Node: Testing field creation253970 -Node: Multiple Line255595 -Node: Getline261872 -Node: Plain Getline264341 -Node: Getline/Variable266914 -Node: Getline/File268065 -Node: Getline/Variable/File269453 -Ref: Getline/Variable/File-Footnote-1271058 -Node: Getline/Pipe271146 -Node: Getline/Variable/Pipe273850 -Node: Getline/Coprocess274985 -Node: Getline/Variable/Coprocess276252 -Node: Getline Notes276994 -Node: Getline Summary279791 -Ref: table-getline-variants280215 -Node: Read Timeout280963 -Ref: Read Timeout-Footnote-1284869 -Node: Retrying Input284927 -Node: Command-line directories286126 -Node: Input Summary287032 -Node: Input Exercises290204 -Node: Printing290638 -Node: Print292472 -Node: Print Examples293929 -Node: Output Separators296709 -Node: OFMT298726 -Node: Printf300082 -Node: Basic Printf300867 -Node: Control Letters302441 -Node: Format Modifiers307603 -Node: Printf Examples313618 -Node: Redirection316104 -Node: Special FD322945 -Ref: Special FD-Footnote-1326113 -Node: Special Files326187 -Node: Other Inherited Files326804 -Node: Special Network327805 -Node: Special Caveats328665 -Node: Close Files And Pipes329614 -Ref: table-close-pipe-return-values336521 -Ref: Close Files And Pipes-Footnote-1337334 -Ref: Close Files And Pipes-Footnote-2337482 -Node: Nonfatal337634 -Node: Output Summary339972 -Node: Output Exercises341194 -Node: Expressions341873 -Node: Values343061 -Node: Constants343739 -Node: Scalar Constants344430 -Ref: Scalar Constants-Footnote-1346940 -Node: Nondecimal-numbers347190 -Node: Regexp Constants350191 -Node: Using Constant Regexps350717 -Node: Standard Regexp Constants351339 -Node: Strong Regexp Constants354527 -Node: Variables357539 -Node: Using Variables358196 -Node: Assignment Options360106 -Node: Conversion362577 -Node: Strings And Numbers363101 -Ref: Strings And Numbers-Footnote-1366164 -Node: Locale influences conversions366273 -Ref: table-locale-affects369031 -Node: All Operators369649 -Node: Arithmetic Ops370278 -Node: Concatenation372994 -Ref: Concatenation-Footnote-1375841 -Node: Assignment Ops375948 -Ref: table-assign-ops380939 -Node: Increment Ops382252 -Node: Truth Values and Conditions385712 -Node: Truth Values386786 -Node: Typing and Comparison387834 -Node: Variable Typing388654 -Ref: Variable Typing-Footnote-1395117 -Ref: Variable Typing-Footnote-2395189 -Node: Comparison Operators395266 -Ref: table-relational-ops395685 -Node: POSIX String Comparison399180 -Ref: POSIX String Comparison-Footnote-1400875 -Ref: POSIX String Comparison-Footnote-2401014 -Node: Boolean Ops401098 -Ref: Boolean Ops-Footnote-1405580 -Node: Conditional Exp405672 -Node: Function Calls407408 -Node: Precedence411285 -Node: Locales414944 -Node: Expressions Summary416576 -Node: Patterns and Actions419149 -Node: Pattern Overview420269 -Node: Regexp Patterns421946 -Node: Expression Patterns422488 -Node: Ranges426269 -Node: BEGIN/END429377 -Node: Using BEGIN/END430138 -Ref: Using BEGIN/END-Footnote-1432892 -Node: I/O And BEGIN/END432998 -Node: BEGINFILE/ENDFILE435311 -Node: Empty438542 -Node: Using Shell Variables438859 -Node: Action Overview441133 -Node: Statements443458 -Node: If Statement445306 -Node: While Statement446801 -Node: Do Statement448829 -Node: For Statement449977 -Node: Switch Statement453148 -Node: Break Statement455589 -Node: Continue Statement457681 -Node: Next Statement459508 -Node: Nextfile Statement461891 -Node: Exit Statement464580 -Node: Built-in Variables466983 -Node: User-modified468116 -Node: Auto-set475883 -Ref: Auto-set-Footnote-1492690 -Ref: Auto-set-Footnote-2492896 -Node: ARGC and ARGV492952 -Node: Pattern Action Summary497165 -Node: Arrays499595 -Node: Array Basics500924 -Node: Array Intro501768 -Ref: figure-array-elements503743 -Ref: Array Intro-Footnote-1506447 -Node: Reference to Elements506575 -Node: Assigning Elements509039 -Node: Array Example509530 -Node: Scanning an Array511289 -Node: Controlling Scanning514311 -Ref: Controlling Scanning-Footnote-1520767 -Node: Numeric Array Subscripts521083 -Node: Uninitialized Subscripts523267 -Node: Delete524886 -Ref: Delete-Footnote-1527638 -Node: Multidimensional527695 -Node: Multiscanning530790 -Node: Arrays of Arrays532381 -Node: Arrays Summary537149 -Node: Functions539242 -Node: Built-in540280 -Node: Calling Built-in541361 -Node: Numeric Functions543357 -Ref: Numeric Functions-Footnote-1547383 -Ref: Numeric Functions-Footnote-2548031 -Ref: Numeric Functions-Footnote-3548079 -Node: String Functions548351 -Ref: String Functions-Footnote-1572492 -Ref: String Functions-Footnote-2572620 -Ref: String Functions-Footnote-3572868 -Node: Gory Details572955 -Ref: table-sub-escapes574746 -Ref: table-sub-proposed576265 -Ref: table-posix-sub577628 -Ref: table-gensub-escapes579169 -Ref: Gory Details-Footnote-1579992 -Node: I/O Functions580146 -Ref: table-system-return-values586600 -Ref: I/O Functions-Footnote-1588680 -Ref: I/O Functions-Footnote-2588828 -Node: Time Functions588948 -Ref: Time Functions-Footnote-1599619 -Ref: Time Functions-Footnote-2599687 -Ref: Time Functions-Footnote-3599845 -Ref: Time Functions-Footnote-4599956 -Ref: Time Functions-Footnote-5600068 -Ref: Time Functions-Footnote-6600295 -Node: Bitwise Functions600561 -Ref: table-bitwise-ops601155 -Ref: Bitwise Functions-Footnote-1607218 -Ref: Bitwise Functions-Footnote-2607391 -Node: Type Functions607582 -Node: I18N Functions610445 -Node: User-defined612096 -Node: Definition Syntax612908 -Ref: Definition Syntax-Footnote-1618602 -Node: Function Example618673 -Ref: Function Example-Footnote-1621595 -Node: Function Calling621617 -Node: Calling A Function622205 -Node: Variable Scope623163 -Node: Pass By Value/Reference626157 -Node: Function Caveats628801 -Ref: Function Caveats-Footnote-1630848 -Node: Return Statement630968 -Node: Dynamic Typing633947 -Node: Indirect Calls634877 -Ref: Indirect Calls-Footnote-1645129 -Node: Functions Summary645257 -Node: Library Functions647962 -Ref: Library Functions-Footnote-1651569 -Ref: Library Functions-Footnote-2651712 -Node: Library Names651883 -Ref: Library Names-Footnote-1655550 -Ref: Library Names-Footnote-2655773 -Node: General Functions655859 -Node: Strtonum Function656962 -Node: Assert Function659984 -Node: Round Function663310 -Node: Cliff Random Function664850 -Node: Ordinal Functions665866 -Ref: Ordinal Functions-Footnote-1668929 -Ref: Ordinal Functions-Footnote-2669181 -Node: Join Function669391 -Ref: Join Function-Footnote-1671161 -Node: Getlocaltime Function671361 -Node: Readfile Function675103 -Node: Shell Quoting677080 -Node: Data File Management678481 -Node: Filetrans Function679113 -Node: Rewind Function683209 -Node: File Checking685118 -Ref: File Checking-Footnote-1686452 -Node: Empty Files686653 -Node: Ignoring Assigns688632 -Node: Getopt Function690182 -Ref: Getopt Function-Footnote-1705393 -Node: Passwd Functions705593 -Ref: Passwd Functions-Footnote-1714432 -Node: Group Functions714520 -Ref: Group Functions-Footnote-1722418 -Node: Walking Arrays722625 -Node: Library Functions Summary725633 -Node: Library Exercises727039 -Node: Sample Programs727504 -Node: Running Examples728274 -Node: Clones729002 -Node: Cut Program730226 -Node: Egrep Program740366 -Node: Id Program749367 -Node: Split Program759314 -Ref: Split Program-Footnote-1769204 -Node: Tee Program769377 -Node: Uniq Program772167 -Node: Wc Program779755 -Node: Bytes vs. Characters780152 -Node: Using extensions781700 -Node: wc program782454 -Node: Miscellaneous Programs787319 -Node: Dupword Program788532 -Node: Alarm Program790562 -Node: Translate Program795417 -Ref: Translate Program-Footnote-1799982 -Node: Labels Program800252 -Ref: Labels Program-Footnote-1803603 -Node: Word Sorting803687 -Node: History Sorting807759 -Node: Extract Program809984 -Node: Simple Sed818038 -Node: Igawk Program821112 -Ref: Igawk Program-Footnote-1835443 -Ref: Igawk Program-Footnote-2835645 -Ref: Igawk Program-Footnote-3835767 -Node: Anagram Program835882 -Node: Signature Program838944 -Node: Programs Summary840191 -Node: Programs Exercises841405 -Ref: Programs Exercises-Footnote-1845535 -Node: Advanced Features845621 -Node: Nondecimal Data847688 -Node: Array Sorting849279 -Node: Controlling Array Traversal849979 -Ref: Controlling Array Traversal-Footnote-1858347 -Node: Array Sorting Functions858465 -Ref: Array Sorting Functions-Footnote-1863556 -Node: Two-way I/O863752 -Ref: Two-way I/O-Footnote-1871473 -Ref: Two-way I/O-Footnote-2871660 -Node: TCP/IP Networking871742 -Node: Profiling874860 -Node: Extension Philosophy884169 -Node: Advanced Features Summary885648 -Node: Internationalization887663 -Node: I18N and L10N889143 -Node: Explaining gettext889830 -Ref: Explaining gettext-Footnote-1895722 -Ref: Explaining gettext-Footnote-2895907 -Node: Programmer i18n896072 -Ref: Programmer i18n-Footnote-1901021 -Node: Translator i18n901070 -Node: String Extraction901864 -Ref: String Extraction-Footnote-1902996 -Node: Printf Ordering903082 -Ref: Printf Ordering-Footnote-1905868 -Node: I18N Portability905932 -Ref: I18N Portability-Footnote-1908388 -Node: I18N Example908451 -Ref: I18N Example-Footnote-1911726 -Ref: I18N Example-Footnote-2911799 -Node: Gawk I18N911908 -Node: I18N Summary912557 -Node: Debugger913898 -Node: Debugging914898 -Node: Debugging Concepts915339 -Node: Debugging Terms917148 -Node: Awk Debugging919723 -Ref: Awk Debugging-Footnote-1920668 -Node: Sample Debugging Session920800 -Node: Debugger Invocation921334 -Node: Finding The Bug922720 -Node: List of Debugger Commands929194 -Node: Breakpoint Control930527 -Node: Debugger Execution Control934221 -Node: Viewing And Changing Data937583 -Node: Execution Stack941124 -Node: Debugger Info942761 -Node: Miscellaneous Debugger Commands946832 -Node: Readline Support951894 -Node: Limitations952790 -Node: Debugging Summary955344 -Node: Namespaces956623 -Node: Global Namespace957734 -Node: Qualified Names959132 -Node: Default Namespace960131 -Node: Changing The Namespace960872 -Node: Naming Rules962486 -Node: Internal Name Management964334 -Node: Namespace Example965376 -Node: Namespace And Features967938 -Node: Namespace Summary969373 -Node: Arbitrary Precision Arithmetic970850 -Node: Computer Arithmetic972337 -Ref: table-numeric-ranges976103 -Ref: table-floating-point-ranges976596 -Ref: Computer Arithmetic-Footnote-1977254 -Node: Math Definitions977311 -Ref: table-ieee-formats980287 -Node: MPFR features980854 -Node: FP Math Caution982572 -Ref: FP Math Caution-Footnote-1983644 -Node: Inexactness of computations984013 -Node: Inexact representation985044 -Node: Comparing FP Values986404 -Node: Errors accumulate987645 -Node: Strange values989101 -Ref: Strange values-Footnote-1991689 -Node: Getting Accuracy991794 -Node: Try To Round994504 -Node: Setting precision995403 -Ref: table-predefined-precision-strings996100 -Node: Setting the rounding mode997930 -Ref: table-gawk-rounding-modes998304 -Ref: Setting the rounding mode-Footnote-11002235 -Node: Arbitrary Precision Integers1002414 -Ref: Arbitrary Precision Integers-Footnote-11005589 -Node: Checking for MPFR1005738 -Node: POSIX Floating Point Problems1007212 -Ref: POSIX Floating Point Problems-Footnote-11011497 -Node: Floating point summary1011535 -Node: Dynamic Extensions1013725 -Node: Extension Intro1015278 -Node: Plugin License1016544 -Node: Extension Mechanism Outline1017341 -Ref: figure-load-extension1017780 -Ref: figure-register-new-function1019345 -Ref: figure-call-new-function1020437 -Node: Extension API Description1022499 -Node: Extension API Functions Introduction1024212 -Ref: table-api-std-headers1026048 -Node: General Data Types1030297 -Ref: General Data Types-Footnote-11038927 -Node: Memory Allocation Functions1039226 -Ref: Memory Allocation Functions-Footnote-11043727 -Node: Constructor Functions1043826 -Node: API Ownership of MPFR and GMP Values1047292 -Node: Registration Functions1048605 -Node: Extension Functions1049305 -Node: Exit Callback Functions1054627 -Node: Extension Version String1055877 -Node: Input Parsers1056540 -Node: Output Wrappers1069261 -Node: Two-way processors1073773 -Node: Printing Messages1076038 -Ref: Printing Messages-Footnote-11077209 -Node: Updating ERRNO1077362 -Node: Requesting Values1078101 -Ref: table-value-types-returned1078838 -Node: Accessing Parameters1079774 -Node: Symbol Table Access1081011 -Node: Symbol table by name1081523 -Ref: Symbol table by name-Footnote-11084547 -Node: Symbol table by cookie1084675 -Ref: Symbol table by cookie-Footnote-11088860 -Node: Cached values1088924 -Ref: Cached values-Footnote-11092460 -Node: Array Manipulation1092613 -Ref: Array Manipulation-Footnote-11093704 -Node: Array Data Types1093741 -Ref: Array Data Types-Footnote-11096399 -Node: Array Functions1096491 -Node: Flattening Arrays1100989 -Node: Creating Arrays1107965 -Node: Redirection API1112732 -Node: Extension API Variables1115565 -Node: Extension Versioning1116276 -Ref: gawk-api-version1116705 -Node: Extension GMP/MPFR Versioning1118436 -Node: Extension API Informational Variables1120064 -Node: Extension API Boilerplate1121137 -Node: Changes from API V11125111 -Node: Finding Extensions1126683 -Node: Extension Example1127242 -Node: Internal File Description1128040 -Node: Internal File Ops1132120 -Ref: Internal File Ops-Footnote-11143470 -Node: Using Internal File Ops1143610 -Ref: Using Internal File Ops-Footnote-11145993 -Node: Extension Samples1146267 -Node: Extension Sample File Functions1147796 -Node: Extension Sample Fnmatch1155445 -Node: Extension Sample Fork1156932 -Node: Extension Sample Inplace1158150 -Node: Extension Sample Ord1161776 -Node: Extension Sample Readdir1162612 -Ref: table-readdir-file-types1163501 -Node: Extension Sample Revout1164568 -Node: Extension Sample Rev2way1165157 -Node: Extension Sample Read write array1165897 -Node: Extension Sample Readfile1167839 -Node: Extension Sample Time1168934 -Node: Extension Sample API Tests1170686 -Node: gawkextlib1171178 -Node: Extension summary1174096 -Node: Extension Exercises1177798 -Node: Language History1179040 -Node: V7/SVR3.11180696 -Node: SVR41182848 -Node: POSIX1184282 -Node: BTL1185663 -Node: POSIX/GNU1186392 -Node: Feature History1192170 -Node: Common Extensions1208489 -Node: Ranges and Locales1209772 -Ref: Ranges and Locales-Footnote-11214388 -Ref: Ranges and Locales-Footnote-21214415 -Ref: Ranges and Locales-Footnote-31214650 -Node: Contributors1214873 -Node: History summary1220870 -Node: Installation1222250 -Node: Gawk Distribution1223194 -Node: Getting1223678 -Node: Extracting1224641 -Node: Distribution contents1226279 -Node: Unix Installation1232759 -Node: Quick Installation1233441 -Node: Shell Startup Files1235855 -Node: Additional Configuration Options1236944 -Node: Configuration Philosophy1239259 -Node: Non-Unix Installation1241628 -Node: PC Installation1242088 -Node: PC Binary Installation1242926 -Node: PC Compiling1243361 -Node: PC Using1244478 -Node: Cygwin1248031 -Node: MSYS1249255 -Node: VMS Installation1249857 -Node: VMS Compilation1250648 -Ref: VMS Compilation-Footnote-11251877 -Node: VMS Dynamic Extensions1251935 -Node: VMS Installation Details1253620 -Node: VMS Running1255873 -Node: VMS GNV1260152 -Node: VMS Old Gawk1260887 -Node: Bugs1261358 -Node: Bug address1262021 -Node: Usenet1265003 -Node: Maintainers1266007 -Node: Other Versions1267192 -Node: Installation summary1275057 -Node: Notes1276266 -Node: Compatibility Mode1277060 -Node: Additions1277842 -Node: Accessing The Source1278767 -Node: Adding Code1280204 -Node: New Ports1286423 -Node: Derived Files1290798 -Ref: Derived Files-Footnote-11296458 -Ref: Derived Files-Footnote-21296493 -Ref: Derived Files-Footnote-31297091 -Node: Future Extensions1297205 -Node: Implementation Limitations1297863 -Node: Extension Design1299073 -Node: Old Extension Problems1300217 -Ref: Old Extension Problems-Footnote-11301735 -Node: Extension New Mechanism Goals1301792 -Ref: Extension New Mechanism Goals-Footnote-11305156 -Node: Extension Other Design Decisions1305345 -Node: Extension Future Growth1307458 -Node: Notes summary1308064 -Node: Basic Concepts1309222 -Node: Basic High Level1309903 -Ref: figure-general-flow1310185 -Ref: figure-process-flow1310870 -Ref: Basic High Level-Footnote-11314171 -Node: Basic Data Typing1314356 -Node: Glossary1317684 -Node: Copying1349569 -Node: GNU Free Documentation License1387112 -Node: Index1412232 +Node: Exit Status154246 +Node: Include Files154923 +Node: Loading Shared Libraries158613 +Node: Obsolete160041 +Node: Undocumented160733 +Node: Invoking Summary161030 +Node: Regexp163871 +Node: Regexp Usage165325 +Node: Escape Sequences167362 +Node: Regexp Operators173603 +Node: Regexp Operator Details174088 +Ref: Regexp Operator Details-Footnote-1180520 +Node: Interval Expressions180667 +Ref: Interval Expressions-Footnote-1182088 +Node: Bracket Expressions182186 +Ref: table-char-classes184662 +Node: Leftmost Longest187988 +Node: Computed Regexps189291 +Node: GNU Regexp Operators192718 +Node: Case-sensitivity196455 +Ref: Case-sensitivity-Footnote-1199321 +Ref: Case-sensitivity-Footnote-2199556 +Node: Regexp Summary199664 +Node: Reading Files201130 +Node: Records203399 +Node: awk split records204474 +Node: gawk split records209174 +Ref: gawk split records-Footnote-1214248 +Node: Fields214285 +Node: Nonconstant Fields217026 +Ref: Nonconstant Fields-Footnote-1219262 +Node: Changing Fields219466 +Node: Field Separators225497 +Node: Default Field Splitting228195 +Node: Regexp Field Splitting229313 +Node: Single Character Fields232990 +Node: Command Line Field Separator234050 +Node: Full Line Fields237268 +Ref: Full Line Fields-Footnote-1238790 +Ref: Full Line Fields-Footnote-2238836 +Node: Field Splitting Summary238937 +Node: Constant Size241011 +Node: Fixed width data241743 +Node: Skipping intervening245210 +Node: Allowing trailing data246008 +Node: Fields with fixed data247045 +Node: Splitting By Content248563 +Ref: Splitting By Content-Footnote-1252346 +Node: More CSV252509 +Node: Testing field creation254101 +Node: Multiple Line255726 +Node: Getline262003 +Node: Plain Getline264472 +Node: Getline/Variable267045 +Node: Getline/File268196 +Node: Getline/Variable/File269584 +Ref: Getline/Variable/File-Footnote-1271189 +Node: Getline/Pipe271277 +Node: Getline/Variable/Pipe273981 +Node: Getline/Coprocess275116 +Node: Getline/Variable/Coprocess276383 +Node: Getline Notes277125 +Node: Getline Summary279922 +Ref: table-getline-variants280346 +Node: Read Timeout281094 +Ref: Read Timeout-Footnote-1285000 +Node: Retrying Input285058 +Node: Command-line directories286257 +Node: Input Summary287163 +Node: Input Exercises290335 +Node: Printing290769 +Node: Print292603 +Node: Print Examples294060 +Node: Output Separators296840 +Node: OFMT298857 +Node: Printf300213 +Node: Basic Printf300998 +Node: Control Letters302572 +Node: Format Modifiers307734 +Node: Printf Examples313749 +Node: Redirection316235 +Node: Special FD323076 +Ref: Special FD-Footnote-1326244 +Node: Special Files326318 +Node: Other Inherited Files326935 +Node: Special Network327936 +Node: Special Caveats328796 +Node: Close Files And Pipes329745 +Ref: table-close-pipe-return-values336652 +Ref: Close Files And Pipes-Footnote-1337465 +Ref: Close Files And Pipes-Footnote-2337613 +Node: Nonfatal337765 +Node: Output Summary340103 +Node: Output Exercises341325 +Node: Expressions342004 +Node: Values343192 +Node: Constants343870 +Node: Scalar Constants344561 +Ref: Scalar Constants-Footnote-1347071 +Node: Nondecimal-numbers347321 +Node: Regexp Constants350322 +Node: Using Constant Regexps350848 +Node: Standard Regexp Constants351470 +Node: Strong Regexp Constants354658 +Node: Variables357670 +Node: Using Variables358327 +Node: Assignment Options360237 +Node: Conversion362708 +Node: Strings And Numbers363232 +Ref: Strings And Numbers-Footnote-1366295 +Node: Locale influences conversions366404 +Ref: table-locale-affects369162 +Node: All Operators369780 +Node: Arithmetic Ops370409 +Node: Concatenation373125 +Ref: Concatenation-Footnote-1375972 +Node: Assignment Ops376079 +Ref: table-assign-ops381070 +Node: Increment Ops382383 +Node: Truth Values and Conditions385843 +Node: Truth Values386917 +Node: Typing and Comparison387965 +Node: Variable Typing388785 +Ref: Variable Typing-Footnote-1395248 +Ref: Variable Typing-Footnote-2395320 +Node: Comparison Operators395397 +Ref: table-relational-ops395816 +Node: POSIX String Comparison399311 +Ref: POSIX String Comparison-Footnote-1401006 +Ref: POSIX String Comparison-Footnote-2401145 +Node: Boolean Ops401229 +Ref: Boolean Ops-Footnote-1405711 +Node: Conditional Exp405803 +Node: Function Calls407539 +Node: Precedence411416 +Node: Locales415075 +Node: Expressions Summary416707 +Node: Patterns and Actions419280 +Node: Pattern Overview420400 +Node: Regexp Patterns422077 +Node: Expression Patterns422619 +Node: Ranges426400 +Node: BEGIN/END429508 +Node: Using BEGIN/END430269 +Ref: Using BEGIN/END-Footnote-1433023 +Node: I/O And BEGIN/END433129 +Node: BEGINFILE/ENDFILE435442 +Node: Empty438673 +Node: Using Shell Variables438990 +Node: Action Overview441264 +Node: Statements443589 +Node: If Statement445437 +Node: While Statement446932 +Node: Do Statement448960 +Node: For Statement450108 +Node: Switch Statement453279 +Node: Break Statement455720 +Node: Continue Statement457812 +Node: Next Statement459639 +Node: Nextfile Statement462022 +Node: Exit Statement464711 +Node: Built-in Variables467114 +Node: User-modified468247 +Node: Auto-set476014 +Ref: Auto-set-Footnote-1492821 +Ref: Auto-set-Footnote-2493027 +Node: ARGC and ARGV493083 +Node: Pattern Action Summary497296 +Node: Arrays499726 +Node: Array Basics501055 +Node: Array Intro501899 +Ref: figure-array-elements503874 +Ref: Array Intro-Footnote-1506578 +Node: Reference to Elements506706 +Node: Assigning Elements509170 +Node: Array Example509661 +Node: Scanning an Array511420 +Node: Controlling Scanning514442 +Ref: Controlling Scanning-Footnote-1520898 +Node: Numeric Array Subscripts521214 +Node: Uninitialized Subscripts523398 +Node: Delete525017 +Ref: Delete-Footnote-1527769 +Node: Multidimensional527826 +Node: Multiscanning530921 +Node: Arrays of Arrays532512 +Node: Arrays Summary537280 +Node: Functions539373 +Node: Built-in540411 +Node: Calling Built-in541492 +Node: Numeric Functions543488 +Ref: Numeric Functions-Footnote-1547514 +Ref: Numeric Functions-Footnote-2548162 +Ref: Numeric Functions-Footnote-3548210 +Node: String Functions548482 +Ref: String Functions-Footnote-1572623 +Ref: String Functions-Footnote-2572751 +Ref: String Functions-Footnote-3572999 +Node: Gory Details573086 +Ref: table-sub-escapes574877 +Ref: table-sub-proposed576396 +Ref: table-posix-sub577759 +Ref: table-gensub-escapes579300 +Ref: Gory Details-Footnote-1580123 +Node: I/O Functions580277 +Ref: table-system-return-values586731 +Ref: I/O Functions-Footnote-1588811 +Ref: I/O Functions-Footnote-2588959 +Node: Time Functions589079 +Ref: Time Functions-Footnote-1599750 +Ref: Time Functions-Footnote-2599818 +Ref: Time Functions-Footnote-3599976 +Ref: Time Functions-Footnote-4600087 +Ref: Time Functions-Footnote-5600199 +Ref: Time Functions-Footnote-6600426 +Node: Bitwise Functions600692 +Ref: table-bitwise-ops601286 +Ref: Bitwise Functions-Footnote-1607349 +Ref: Bitwise Functions-Footnote-2607522 +Node: Type Functions607713 +Node: I18N Functions610576 +Node: User-defined612227 +Node: Definition Syntax613039 +Ref: Definition Syntax-Footnote-1618733 +Node: Function Example618804 +Ref: Function Example-Footnote-1621726 +Node: Function Calling621748 +Node: Calling A Function622336 +Node: Variable Scope623294 +Node: Pass By Value/Reference626288 +Node: Function Caveats628932 +Ref: Function Caveats-Footnote-1630979 +Node: Return Statement631099 +Node: Dynamic Typing634078 +Node: Indirect Calls635008 +Ref: Indirect Calls-Footnote-1645260 +Node: Functions Summary645388 +Node: Library Functions648093 +Ref: Library Functions-Footnote-1651700 +Ref: Library Functions-Footnote-2651843 +Node: Library Names652014 +Ref: Library Names-Footnote-1655681 +Ref: Library Names-Footnote-2655904 +Node: General Functions655990 +Node: Strtonum Function657093 +Node: Assert Function660115 +Node: Round Function663441 +Node: Cliff Random Function664981 +Node: Ordinal Functions665997 +Ref: Ordinal Functions-Footnote-1669060 +Ref: Ordinal Functions-Footnote-2669312 +Node: Join Function669522 +Ref: Join Function-Footnote-1671292 +Node: Getlocaltime Function671492 +Node: Readfile Function675234 +Node: Shell Quoting677211 +Node: Data File Management678612 +Node: Filetrans Function679244 +Node: Rewind Function683340 +Node: File Checking685249 +Ref: File Checking-Footnote-1686583 +Node: Empty Files686784 +Node: Ignoring Assigns688763 +Node: Getopt Function690313 +Ref: Getopt Function-Footnote-1705524 +Node: Passwd Functions705724 +Ref: Passwd Functions-Footnote-1714563 +Node: Group Functions714651 +Ref: Group Functions-Footnote-1722549 +Node: Walking Arrays722756 +Node: Library Functions Summary725764 +Node: Library Exercises727170 +Node: Sample Programs727635 +Node: Running Examples728405 +Node: Clones729133 +Node: Cut Program730357 +Node: Egrep Program740497 +Node: Id Program749498 +Node: Split Program759445 +Ref: Split Program-Footnote-1769335 +Node: Tee Program769508 +Node: Uniq Program772298 +Node: Wc Program779886 +Node: Bytes vs. Characters780283 +Node: Using extensions781831 +Node: wc program782585 +Node: Miscellaneous Programs787450 +Node: Dupword Program788663 +Node: Alarm Program790693 +Node: Translate Program795548 +Ref: Translate Program-Footnote-1800113 +Node: Labels Program800383 +Ref: Labels Program-Footnote-1803734 +Node: Word Sorting803818 +Node: History Sorting807890 +Node: Extract Program810115 +Node: Simple Sed818169 +Node: Igawk Program821243 +Ref: Igawk Program-Footnote-1835574 +Ref: Igawk Program-Footnote-2835776 +Ref: Igawk Program-Footnote-3835898 +Node: Anagram Program836013 +Node: Signature Program839075 +Node: Programs Summary840322 +Node: Programs Exercises841536 +Ref: Programs Exercises-Footnote-1845666 +Node: Advanced Features845752 +Node: Nondecimal Data847819 +Node: Array Sorting849410 +Node: Controlling Array Traversal850110 +Ref: Controlling Array Traversal-Footnote-1858478 +Node: Array Sorting Functions858596 +Ref: Array Sorting Functions-Footnote-1863687 +Node: Two-way I/O863883 +Ref: Two-way I/O-Footnote-1871604 +Ref: Two-way I/O-Footnote-2871791 +Node: TCP/IP Networking871873 +Node: Profiling874991 +Node: Extension Philosophy884300 +Node: Advanced Features Summary885779 +Node: Internationalization887794 +Node: I18N and L10N889274 +Node: Explaining gettext889961 +Ref: Explaining gettext-Footnote-1895853 +Ref: Explaining gettext-Footnote-2896038 +Node: Programmer i18n896203 +Ref: Programmer i18n-Footnote-1901152 +Node: Translator i18n901201 +Node: String Extraction901995 +Ref: String Extraction-Footnote-1903127 +Node: Printf Ordering903213 +Ref: Printf Ordering-Footnote-1905999 +Node: I18N Portability906063 +Ref: I18N Portability-Footnote-1908519 +Node: I18N Example908582 +Ref: I18N Example-Footnote-1911857 +Ref: I18N Example-Footnote-2911930 +Node: Gawk I18N912039 +Node: I18N Summary912688 +Node: Debugger914029 +Node: Debugging915029 +Node: Debugging Concepts915470 +Node: Debugging Terms917279 +Node: Awk Debugging919854 +Ref: Awk Debugging-Footnote-1920799 +Node: Sample Debugging Session920931 +Node: Debugger Invocation921465 +Node: Finding The Bug922851 +Node: List of Debugger Commands929325 +Node: Breakpoint Control930658 +Node: Debugger Execution Control934352 +Node: Viewing And Changing Data937714 +Node: Execution Stack941255 +Node: Debugger Info942892 +Node: Miscellaneous Debugger Commands946963 +Node: Readline Support952025 +Node: Limitations952921 +Node: Debugging Summary955475 +Node: Namespaces956754 +Node: Global Namespace957865 +Node: Qualified Names959263 +Node: Default Namespace960262 +Node: Changing The Namespace961003 +Node: Naming Rules962617 +Node: Internal Name Management964465 +Node: Namespace Example965507 +Node: Namespace And Features968069 +Node: Namespace Summary969504 +Node: Arbitrary Precision Arithmetic970981 +Node: Computer Arithmetic972468 +Ref: table-numeric-ranges976234 +Ref: table-floating-point-ranges976727 +Ref: Computer Arithmetic-Footnote-1977385 +Node: Math Definitions977442 +Ref: table-ieee-formats980418 +Node: MPFR features980985 +Node: FP Math Caution982703 +Ref: FP Math Caution-Footnote-1983775 +Node: Inexactness of computations984144 +Node: Inexact representation985175 +Node: Comparing FP Values986535 +Node: Errors accumulate987776 +Node: Strange values989232 +Ref: Strange values-Footnote-1991820 +Node: Getting Accuracy991925 +Node: Try To Round994635 +Node: Setting precision995534 +Ref: table-predefined-precision-strings996231 +Node: Setting the rounding mode998061 +Ref: table-gawk-rounding-modes998435 +Ref: Setting the rounding mode-Footnote-11002366 +Node: Arbitrary Precision Integers1002545 +Ref: Arbitrary Precision Integers-Footnote-11005720 +Node: Checking for MPFR1005869 +Node: POSIX Floating Point Problems1007343 +Ref: POSIX Floating Point Problems-Footnote-11011628 +Node: Floating point summary1011666 +Node: Dynamic Extensions1013856 +Node: Extension Intro1015409 +Node: Plugin License1016675 +Node: Extension Mechanism Outline1017472 +Ref: figure-load-extension1017911 +Ref: figure-register-new-function1019476 +Ref: figure-call-new-function1020568 +Node: Extension API Description1022630 +Node: Extension API Functions Introduction1024343 +Ref: table-api-std-headers1026179 +Node: General Data Types1030428 +Ref: General Data Types-Footnote-11039058 +Node: Memory Allocation Functions1039357 +Ref: Memory Allocation Functions-Footnote-11043858 +Node: Constructor Functions1043957 +Node: API Ownership of MPFR and GMP Values1047423 +Node: Registration Functions1048736 +Node: Extension Functions1049436 +Node: Exit Callback Functions1054758 +Node: Extension Version String1056008 +Node: Input Parsers1056671 +Node: Output Wrappers1069392 +Node: Two-way processors1073904 +Node: Printing Messages1076169 +Ref: Printing Messages-Footnote-11077340 +Node: Updating ERRNO1077493 +Node: Requesting Values1078232 +Ref: table-value-types-returned1078969 +Node: Accessing Parameters1079905 +Node: Symbol Table Access1081142 +Node: Symbol table by name1081654 +Ref: Symbol table by name-Footnote-11084678 +Node: Symbol table by cookie1084806 +Ref: Symbol table by cookie-Footnote-11088991 +Node: Cached values1089055 +Ref: Cached values-Footnote-11092591 +Node: Array Manipulation1092744 +Ref: Array Manipulation-Footnote-11093835 +Node: Array Data Types1093872 +Ref: Array Data Types-Footnote-11096530 +Node: Array Functions1096622 +Node: Flattening Arrays1101120 +Node: Creating Arrays1108096 +Node: Redirection API1112863 +Node: Extension API Variables1115696 +Node: Extension Versioning1116407 +Ref: gawk-api-version1116836 +Node: Extension GMP/MPFR Versioning1118567 +Node: Extension API Informational Variables1120195 +Node: Extension API Boilerplate1121268 +Node: Changes from API V11125242 +Node: Finding Extensions1126814 +Node: Extension Example1127373 +Node: Internal File Description1128171 +Node: Internal File Ops1132251 +Ref: Internal File Ops-Footnote-11143601 +Node: Using Internal File Ops1143741 +Ref: Using Internal File Ops-Footnote-11146124 +Node: Extension Samples1146398 +Node: Extension Sample File Functions1147927 +Node: Extension Sample Fnmatch1155576 +Node: Extension Sample Fork1157063 +Node: Extension Sample Inplace1158281 +Node: Extension Sample Ord1161907 +Node: Extension Sample Readdir1162743 +Ref: table-readdir-file-types1163632 +Node: Extension Sample Revout1164699 +Node: Extension Sample Rev2way1165288 +Node: Extension Sample Read write array1166028 +Node: Extension Sample Readfile1167970 +Node: Extension Sample Time1169065 +Node: Extension Sample API Tests1170817 +Node: gawkextlib1171309 +Node: Extension summary1174227 +Node: Extension Exercises1177929 +Node: Language History1179171 +Node: V7/SVR3.11180827 +Node: SVR41182979 +Node: POSIX1184413 +Node: BTL1185794 +Node: POSIX/GNU1186523 +Node: Feature History1192301 +Node: Common Extensions1208620 +Node: Ranges and Locales1209903 +Ref: Ranges and Locales-Footnote-11214519 +Ref: Ranges and Locales-Footnote-21214546 +Ref: Ranges and Locales-Footnote-31214781 +Node: Contributors1215004 +Node: History summary1221001 +Node: Installation1222381 +Node: Gawk Distribution1223325 +Node: Getting1223809 +Node: Extracting1224772 +Node: Distribution contents1226410 +Node: Unix Installation1232890 +Node: Quick Installation1233572 +Node: Shell Startup Files1235986 +Node: Additional Configuration Options1237075 +Node: Configuration Philosophy1239390 +Node: Non-Unix Installation1241759 +Node: PC Installation1242219 +Node: PC Binary Installation1243057 +Node: PC Compiling1243492 +Node: PC Using1244609 +Node: Cygwin1248162 +Node: MSYS1249386 +Node: VMS Installation1249988 +Node: VMS Compilation1250779 +Ref: VMS Compilation-Footnote-11252008 +Node: VMS Dynamic Extensions1252066 +Node: VMS Installation Details1253751 +Node: VMS Running1256004 +Node: VMS GNV1260283 +Node: VMS Old Gawk1261018 +Node: Bugs1261489 +Node: Bug address1262152 +Node: Usenet1265134 +Node: Maintainers1266138 +Node: Other Versions1267323 +Node: Installation summary1275188 +Node: Notes1276397 +Node: Compatibility Mode1277191 +Node: Additions1277973 +Node: Accessing The Source1278898 +Node: Adding Code1280335 +Node: New Ports1286554 +Node: Derived Files1290929 +Ref: Derived Files-Footnote-11296589 +Ref: Derived Files-Footnote-21296624 +Ref: Derived Files-Footnote-31297222 +Node: Future Extensions1297336 +Node: Implementation Limitations1297994 +Node: Extension Design1299204 +Node: Old Extension Problems1300348 +Ref: Old Extension Problems-Footnote-11301866 +Node: Extension New Mechanism Goals1301923 +Ref: Extension New Mechanism Goals-Footnote-11305287 +Node: Extension Other Design Decisions1305476 +Node: Extension Future Growth1307589 +Node: Notes summary1308195 +Node: Basic Concepts1309353 +Node: Basic High Level1310034 +Ref: figure-general-flow1310316 +Ref: figure-process-flow1311001 +Ref: Basic High Level-Footnote-11314302 +Node: Basic Data Typing1314487 +Node: Glossary1317815 +Node: Copying1349700 +Node: GNU Free Documentation License1387243 +Node: Index1412363  End Tag Table diff --git a/doc/gawk.texi b/doc/gawk.texi index 82c06b52..b472316b 100644 --- a/doc/gawk.texi +++ b/doc/gawk.texi @@ -4842,7 +4842,10 @@ blocksize, which is usually the filesystem's I/O blocksize.) If this variable exists with a value of @samp{gst}, @command{gawk} switches to using the hash function from GNU Smalltalk for managing arrays. -This function may be marginally faster than the standard function. +With a value of @samp{fnv1a}, @command{gawk} uses the +@uref{http://www.isthe.com/chongo/tech/comp/fnv/index.html, +FNV1-A hash function}. +These functions may be marginally faster than the standard function. @item AWKREADFUNC If this variable exists, @command{gawk} switches to reading source diff --git a/doc/gawktexi.in b/doc/gawktexi.in index fb237350..2c2d7297 100644 --- a/doc/gawktexi.in +++ b/doc/gawktexi.in @@ -4708,7 +4708,10 @@ blocksize, which is usually the filesystem's I/O blocksize.) If this variable exists with a value of @samp{gst}, @command{gawk} switches to using the hash function from GNU Smalltalk for managing arrays. -This function may be marginally faster than the standard function. +With a value of @samp{fnv1a}, @command{gawk} uses the +@uref{http://www.isthe.com/chongo/tech/comp/fnv/index.html, +FNV1-A hash function}. +These functions may be marginally faster than the standard function. @item AWKREADFUNC If this variable exists, @command{gawk} switches to reading source diff --git a/str_array.c b/str_array.c index 84bd2f02..215a52fd 100644 --- a/str_array.c +++ b/str_array.c @@ -94,6 +94,7 @@ static void grow_table(NODE *symbol); static unsigned long gst_hash_string(const char *str, size_t len, unsigned long hsize, size_t *code); static unsigned long scramble(unsigned long x); +static unsigned long fnv1a_hash_string(const char *str, size_t len, unsigned long hsize, size_t *code); static unsigned long awk_hash(const char *s, size_t len, unsigned long hsize, size_t *code); unsigned long (*hash)(const char *s, size_t len, unsigned long hsize, size_t *code) = awk_hash; @@ -111,8 +112,13 @@ str_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED) /* check relevant environment variables */ if ((newval = getenv_long("STR_CHAIN_MAX")) > 0) STR_CHAIN_MAX = newval; - if ((val = getenv("AWK_HASH")) != NULL && strcmp(val, "gst") == 0) - hash = gst_hash_string; + + if ((val = getenv("AWK_HASH")) != NULL) { + if (strcmp(val, "gst") == 0) + hash = gst_hash_string; + else if (strcmp(val, "fnv1a") == 0) + hash = fnv1a_hash_string; + } } else null_array(symbol); @@ -772,6 +778,34 @@ scramble(unsigned long x) return x; } +/* fnv1a_hash_string --- fnv1a hash function */ + +/* + * FNV-1a hash function + * http://www.isthe.com/chongo/tech/comp/fnv/index.html + */ + +static unsigned long +fnv1a_hash_string(const char *str, size_t len, unsigned long hsize, size_t *code) +{ + /* FNV-1a */ + register unsigned ret = 2166136261U; + + while (len > 0) { + ret ^= (unsigned char) (*str++); + ret *= 16777619U; + len-- ; + } + + if (code != NULL) + *code = ret; + + if (ret >= hsize) + ret %= hsize; + + return ret; +} + /* env_remove --- for ENVIRON, remove value from real environment */ static NODE ** -- cgit v1.2.1