[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gawk-diffs] [SCM] gawk branch, master, updated. 44cd8b0b374419f77febc50
|
From: |
Arnold Robbins |
|
Subject: |
[gawk-diffs] [SCM] gawk branch, master, updated. 44cd8b0b374419f77febc504b0053b87c894810c |
|
Date: |
Tue, 25 Oct 2011 20:09:15 +0000 |
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "gawk".
The branch, master has been updated
via 44cd8b0b374419f77febc504b0053b87c894810c (commit)
via a3d40d091d31ec54b85240209afddb0212de085c (commit)
via 3a149467427d21fcd2aebf523fb44b12bbe1d010 (commit)
via d9cd8461596769cf68417bae4f819b6ccb4d1d7b (commit)
via f14c009c2f40d5ccb14c66331d8d43b41480c5f9 (commit)
via 1df47081df8258ff14bb0a6f77e1410f643baa8b (commit)
via fe18d21be4bb5d92eb45b10a5fe37b2d908c706f (commit)
via 9773d7150bc164f72806b2b31fc5f43a4a115721 (commit)
via fc34db7df7a5992eed6d416a86d77789aeb6b143 (commit)
via 93726e541fa0c9ece75d4b62bbfc0dd50dc6d0d6 (commit)
via e1cf68f45b6417234c416c703625adf2146acad6 (commit)
via b8a1c347098ba746c5b2ba6201790f6cfc7eba44 (commit)
via f34fdd3438efc2c66cbd7ceeaf06c70b814342ad (commit)
via 3b5e1a089dc3f1193ddc73747524aa24fcab3899 (commit)
via 54b630ec92718b620e53997958003ea978fb9006 (commit)
via afc57f3db63c875d7cacbb2d69482558ef536ee7 (commit)
via c0a8d7149e857272e9202044c8ed77b4fc02e180 (commit)
via b93f884037cf5fb58029cb9108923609aa94dc2a (commit)
via d45dee9add229d64ca875c11c78392e1a80dc100 (commit)
via b8fb7b2d4287058c9d2fab1a871e9181840279be (commit)
via 4a9f65ea0a861f842fa05120f9da0365019c2892 (commit)
via 0cf50ae4c064bd2d8960ffd1e14f97402b8f5157 (commit)
from a2f4c46ba3d4cd3de6be372316abc0e0e6518d4c (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
http://git.sv.gnu.org/cgit/gawk.git/commit/?id=44cd8b0b374419f77febc504b0053b87c894810c
commit 44cd8b0b374419f77febc504b0053b87c894810c
Merge: a2f4c46 a3d40d0
Author: Arnold D. Robbins <address@hidden>
Date: Tue Oct 25 22:08:53 2011 +0200
Merge branch 'gawk-4.0-stable'
diff --cc ChangeLog
index b6b3828,4f6f4b7..b4b3ae2
--- a/ChangeLog
+++ b/ChangeLog
@@@ -1,11 -1,68 +1,76 @@@
2011-10-25 Arnold D. Robbins <address@hidden>
+ Merge with gawk_performance branch done. Additionally:
+
+ * cint_array.c, int_array.c, str_array.c: Fix compiler complaints
+ about printf formats (signed / unsigned vs. %d / %u).
+ * eval.c (setup_frame): Add a missing return value.
+
++2011-10-25 Arnold D. Robbins <address@hidden>
++
+ * Makefile.am (dist-hook): Use `cd $(srcdir)/pc' so that
+ `make distcheck' works completely.
+ * builtin.c (do_strftime): Add cast to long int in check
+ for fclock < 0 for systems where time_t is unsigned (e.g., VMS).
+
+ 2011-10-25 Stefano Lattarini <address@hidden>
+
+ dist: generated file `version.c' is not removed by "make distclean"
+
+ * Makefile.am (distcleancheck_listfiles): Define to ignore the
+ generated `version.c' file.
+
+ 2011-10-24 Arnold D. Robbins <address@hidden>
+
+ * dfa.c (wcscoll): Create for VMS.
+ * Makefile.am (dist-hook): Run sed scripts to make pc/config.h.
+
+ 2011-10-24 Eli Zaretskii <address@hidden>
+
+ * builtin.c [HAVE_POPEN_H]: Include "popen.h".
+ * README.git: Update for pc/ systems.
+
+ 2011-10-21 Arnold D. Robbins <address@hidden>
+
+ * Makefile.am (distcleancheck_listfiles): Added, per advice from
+ Stefano Lattarini <address@hidden>.
+ * dfa.c: Additional faking of mbsupport for systems without it;
+ mainly VMS.
+
+ 2011-10-21 Stefano Lattarini <address@hidden>
+
+ * configure.ac (AM_C_PROTOTYPES): Remove call to this macro.
+ The comments in configure.ac said that the call to AM_C_PROTOTYPES
+ was needed for dfa.h, synced from GNU grep; but this statement is
+ not true anymore in grep since commit v2.5.4-24-g9b5e7d4 "replace
+ AC_CHECK_* with gnulib modules", dating back to 2009-11-26. Also,
+ the support for automatic de-ANSI-fication has been deprecated in
+ automake 1.11.2, and will be removed altogether in automake 1.12.
+ * vms/vms-conf.h (PROTOTYPES, __PROTOTYPES): Remove these #define,
+ they are not used anymore.
+ * pc/config.h (PROTOTYPES): Likewise.
+
+ 2011-10-18 Dave Pitts <address@hidden>
+
+ * dfa.c: Move some decls to the top of their functions for
+ C90 compilers.
+
+ 2011-10-18 Arnold D. Robbins <address@hidden>
+
+ * builtin.c (do_strftime): Add check for negative / overflowed
+ time_t value with fatal error. Thanks to Hermann Peifer
+ <address@hidden> for the bug report.
+ * dfa.c (setbit_wc): Non-MBS version. Add a return false
+ since VMS compiler doesn't understand that abort doesn't return.
+
+ 2011-10-10 Arnold D. Robbins <address@hidden>
+
+ * builtin.c (do_sub): Init textlen to zero to avoid "may be
+ used unitialized" warning. Thanks to Corinna Vinschen for
+ pointing this out.
+ * eval.c (unwind_stack): Add parentheses around condition in while
+ to avoid overzealous warning from GCC.
+
2011-09-30 Eli Zaretskii <address@hidden>
* io.c (remap_std_file): Fix non-portable code that caused
diff --cc array.c
index 70e0dec,82e99a4..2a89a60
--- a/array.c
+++ b/array.c
@@@ -1264,40 -1609,32 +1264,40 @@@ assoc_list(NODE *symbol, const char *so
static const struct qsort_funcs {
const char *name;
qsort_compfunc comp_func;
- qsort_prefunc pre_func; /* pre-processing of list items
*/
+ enum assoc_list_flags flags;
} sort_funcs[] = {
- { "@ind_str_asc", sort_up_index_string, 0 },
- { "@ind_num_asc", sort_up_index_number,
sort_force_index_number },
- { "@val_str_asc", sort_up_value_string,
sort_force_value_string },
- { "@val_num_asc", sort_up_value_number,
sort_force_value_number },
- { "@ind_str_desc", sort_down_index_string, 0 },
- { "@ind_num_desc", sort_down_index_number,
sort_force_index_number },
- { "@val_str_desc", sort_down_value_string,
sort_force_value_string },
- { "@val_num_desc", sort_down_value_number,
sort_force_value_number },
- { "@val_type_asc", sort_up_value_type, 0 },
- { "@val_type_desc", sort_down_value_type, 0 },
- { "@unsorted", 0, 0 },
- };
+{ "@ind_str_asc", sort_up_index_string, AINDEX|AISTR|AASC },
+{ "@ind_num_asc", sort_up_index_number, AINDEX|AINUM|AASC },
+{ "@val_str_asc", sort_up_value_string, AVALUE|AVSTR|AASC },
+{ "@val_num_asc", sort_up_value_number, AVALUE|AVNUM|AASC },
+{ "@ind_str_desc", sort_down_index_string, AINDEX|AISTR|ADESC },
+{ "@ind_num_desc", sort_down_index_number, AINDEX|AINUM|ADESC },
+{ "@val_str_desc", sort_down_value_string, AVALUE|AVSTR|ADESC },
+{ "@val_num_desc", sort_down_value_number, AVALUE|AVNUM|ADESC },
+{ "@val_type_asc", sort_up_value_type, AVALUE|AASC },
+{ "@val_type_desc", sort_down_value_type, AVALUE|ADESC },
+{ "@unsorted", 0, AINDEX },
+};
+
+ /* N.B.: AASC and ADESC are hints to the specific array types.
+ * See cint_list() in cint_array.c.
+ */
+
NODE **list;
- NODE *r;
- size_t num_elems, i, j;
+ NODE fl;
+ unsigned long num_elems, j;
+ int elem_size, qi;
qsort_compfunc cmp_func = 0;
- qsort_prefunc pre_func = 0;
INSTRUCTION *code = NULL;
- int qi;
extern int currule;
- int save_rule;
++ int save_rule = 0;
- num_elems = array->table_size;
+ num_elems = symbol->table_size;
assert(num_elems > 0);
+ elem_size = 1;
+ fl.flags = 0;
+
for (qi = 0, j = sizeof(sort_funcs)/sizeof(sort_funcs[0]); qi < j;
qi++) {
if (strcmp(sort_funcs[qi].name, sort_str) == 0)
break;
diff --cc cint_array.c
index bdda111,0000000..3d812cb
mode 100644,000000..100644
--- a/cint_array.c
+++ b/cint_array.c
@@@ -1,1232 -1,0 +1,1232 @@@
+/*
+ * cint_array.c - routines for arrays of (mostly) consecutive positive
integer indices.
+ */
+
+/*
+ * Copyright (C) 1986, 1988, 1989, 1991-2011 the Free Software Foundation,
Inc.
+ *
+ * This file is part of GAWK, the GNU implementation of the
+ * AWK Programming Language.
+ *
+ * GAWK is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GAWK is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
USA
+ */
+
+#include "awk.h"
+
+extern FILE *output_fp;
+extern void indent(int indent_level);
+extern NODE **is_integer(NODE *symbol, NODE *subs);
+
+/*
+ * NHAT --- maximum size of a leaf array (2^NHAT).
+ * THRESHOLD --- Maximum capacity waste; THRESHOLD >= 2^(NHAT + 1).
+ */
+
+static int NHAT = 10;
+static long THRESHOLD;
+
+/* What is the optimium NHAT ? timing results suggest that 10 is a good
choice,
+ * although differences aren't that significant for > 10.
+ */
+
+
+static NODE **cint_array_init(NODE *symbol, NODE *subs);
+static NODE **is_uinteger(NODE *symbol, NODE *subs);
+static NODE **cint_lookup(NODE *symbol, NODE *subs);
+static NODE **cint_exists(NODE *symbol, NODE *subs);
+static NODE **cint_clear(NODE *symbol, NODE *subs);
+static NODE **cint_remove(NODE *symbol, NODE *subs);
+static NODE **cint_list(NODE *symbol, NODE *t);
+static NODE **cint_copy(NODE *symbol, NODE *newsymb);
+static NODE **cint_dump(NODE *symbol, NODE *ndump);
+#ifdef ARRAYDEBUG
+static NODE **cint_option(NODE *opt, NODE *val);
+static void cint_print(NODE *symbol);
+#endif
+
+array_ptr cint_array_func[] = {
+ cint_array_init,
+ is_uinteger,
+ cint_lookup,
+ cint_exists,
+ cint_clear,
+ cint_remove,
+ cint_list,
+ cint_copy,
+ cint_dump,
+#ifdef ARRAYDEBUG
+ cint_option,
+#endif
+};
+
+static inline int cint_hash(long k);
+static inline NODE **cint_find(NODE *symbol, long k, int h1);
+
+static inline NODE *make_node(NODETYPE type);
+
+static NODE **tree_lookup(NODE *symbol, NODE *tree, long k, int m, long base);
+static NODE **tree_exists(NODE *tree, long k);
+static void tree_clear(NODE *tree);
+static int tree_remove(NODE *symbol, NODE *tree, long k);
+static void tree_copy(NODE *newsymb, NODE *tree, NODE *newtree);
+static long tree_list(NODE *tree, NODE **list, unsigned int flags);
+static inline NODE **tree_find(NODE *tree, long k, int i);
+static void tree_info(NODE *tree, NODE *ndump, const char *aname);
+static size_t tree_kilobytes(NODE *tree);
+#ifdef ARRAYDEBUG
+static void tree_print(NODE *tree, size_t bi, int indent_level);
+#endif
+
+static inline NODE **leaf_lookup(NODE *symbol, NODE *array, long k, long
size, long base);
+static inline NODE **leaf_exists(NODE *array, long k);
+static void leaf_clear(NODE *array);
+static int leaf_remove(NODE *symbol, NODE *array, long k);
+static void leaf_copy(NODE *newsymb, NODE *array, NODE *newarray);
+static long leaf_list(NODE *array, NODE **list, unsigned int flags);
+static void leaf_info(NODE *array, NODE *ndump, const char *aname);
+#ifdef ARRAYDEBUG
+static void leaf_print(NODE *array, size_t bi, int indent_level);
+#endif
+
+/* powers of 2 table upto 2^30 */
+static const long power_two_table[] = {
+ 1, 2, 4, 8, 16, 32, 64,
+ 128, 256, 512, 1024, 2048, 4096,
+ 8192, 16384, 32768, 65536, 131072, 262144,
+ 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
+ 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824
+};
+
+
+#define ISUINT(a, s) ((((s)->flags & NUMINT) != 0 || is_integer(a, s) !=
NULL) \
+ && (s)->numbr >= 0)
+
+/*
+ * To store 2^n integers, allocate top-level array of size n, elements
+ * of which are 1-Dimensional (leaf-array) of geometrically increasing
+ * size (power of 2).
+ *
+ * [0] --> [ 0 ]
+ * [1] --> [ 1 ]
+ * |2| --> [ 2 | 3 ]
+ * |3| --> [ 4 | 5 | 6 | 7 ]
+ * |.|
+ * |k| --> [ 2^(k - 1)| ... | 2^k - 1 ]
+ * ...
+ *
+ * For a given integer n (> 0), the leaf-array is at 1 + floor(log2(n)).
+ *
+ * The idea for the geometrically increasing array sizes is from:
+ * Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays.
+ * Bagwell, Phil (2002).
+ * http://infoscience.epfl.ch/record/64410/files/techlists.pdf
+ *
+ * Disadvantage:
+ * Worst case memory waste > 99% and will happen when each of the
+ * leaf arrays contains only a single element. Even with consecutive
+ * integers, memory waste can be as high as 50%.
+ *
+ * Solution: Hashed Array Trees (HATs).
+ *
+ */
+
+/* cint_array_init --- check relevant environment variables */
+
+static NODE **
+cint_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED)
+{
+ long newval;
+
+ if ((newval = getenv_long("NHAT")) > 1 && newval < INT32_BIT)
+ NHAT = newval;
+ THRESHOLD = power_two_table[NHAT + 1];
+ return (NODE **) ! NULL;
+}
+
+
+/* is_uinteger --- test if the subscript is an integer >= 0 */
+
+NODE **
+is_uinteger(NODE *symbol, NODE *subs)
+{
+ if (is_integer(symbol, subs) != NULL && subs->numbr >= 0)
+ return (NODE **) ! NULL;
+ return NULL;
+}
+
+
+/* cint_lookup --- Find the subscript in the array; Install it if it isn't
there. */
+
+static NODE **
+cint_lookup(NODE *symbol, NODE *subs)
+{
+ NODE **lhs;
+ long k;
+ int h1 = -1, m, li;
+ NODE *tn, *xn;
+ long cint_size, capacity;
+
+ k = -1;
+ if (ISUINT(symbol, subs)) {
+ k = subs->numbr; /* k >= 0 */
+ h1 = cint_hash(k); /* h1 >= NHAT */
+ if ((lhs = cint_find(symbol, k, h1)) != NULL)
+ return lhs;
+ }
+ xn = symbol->xarray;
+ if (xn != NULL && (lhs = xn->aexists(xn, subs)) != NULL)
+ return lhs;
+
+ /* It's not there, install it */
+
+ if (k < 0)
+ goto xinstall;
+
+ m = h1 - 1; /* m >= (NHAT- 1) */
+
+ /* Estimate capacity upper bound.
+ * capacity upper bound = current capacity + leaf array size.
+ */
+ li = m > NHAT ? m : NHAT;
+ while (li >= NHAT) {
+ /* leaf-array of a HAT */
+ li = (li + 1) / 2;
+ }
+ capacity = symbol->array_capacity + power_two_table[li];
+
+ cint_size = (xn == NULL) ? symbol->table_size
+ : (symbol->table_size - xn->table_size);
+ assert(cint_size >= 0);
+ if ((capacity - cint_size) > THRESHOLD)
+ goto xinstall;
+
+ if (symbol->nodes == NULL) {
+ symbol->array_capacity = 0;
+ assert(symbol->table_size == 0);
+
+ /* nodes[0] .. nodes[NHAT- 1] not used */
+ emalloc(symbol->nodes, NODE **, INT32_BIT * sizeof(NODE *),
"cint_lookup");
+ memset(symbol->nodes, '\0', INT32_BIT * sizeof(NODE *));
+ }
+
+ symbol->table_size++; /* one more element in array */
+
+ tn = symbol->nodes[h1];
+ if (tn == NULL) {
+ tn = make_node(Node_array_tree);
+ symbol->nodes[h1] = tn;
+ }
+
+ if (m < NHAT)
+ return tree_lookup(symbol, tn, k, NHAT, 0);
+ return tree_lookup(symbol, tn, k, m, power_two_table[m]);
+
+xinstall:
+
+ symbol->table_size++;
+ if (xn == NULL) {
+ extern array_ptr int_array_func[];
+ extern array_ptr str_array_func[];
+
+ xn = symbol->xarray = make_array();
+ xn->vname = symbol->vname; /* shallow copy */
+
+ /* Avoid using assoc_lookup(xn, subs) which may lead
+ * to infinite recursion.
+ */
+
+ if (is_integer(xn, subs))
+ xn->array_funcs = int_array_func;
+ else
+ xn->array_funcs = str_array_func;
+ xn->flags |= XARRAY;
+ }
+ return xn->alookup(xn, subs);
+}
+
+
+/* cint_exists --- test whether an index is in the array or not. */
+
+static NODE **
+cint_exists(NODE *symbol, NODE *subs)
+{
+ NODE *xn;
+
+ if (ISUINT(symbol, subs)) {
+ long k = subs->numbr;
+ NODE **lhs;
+ if ((lhs = cint_find(symbol, k, cint_hash(k))) != NULL)
+ return lhs;
+ }
+ if ((xn = symbol->xarray) == NULL)
+ return NULL;
+ return xn->aexists(xn, subs);
+}
+
+
+/* cint_clear --- flush all the values in symbol[] */
+
+static NODE **
+cint_clear(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)
+{
+ size_t i;
+ NODE *tn;
+
+ assert(symbol->nodes != NULL);
+
+ if (symbol->xarray != NULL) {
+ NODE *xn = symbol->xarray;
+ assoc_clear(xn);
+ freenode(xn);
+ symbol->xarray = NULL;
+ }
+
+ for (i = NHAT; i < INT32_BIT; i++) {
+ tn = symbol->nodes[i];
+ if (tn != NULL) {
+ tree_clear(tn);
+ freenode(tn);
+ }
+ }
+
+ efree(symbol->nodes);
+ init_array(symbol); /* re-initialize symbol */
+ return NULL;
+}
+
+
+/* cint_remove --- remove an index from the array */
+
+static NODE **
+cint_remove(NODE *symbol, NODE *subs)
+{
+ long k;
+ int h1;
+ NODE *tn, *xn = symbol->xarray;
+
+ assert(symbol->nodes != NULL);
+ if (! ISUINT(symbol, subs))
+ goto xremove;
+
+ k = subs->numbr;
+ h1 = cint_hash(k);
+ tn = symbol->nodes[h1];
+ if (tn == NULL || ! tree_remove(symbol, tn, k))
+ goto xremove;
+
+ if (tn->table_size == 0) {
+ freenode(tn);
+ symbol->nodes[h1] = NULL;
+ }
+
+ symbol->table_size--;
+
+ if (xn == NULL && symbol->table_size == 0) {
+ efree(symbol->nodes);
+ init_array(symbol); /* re-initialize array 'symbol' */
+ } else if(xn != NULL && symbol->table_size == xn->table_size) {
+ /* promote xn to symbol */
+ xn->flags &= ~XARRAY;
+ xn->parent_array = symbol->parent_array;
+ efree(symbol->nodes);
+ *symbol = *xn;
+ freenode(xn);
+ }
+
+ return (NODE **) ! NULL;
+
+xremove:
+ xn = symbol->xarray;
+ if (xn == NULL || xn->aremove(xn, subs) == NULL)
+ return NULL;
+ if (xn->table_size == 0) {
+ freenode(xn);
+ symbol->xarray = NULL;
+ }
+ symbol->table_size--;
+ assert(symbol->table_size > 0);
+
+ return (NODE **) ! NULL;
+}
+
+
+/* cint_copy --- duplicate input array "symbol" */
+
+static NODE **
+cint_copy(NODE *symbol, NODE *newsymb)
+{
+ NODE **old, **new;
+ size_t i;
+
+ assert(symbol->nodes != NULL);
+
+ /* allocate new table */
+ emalloc(new, NODE **, INT32_BIT * sizeof(NODE *), "cint_copy");
+ memset(new, '\0', INT32_BIT * sizeof(NODE *));
+
+ old = symbol->nodes;
+ for (i = NHAT; i < INT32_BIT; i++) {
+ if (old[i] == NULL)
+ continue;
+ new[i] = make_node(Node_array_tree);
+ tree_copy(newsymb, old[i], new[i]);
+ }
+
+ if (symbol->xarray != NULL) {
+ NODE *xn, *n;
+ xn = symbol->xarray;
+ n = make_array();
+ n->vname = newsymb->vname;
+ (void) xn->acopy(xn, n);
+ newsymb->xarray = n;
+ } else
+ newsymb->xarray = NULL;
+
+ newsymb->nodes = new;
+ newsymb->table_size = symbol->table_size;
+ newsymb->array_capacity = symbol->array_capacity;
+ newsymb->flags = symbol->flags;
+
+ return NULL;
+}
+
+
+/* cint_list --- return a list of items */
+
+static NODE**
+cint_list(NODE *symbol, NODE *t)
+{
+ NODE **list = NULL;
+ NODE *tn, *xn;
+ unsigned long k = 0, num_elems, list_size;
+ size_t j, ja, jd;
+ int elem_size = 1;
+
+ num_elems = symbol->table_size;
+ if (num_elems == 0)
+ return NULL;
+
+ if ((t->flags & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))
+ num_elems = 1;
+
+ if ((t->flags & (AINDEX|AVALUE)) == (AINDEX|AVALUE))
+ elem_size = 2;
+ list_size = num_elems * elem_size;
+
+ if (symbol->xarray != NULL) {
+ xn = symbol->xarray;
+ list = xn->alist(xn, t);
+ assert(list != NULL);
+ t->flags &= ~(AASC|ADESC);
+ if (num_elems == 1 || num_elems == xn->table_size)
+ return list;
+ erealloc(list, NODE **, list_size * sizeof(NODE *),
"cint_list");
+ k = elem_size * xn->table_size;
+ } else
+ emalloc(list, NODE **, list_size * sizeof(NODE *), "cint_list");
+
+
+ if ((t->flags & AINUM) == 0) /* not sorting by "index num" */
+ t->flags &= ~(AASC|ADESC);
+
+ /* populate it with index in ascending or descending order */
+
+ for (ja = NHAT, jd = INT32_BIT - 1; ja < INT32_BIT && jd >= NHAT; ) {
+ j = (t->flags & ADESC) ? jd-- : ja++;
+ tn = symbol->nodes[j];
+ if (tn == NULL)
+ continue;
+ k += tree_list(tn, list + k, t->flags);
+ if (k >= list_size)
+ return list;
+ }
+ return list;
+}
+
+
+/* cint_dump --- dump array info */
+
+static NODE **
+cint_dump(NODE *symbol, NODE *ndump)
+{
+ NODE *tn, *xn = NULL;
+ int indent_level;
+ size_t i;
+ long cint_size = 0, xsize = 0;
+ AWKNUM kb = 0;
+ extern AWKNUM int_kilobytes(NODE *symbol);
+ extern AWKNUM str_kilobytes(NODE *symbol);
+ extern array_ptr int_array_func[];
+
+ indent_level = ndump->alevel;
+
+ if (symbol->xarray != NULL) {
+ xn = symbol->xarray;
+ xsize = xn->table_size;
+ }
+ cint_size = symbol->table_size - xsize;
+
+ if ((symbol->flags & XARRAY) == 0)
+ fprintf(output_fp, "%s `%s'\n",
+ (symbol->parent_array == NULL) ? "array" : "sub-array",
+ array_vname(symbol));
+ indent_level++;
+ indent(indent_level);
+ fprintf(output_fp, "array_func: cint_array_func\n");
+ if (symbol->flags != 0) {
+ indent(indent_level);
+ fprintf(output_fp, "flags: %s\n", flags2str(symbol->flags));
+ }
+ indent(indent_level);
+ fprintf(output_fp, "NHAT: %d\n", NHAT);
+ indent(indent_level);
+ fprintf(output_fp, "THRESHOLD: %ld\n", THRESHOLD);
+ indent(indent_level);
+ fprintf(output_fp, "table_size: %ld (total), %ld (cint), %ld (int +
str)\n",
+ symbol->table_size, cint_size, xsize);
+ indent(indent_level);
+ fprintf(output_fp, "array_capacity: %lu\n", (unsigned long)
symbol->array_capacity);
+ indent(indent_level);
+ fprintf(output_fp, "Load Factor: %.2g\n", (AWKNUM) cint_size /
symbol->array_capacity);
+
+ for (i = NHAT; i < INT32_BIT; i++) {
+ tn = symbol->nodes[i];
+ if (tn == NULL)
+ continue;
+ /* Node_array_tree + HAT */
+ kb += (sizeof(NODE) + tree_kilobytes(tn)) / 1024.0;
+ }
+ kb += (INT32_BIT * sizeof(NODE *)) / 1024.0; /* symbol->nodes */
+ kb += (symbol->array_capacity * sizeof(NODE *)) / 1024.0; /*
value nodes in Node_array_leaf(s) */
+ if (xn != NULL) {
+ if (xn->array_funcs == int_array_func)
+ kb += int_kilobytes(xn);
+ else
+ kb += str_kilobytes(xn);
+ }
+
+ indent(indent_level);
+ fprintf(output_fp, "memory: %.2g kB (total)\n", kb);
+
+ /* dump elements */
+
+ if (ndump->adepth >= 0) {
+ const char *aname;
+
+ fprintf(output_fp, "\n");
+ aname = make_aname(symbol);
+ for (i = NHAT; i < INT32_BIT; i++) {
+ tn = symbol->nodes[i];
+ if (tn != NULL)
+ tree_info(tn, ndump, aname);
+ }
+ }
+
+ if (xn != NULL) {
+ fprintf(output_fp, "\n");
+ xn->adump(xn, ndump);
+ }
+
+#ifdef ARRAYDEBUG
+ if (ndump->adepth < -999)
+ cint_print(symbol);
+#endif
+
+ return NULL;
+}
+
+
+/* cint_hash --- locate the HAT for a given number 'k' */
+
+static inline int
+cint_hash(long k)
+{
+ uint32_t num, r, shift;
+
+ assert(k >= 0);
+ if (k == 0)
+ return NHAT;
+ num = k;
+
+ /* Find the Floor(log base 2 of 32-bit integer) */
+
+ /* Warren Jr., Henry S. (2002). Hacker's Delight.
+ * Addison Wesley. pp. pp. 215. ISBN 978-0201914658.
+ *
+ * r = 0;
+ * if (num >= 1<<16) { num >>= 16; r += 16; }
+ * if (num >= 1<< 8) { num >>= 8; r += 8; }
+ * if (num >= 1<< 4) { num >>= 4; r += 4; }
+ * if (num >= 1<< 2) { num >>= 2; r += 2; }
+ * if (num >= 1<< 1) { r += 1; }
+ */
+
+
+ /* Slightly different code copied from:
+ *
+ * http://www-graphics.stanford.edu/~seander/bithacks.html
+ * Bit Twiddling Hacks
+ * By Sean Eron Anderson
+ * address@hidden
+ * Individually, the code snippets here are in the public domain
+ * (unless otherwise noted) â feel free to use them however you
please.
+ * The aggregate collection and descriptions are © 1997-2005
+ * Sean Eron Anderson. The code and descriptions are distributed in the
+ * hope that they will be useful, but WITHOUT ANY WARRANTY and without
+ * even the implied warranty of merchantability or fitness for a
particular
+ * purpose.
+ *
+ */
+
+ r = (num > 0xFFFF) << 4; num >>= r;
+ shift = (num > 0xFF) << 3; num >>= shift; r |= shift;
+ shift = (num > 0x0F) << 2; num >>= shift; r |= shift;
+ shift = (num > 0x03) << 1; num >>= shift; r |= shift;
+ r |= (num >> 1);
+
+ /* We use a single HAT for 0 <= num < 2^NHAT */
+ if (r < NHAT)
+ return NHAT;
+
+ return (1 + r);
+}
+
+
+/* cint_find --- locate the integer subscript */
+
+static inline NODE **
+cint_find(NODE *symbol, long k, int h1)
+{
+ NODE *tn;
+
+ if (symbol->nodes == NULL || (tn = symbol->nodes[h1]) == NULL)
+ return NULL;
+ return tree_exists(tn, k);
+}
+
+
+#ifdef ARRAYDEBUG
+
+static NODE **
+cint_option(NODE *opt, NODE *val)
+{
+ NODE *tmp;
+ NODE **ret = (NODE **) ! NULL;
+
+ tmp = force_string(opt);
+ (void) force_number(val);
+ if (STREQ(tmp->stptr, "NHAT"))
+ NHAT = (int) val->numbr;
+ else
+ ret = NULL;
+ return ret;
+}
+
+
+/* cint_print --- print structural info */
+
+static void
+cint_print(NODE *symbol)
+{
+ NODE *tn;
+ size_t i;
+
+ fprintf(output_fp, "I[%4lu:%-4lu]\n", (unsigned long) INT32_BIT,
+ (unsigned long) symbol->table_size);
+ for (i = NHAT; i < INT32_BIT; i++) {
+ tn = symbol->nodes[i];
+ if (tn == NULL)
+ continue;
+ tree_print(tn, i, 1);
+ }
+}
+
+#endif
+
+
+/*------------------------ Hashed Array Trees -----------------------------*/
+
+/*
+ * HATs: Hashed Array Trees
+ * Fast variable-length arrays
+ * Edward Sitarski
+ * http://www.drdobbs.com/architecture-and-design/184409965
+ *
+ * HAT has a top-level array containing a power of two
+ * number of leaf arrays. All leaf arrays are the same size as the
+ * top-level array. A full HAT can hold n^2 elements,
+ * where n (some power of 2) is the size of each leaf array.
+ * [i/n][i & (n - 1)] locates the `i th' element in a HAT.
+ *
+ */
+
+/*
+ * A half HAT is defined here as a HAT with a top-level array of size n^2/2
+ * and holds the first n^2/2 elements.
+ *
+ * 1. 2^8 elements can be stored in a full HAT of size 2^4.
+ * 2. 2^9 elements can be stored in a half HAT of size 2^5.
+ * 3. When the number of elements is some power of 2, it
+ * can be stored in a full or a half HAT.
+ * 4. When the number of elements is some power of 2, it
+ * can be stored in a HAT (full or half) with HATs as leaf elements
+ * (full or half), and so on (e.g. 2^8 elements in a HAT of size 2^4
(top-level
+ * array dimension) with each leaf array being a HAT of size 2^2).
+ *
+ * IMPLEMENTATION DETAILS:
+ * 1. A HAT of 2^12 elements needs 2^6 house-keeping NODEs
+ * of Node_array_leaf.
+ *
+ * 2. A HAT of HATS of 2^12 elements needs
+ * 2^6 * (1 Node_array_tree + 2^3 Node_array_leaf)
+ * ~ 2^9 house-keeping NODEs.
+ *
+ * 3. When a leaf array (or leaf HAT) becomes empty, the memory
+ * is deallocated, and when there is no leaf array (or leaf HAT) left,
+ * the HAT is deleted.
+ *
+ * 4. A HAT stores the base (first) element, and locates the leaf array/HAT
+ * for the `i th' element using integer division
+ * (i - base)/n where n is the size of the top-level array.
+ *
+ */
+
+/* make_node --- initialize a NODE */
+
+static inline NODE *
+make_node(NODETYPE type)
+{
+ NODE *n;
+ getnode(n);
+ memset(n, '\0', sizeof(NODE));
+ n->type = type;
+ return n;
+}
+
+
+/* tree_lookup --- Find an integer subscript in a HAT; Install it if it isn't
there */
+
+static NODE **
+tree_lookup(NODE *symbol, NODE *tree, long k, int m, long base)
+{
+ NODE **lhs;
+ NODE *tn;
+ int i, n;
+ size_t size;
+ long num = k;
+
+ /*
+ * HAT size (size of Top & Leaf array) = 2^n
+ * where n = Floor ((m + 1)/2). For an odd value of m,
+ * only the first half of the HAT is needed.
+ */
+
+ n = (m + 1) / 2;
+
+ if (tree->table_size == 0) {
+ size_t actual_size;
+ NODE **table;
+
+ assert(tree->nodes == NULL);
+
+ /* initialize top-level array */
+ size = actual_size = power_two_table[n];
+ tree->array_base = base;
+ tree->array_size = size;
+ tree->table_size = 0; /* # of elements in the array */
+ if (n > m/2) {
+ /* only first half of the array used */
+ actual_size /= 2;
+ tree->flags |= HALFHAT;
+ }
+ emalloc(table, NODE **, actual_size * sizeof(NODE *),
"tree_lookup");
+ memset(table, '\0', actual_size * sizeof(NODE *));
+ tree->nodes = table;
+ } else
+ size = tree->array_size;
+
+ num -= tree->array_base;
+ i = num / size; /* top-level array index */
+ assert(i >= 0);
+
+ if ((lhs = tree_find(tree, k, i)) != NULL)
+ return lhs;
+
+ /* It's not there, install it */
+
+ tree->table_size++;
+ base += (size * i);
+ tn = tree->nodes[i];
+ if (n > NHAT) {
+ if (tn == NULL)
+ tn = tree->nodes[i] = make_node(Node_array_tree);
+ return tree_lookup(symbol, tn, k, n, base);
+ } else {
+ if (tn == NULL)
+ tn = tree->nodes[i] = make_node(Node_array_leaf);
+ return leaf_lookup(symbol, tn, k, size, base);
+ }
+}
+
+
+/* tree_exists --- test whether integer subscript `k' exists or not */
+
+static NODE **
+tree_exists(NODE *tree, long k)
+{
+ int i;
+ NODE *tn;
+
+ i = (k - tree->array_base) / tree->array_size;
+ assert(i >= 0);
+ tn = tree->nodes[i];
+ if (tn == NULL)
+ return NULL;
+ if (tn->type == Node_array_tree)
+ return tree_exists(tn, k);
+ return leaf_exists(tn, k);
+}
+
+/* tree_clear --- flush all the values */
+
+static void
+tree_clear(NODE *tree)
+{
+ NODE *tn;
+ size_t j, hsize;
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
+
+ for (j = 0; j < hsize; j++) {
+ tn = tree->nodes[j];
+ if (tn == NULL)
+ continue;
+ if (tn->type == Node_array_tree)
+ tree_clear(tn);
+ else
+ leaf_clear(tn);
+ freenode(tn);
+ }
+
+ efree(tree->nodes);
+ memset(tree, '\0', sizeof(NODE));
+ tree->type = Node_array_tree;
+}
+
+
+/* tree_remove --- If the integer subscript is in the HAT, remove it */
+
+static int
+tree_remove(NODE *symbol, NODE *tree, long k)
+{
+ int i;
+ NODE *tn;
+
+ i = (k - tree->array_base) / tree->array_size;
+ assert(i >= 0);
+ tn = tree->nodes[i];
+ if (tn == NULL)
+ return FALSE;
+
+ if (tn->type == Node_array_tree
+ && ! tree_remove(symbol, tn, k))
+ return FALSE;
+ else if (tn->type == Node_array_leaf
+ && ! leaf_remove(symbol, tn, k))
+ return FALSE;
+
+ if (tn->table_size == 0) {
+ freenode(tn);
+ tree->nodes[i] = NULL;
+ }
+
+ /* one less item in array */
+ if (--tree->table_size == 0) {
+ efree(tree->nodes);
+ memset(tree, '\0', sizeof(NODE));
+ tree->type = Node_array_tree;
+ }
+ return TRUE;
+}
+
+
+/* tree_find --- locate an interger subscript in the HAT */
+
+static inline NODE **
+tree_find(NODE *tree, long k, int i)
+{
+ NODE *tn;
+
+ assert(tree->nodes != NULL);
+ tn = tree->nodes[i];
+ if (tn != NULL) {
+ if (tn->type == Node_array_tree)
+ return tree_exists(tn, k);
+ return leaf_exists(tn, k);
+ }
+ return NULL;
+}
+
+
+/* tree_list --- return a list of items in the HAT */
+
+static long
+tree_list(NODE *tree, NODE **list, unsigned int flags)
+{
+ NODE *tn;
+ size_t j, cj, hsize;
+ long k = 0;
+
+ assert(list != NULL);
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
+
+ for (j = 0; j < hsize; j++) {
+ cj = (flags & ADESC) ? (hsize - 1 - j) : j;
+ tn = tree->nodes[cj];
+ if (tn == NULL)
+ continue;
+ if (tn->type == Node_array_tree)
+ k += tree_list(tn, list + k, flags);
+ else
+ k += leaf_list(tn, list + k, flags);
+ if ((flags & ADELETE) != 0 && k >= 1)
+ return k;
+ }
+ return k;
+}
+
+
+/* tree_copy --- duplicate a HAT */
+
+static void
+tree_copy(NODE *newsymb, NODE *tree, NODE *newtree)
+{
+ NODE **old, **new;
+ size_t j, hsize;
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
+
+ emalloc(new, NODE **, hsize * sizeof(NODE *), "tree_copy");
+ memset(new, '\0', hsize * sizeof(NODE *));
+ newtree->nodes = new;
+ newtree->array_base = tree->array_base;
+ newtree->array_size = tree->array_size;
+ newtree->table_size = tree->table_size;
+ newtree->flags = tree->flags;
+
+ old = tree->nodes;
+ for (j = 0; j < hsize; j++) {
+ if (old[j] == NULL)
+ continue;
+ if (old[j]->type == Node_array_tree) {
+ new[j] = make_node(Node_array_tree);
+ tree_copy(newsymb, old[j], new[j]);
+ } else {
+ new[j] = make_node(Node_array_leaf);
+ leaf_copy(newsymb, old[j], new[j]);
+ }
+ }
+}
+
+
+/* tree_info --- print index, value info */
+
+static void
+tree_info(NODE *tree, NODE *ndump, const char *aname)
+{
+ NODE *tn;
+ size_t j, hsize;
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
+
+ for (j = 0; j < hsize; j++) {
+ tn = tree->nodes[j];
+ if (tn == NULL)
+ continue;
+ if (tn->type == Node_array_tree)
+ tree_info(tn, ndump, aname);
+ else
+ leaf_info(tn, ndump, aname);
+ }
+}
+
+
+/* tree_kilobytes --- calculate memory consumption of a HAT */
+
+static size_t
+tree_kilobytes(NODE *tree)
+{
+ NODE *tn;
+ size_t j, hsize;
+ size_t sz = 0;
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
+ for (j = 0; j < hsize; j++) {
+ tn = tree->nodes[j];
+ if (tn == NULL)
+ continue;
+ sz += sizeof(NODE); /* Node_array_tree or Node_array_leaf */
+ if (tn->type == Node_array_tree)
+ sz += tree_kilobytes(tn);
+ }
+ sz += hsize * sizeof(NODE *); /* tree->nodes */
+ return sz;
+}
+
+#ifdef ARRAYDEBUG
+
+/* tree_print --- print the HAT structures */
+
+static void
+tree_print(NODE *tree, size_t bi, int indent_level)
+{
+ NODE *tn;
+ size_t j, hsize;
+
+ indent(indent_level);
+
+ hsize = tree->array_size;
+ if ((tree->flags & HALFHAT) != 0)
+ hsize /= 2;
- fprintf(output_fp, "%4u:%s[%4lu:%-4lu]\n", bi,
++ fprintf(output_fp, "%4lu:%s[%4lu:%-4lu]\n", bi,
+ (tree->flags & HALFHAT) ? "HH" : "H",
+ (unsigned long) hsize, (unsigned long)
tree->table_size);
+
+ for (j = 0; j < hsize; j++) {
+ tn = tree->nodes[j];
+ if (tn == NULL)
+ continue;
+ if (tn->type == Node_array_tree)
+ tree_print(tn, j, indent_level + 1);
+ else
+ leaf_print(tn, j, indent_level + 1);
+ }
+}
+#endif
+
+/*--------------------- leaf (linear 1-D) array --------------------*/
+
+/* leaf_lookup --- find an integer subscript in the array; Install it if
+ it isn't there.
+*/
+
+static inline NODE **
+leaf_lookup(NODE *symbol, NODE *array, long k, long size, long base)
+{
+ NODE **lhs;
+
+ if (array->nodes == NULL) {
+ array->table_size = 0; /* sanity */
+ array->array_size = size;
+ array->array_base = base;
+ emalloc(array->nodes, NODE **, size * sizeof(NODE *),
"leaf_lookup");
+ memset(array->nodes, '\0', size * sizeof(NODE *));
+ symbol->array_capacity += size;
+ }
+
+ lhs = array->nodes + (k - base); /* leaf element */
+ if (*lhs == NULL) {
+ array->table_size++; /* one more element in leaf array */
+ *lhs = dupnode(Nnull_string);
+ }
+ return lhs;
+}
+
+
+/* leaf_exists --- check if the array contains an integer subscript */
+
+static inline NODE **
+leaf_exists(NODE *array, long k)
+{
+ NODE **lhs;
+ lhs = array->nodes + (k - array->array_base);
+ return (*lhs != NULL) ? lhs : NULL;
+}
+
+
+/* leaf_clear --- flush all values in the array */
+
+static void
+leaf_clear(NODE *array)
+{
+ long i, size = array->array_size;
+ NODE *r;
+
+ for (i = 0; i < size; i++) {
+ r = array->nodes[i];
+ if (r == NULL)
+ continue;
+ if (r->type == Node_var_array) {
+ assoc_clear(r); /* recursively clear all
sub-arrays */
+ efree(r->vname);
+ freenode(r);
+ } else
+ unref(r);
+ }
+ efree(array->nodes);
+ array->nodes = NULL;
+ array->array_size = array->table_size = 0;
+}
+
+
+/* leaf_remove --- remove an integer subscript from the array */
+
+static int
+leaf_remove(NODE *symbol, NODE *array, long k)
+{
+ NODE **lhs;
+
+ lhs = array->nodes + (k - array->array_base);
+ if (*lhs == NULL)
+ return FALSE;
+ *lhs = NULL;
+ if (--array->table_size == 0) {
+ efree(array->nodes);
+ array->nodes = NULL;
+ symbol->array_capacity -= array->array_size;
+ array->array_size = 0; /* sanity */
+ }
+ return TRUE;
+}
+
+
+/* leaf_copy --- duplicate a leaf array */
+
+static void
+leaf_copy(NODE *newsymb, NODE *array, NODE *newarray)
+{
+ NODE **old, **new;
+ long size, i;
+
+ size = array->array_size;
+ emalloc(new, NODE **, size * sizeof(NODE *), "leaf_copy");
+ memset(new, '\0', size * sizeof(NODE *));
+ newarray->nodes = new;
+ newarray->array_size = size;
+ newarray->array_base = array->array_base;
+ newarray->flags = array->flags;
+ newarray->table_size = array->table_size;
+
+ old = array->nodes;
+ for (i = 0; i < size; i++) {
+ if (old[i] == NULL)
+ continue;
+ if (old[i]->type == Node_val)
+ new[i] = dupnode(old[i]);
+ else {
+ NODE *r;
+ r = make_array();
+ r->vname = estrdup(old[i]->vname,
strlen(old[i]->vname));
+ r->parent_array = newsymb;
+ new[i] = assoc_copy(old[i], r);
+ }
+ }
+}
+
+
+/* leaf_list --- return a list of items */
+
+static long
+leaf_list(NODE *array, NODE **list, unsigned int flags)
+{
+ NODE *r, *subs;
+ long num, i, ci, k = 0;
+ long size = array->array_size;
+ static char buf[100];
+
+ for (i = 0; i < size; i++) {
+ ci = (flags & ADESC) ? (size - 1 - i) : i;
+ r = array->nodes[ci];
+ if (r == NULL)
+ continue;
+
+ /* index */
+ num = array->array_base + ci;
+ if (flags & AISTR) {
+ sprintf(buf, "%ld", num);
+ subs = make_string(buf, strlen(buf));
+ subs->numbr = num;
+ subs->flags |= (NUMCUR|NUMINT);
+ } else {
+ subs = make_number((AWKNUM) num);
+ subs->flags |= (INTIND|NUMINT);
+ }
+ list[k++] = subs;
+
+ /* value */
+ if (flags & AVALUE) {
+ if (r->type == Node_val) {
+ if ((flags & AVNUM) != 0)
+ (void) force_number(r);
+ else if ((flags & AVSTR) != 0)
+ r = force_string(r);
+ }
+ list[k++] = r;
+ }
+ if ((flags & ADELETE) != 0 && k >= 1)
+ return k;
+ }
+
+ return k;
+}
+
+
+/* leaf_info --- print index, value info */
+
+static void
+leaf_info(NODE *array, NODE *ndump, const char *aname)
+{
+ NODE *subs, *val;
+ size_t i, size;
+
+ size = array->array_size;
+
+ subs = make_number((AWKNUM) 0.0);
+ subs->flags |= (INTIND|NUMINT);
+ for (i = 0; i < size; i++) {
+ val = array->nodes[i];
+ if (val == NULL)
+ continue;
+ subs->numbr = array->array_base + i;
+ assoc_info(subs, val, ndump, aname);
+ }
+ unref(subs);
+}
+
+#ifdef ARRAYDEBUG
+
+/* leaf_print --- print the leaf-array structure */
+
+
+static void
+leaf_print(NODE *array, size_t bi, int indent_level)
+{
+ indent(indent_level);
- fprintf(output_fp, "%4u:L[%4lu:%-4lu]\n", bi,
++ fprintf(output_fp, "%4lu:L[%4lu:%-4lu]\n", bi,
+ (unsigned long) array->array_size,
+ (unsigned long) array->table_size);
+}
+#endif
diff --cc doc/gawk.info
index 619faff,0606273..b92d1b8
--- a/doc/gawk.info
+++ b/doc/gawk.info
@@@ -27438,389 -27450,389 +27438,775 @@@ Inde
Tag Table:
++<<<<<<< HEAD
+Node: Top1345
+Node: Foreword33439
+Node: Preface37784
+Ref: Preface-Footnote-140837
+Ref: Preface-Footnote-240943
+Node: History41175
+Node: Names43566
+Ref: Names-Footnote-145043
+Node: This Manual45115
+Ref: This Manual-Footnote-150062
+Node: Conventions50162
+Node: Manual History52296
+Ref: Manual History-Footnote-155566
+Ref: Manual History-Footnote-255607
+Node: How To Contribute55681
+Node: Acknowledgments56825
+Node: Getting Started61156
+Node: Running gawk63535
+Node: One-shot64721
+Node: Read Terminal65946
+Ref: Read Terminal-Footnote-167596
+Ref: Read Terminal-Footnote-267872
+Node: Long68043
+Node: Executable Scripts69419
+Ref: Executable Scripts-Footnote-171288
+Ref: Executable Scripts-Footnote-271390
+Node: Comments71841
+Node: Quoting74308
+Node: DOS Quoting78931
+Node: Sample Data Files79606
+Node: Very Simple82638
+Node: Two Rules87237
+Node: More Complex89384
+Ref: More Complex-Footnote-192314
+Node: Statements/Lines92399
+Ref: Statements/Lines-Footnote-196861
+Node: Other Features97126
+Node: When98054
+Node: Invoking Gawk100201
+Node: Command Line101586
+Node: Options102369
+Ref: Options-Footnote-1115806
+Node: Other Arguments115831
+Node: Naming Standard Input118489
+Node: Environment Variables119583
+Node: AWKPATH Variable120027
+Ref: AWKPATH Variable-Footnote-1122624
+Node: Other Environment Variables122884
+Node: Exit Status125224
+Node: Include Files125899
+Node: Obsolete129384
+Node: Undocumented130070
+Node: Regexp130311
+Node: Regexp Usage131700
+Node: Escape Sequences133726
+Node: Regexp Operators139489
+Ref: Regexp Operators-Footnote-1146686
+Ref: Regexp Operators-Footnote-2146833
+Node: Bracket Expressions146931
+Ref: table-char-classes148821
+Node: GNU Regexp Operators151344
+Node: Case-sensitivity155067
+Ref: Case-sensitivity-Footnote-1158035
+Ref: Case-sensitivity-Footnote-2158270
+Node: Leftmost Longest158378
+Node: Computed Regexps159579
+Node: Reading Files162989
+Node: Records164930
+Ref: Records-Footnote-1173604
+Node: Fields173641
+Ref: Fields-Footnote-1176674
+Node: Nonconstant Fields176760
+Node: Changing Fields178962
+Node: Field Separators184940
+Node: Default Field Splitting187569
+Node: Regexp Field Splitting188686
+Node: Single Character Fields192028
+Node: Command Line Field Separator193087
+Node: Field Splitting Summary196528
+Ref: Field Splitting Summary-Footnote-1199720
+Node: Constant Size199821
+Node: Splitting By Content204405
+Ref: Splitting By Content-Footnote-1208131
+Node: Multiple Line208171
+Ref: Multiple Line-Footnote-1214018
+Node: Getline214197
+Node: Plain Getline216425
+Node: Getline/Variable218514
+Node: Getline/File219655
+Node: Getline/Variable/File220977
+Ref: Getline/Variable/File-Footnote-1222576
+Node: Getline/Pipe222663
+Node: Getline/Variable/Pipe225223
+Node: Getline/Coprocess226330
+Node: Getline/Variable/Coprocess227573
+Node: Getline Notes228287
+Node: Getline Summary230229
+Ref: table-getline-variants230572
+Node: Command line directories231428
+Node: Printing232053
+Node: Print233684
+Node: Print Examples235021
+Node: Output Separators237805
+Node: OFMT239565
+Node: Printf240923
+Node: Basic Printf241829
+Node: Control Letters243368
+Node: Format Modifiers247180
+Node: Printf Examples253189
+Node: Redirection255904
+Node: Special Files262888
+Node: Special FD263421
+Ref: Special FD-Footnote-1267046
+Node: Special Network267120
+Node: Special Caveats267970
+Node: Close Files And Pipes268766
+Ref: Close Files And Pipes-Footnote-1275789
+Ref: Close Files And Pipes-Footnote-2275937
+Node: Expressions276087
+Node: Values277219
+Node: Constants277895
+Node: Scalar Constants278575
+Ref: Scalar Constants-Footnote-1279434
+Node: Nondecimal-numbers279616
+Node: Regexp Constants282675
+Node: Using Constant Regexps283150
+Node: Variables286205
+Node: Using Variables286860
+Node: Assignment Options288584
+Node: Conversion290456
+Ref: table-locale-affects295832
+Ref: Conversion-Footnote-1296456
+Node: All Operators296565
+Node: Arithmetic Ops297195
+Node: Concatenation299700
+Ref: Concatenation-Footnote-1302493
+Node: Assignment Ops302613
+Ref: table-assign-ops307601
+Node: Increment Ops309009
+Node: Truth Values and Conditions312479
+Node: Truth Values313562
+Node: Typing and Comparison314611
+Node: Variable Typing315400
+Ref: Variable Typing-Footnote-1319297
+Node: Comparison Operators319419
+Ref: table-relational-ops319829
+Node: POSIX String Comparison323378
+Ref: POSIX String Comparison-Footnote-1324334
+Node: Boolean Ops324472
+Ref: Boolean Ops-Footnote-1328550
+Node: Conditional Exp328641
+Node: Function Calls330373
+Node: Precedence333967
+Node: Locales337636
+Node: Patterns and Actions338725
+Node: Pattern Overview339779
+Node: Regexp Patterns341445
+Node: Expression Patterns341988
+Node: Ranges345673
+Node: BEGIN/END348639
+Node: Using BEGIN/END349401
+Ref: Using BEGIN/END-Footnote-1352132
+Node: I/O And BEGIN/END352238
+Node: BEGINFILE/ENDFILE354520
+Node: Empty357413
+Node: Using Shell Variables357729
+Node: Action Overview360014
+Node: Statements362371
+Node: If Statement364225
+Node: While Statement365724
+Node: Do Statement367768
+Node: For Statement368924
+Node: Switch Statement372076
+Node: Break Statement374173
+Node: Continue Statement376163
+Node: Next Statement377950
+Node: Nextfile Statement380340
+Node: Exit Statement382885
+Node: Built-in Variables385301
+Node: User-modified386396
+Ref: User-modified-Footnote-1394422
+Node: Auto-set394484
+Ref: Auto-set-Footnote-1403775
+Node: ARGC and ARGV403980
+Node: Arrays407831
+Node: Array Basics409336
+Node: Array Intro410047
+Node: Reference to Elements414365
+Node: Assigning Elements416635
+Node: Array Example417126
+Node: Scanning an Array418858
+Node: Delete421524
+Ref: Delete-Footnote-1423959
+Node: Numeric Array Subscripts424016
+Node: Uninitialized Subscripts426199
+Node: Multi-dimensional427827
+Node: Multi-scanning430921
+Node: Arrays of Arrays432505
+Node: Functions437082
+Node: Built-in437904
+Node: Calling Built-in438982
+Node: Numeric Functions440970
+Ref: Numeric Functions-Footnote-1444735
+Ref: Numeric Functions-Footnote-2445092
+Ref: Numeric Functions-Footnote-3445140
+Node: String Functions445409
+Ref: String Functions-Footnote-1468906
+Ref: String Functions-Footnote-2469035
+Ref: String Functions-Footnote-3469283
+Node: Gory Details469370
+Ref: table-sub-escapes471049
+Ref: table-sub-posix-92472403
+Ref: table-sub-proposed473746
+Ref: table-posix-sub475096
+Ref: table-gensub-escapes476642
+Ref: Gory Details-Footnote-1477849
+Ref: Gory Details-Footnote-2477900
+Node: I/O Functions478051
+Ref: I/O Functions-Footnote-1484706
+Node: Time Functions484853
+Ref: Time Functions-Footnote-1495745
+Ref: Time Functions-Footnote-2495813
+Ref: Time Functions-Footnote-3495971
+Ref: Time Functions-Footnote-4496082
+Ref: Time Functions-Footnote-5496194
+Ref: Time Functions-Footnote-6496421
+Node: Bitwise Functions496687
+Ref: table-bitwise-ops497245
+Ref: Bitwise Functions-Footnote-1501405
+Node: Type Functions501589
+Node: I18N Functions502059
+Node: User-defined503686
+Node: Definition Syntax504490
+Ref: Definition Syntax-Footnote-1509400
+Node: Function Example509469
+Node: Function Caveats512063
+Node: Calling A Function512484
+Node: Variable Scope513599
+Node: Pass By Value/Reference515574
+Node: Return Statement519014
+Node: Dynamic Typing521995
+Node: Indirect Calls522730
+Node: Internationalization532415
+Node: I18N and L10N533841
+Node: Explaining gettext534527
+Ref: Explaining gettext-Footnote-1539593
+Ref: Explaining gettext-Footnote-2539777
+Node: Programmer i18n539942
+Node: Translator i18n544142
+Node: String Extraction544935
+Ref: String Extraction-Footnote-1545896
+Node: Printf Ordering545982
+Ref: Printf Ordering-Footnote-1548766
+Node: I18N Portability548830
+Ref: I18N Portability-Footnote-1551279
+Node: I18N Example551342
+Ref: I18N Example-Footnote-1553977
+Node: Gawk I18N554049
+Node: Advanced Features554666
+Node: Nondecimal Data556179
+Node: Array Sorting557762
+Node: Controlling Array Traversal558462
+Node: Controlling Scanning With A Function559209
+Node: Controlling Scanning566912
+Ref: Controlling Scanning-Footnote-1570713
+Node: Array Sorting Functions571029
+Ref: Array Sorting Functions-Footnote-1574545
+Ref: Array Sorting Functions-Footnote-2574638
+Node: Two-way I/O574832
+Ref: Two-way I/O-Footnote-1580264
+Node: TCP/IP Networking580334
+Node: Profiling583178
+Node: Library Functions590652
+Ref: Library Functions-Footnote-1593659
+Node: Library Names593830
+Ref: Library Names-Footnote-1597301
+Ref: Library Names-Footnote-2597521
+Node: General Functions597607
+Node: Strtonum Function598560
+Node: Assert Function601490
+Node: Round Function604816
+Node: Cliff Random Function606359
+Node: Ordinal Functions607375
+Ref: Ordinal Functions-Footnote-1610445
+Ref: Ordinal Functions-Footnote-2610697
+Node: Join Function610906
+Ref: Join Function-Footnote-1612677
+Node: Gettimeofday Function612877
+Node: Data File Management616592
+Node: Filetrans Function617224
+Node: Rewind Function621363
+Node: File Checking622750
+Node: Empty Files623844
+Node: Ignoring Assigns626074
+Node: Getopt Function627627
+Ref: Getopt Function-Footnote-1638931
+Node: Passwd Functions639134
+Ref: Passwd Functions-Footnote-1648109
+Node: Group Functions648197
+Node: Walking Arrays656281
+Node: Sample Programs657850
+Node: Running Examples658515
+Node: Clones659243
+Node: Cut Program660467
+Node: Egrep Program670312
+Ref: Egrep Program-Footnote-1678085
+Node: Id Program678195
+Node: Split Program681811
+Ref: Split Program-Footnote-1685330
+Node: Tee Program685458
+Node: Uniq Program688261
+Node: Wc Program695690
+Ref: Wc Program-Footnote-1699956
+Ref: Wc Program-Footnote-2700156
+Node: Miscellaneous Programs700248
+Node: Dupword Program701436
+Node: Alarm Program703467
+Node: Translate Program708216
+Ref: Translate Program-Footnote-1712603
+Ref: Translate Program-Footnote-2712831
+Node: Labels Program712965
+Ref: Labels Program-Footnote-1716336
+Node: Word Sorting716420
+Node: History Sorting720304
+Node: Extract Program722143
+Ref: Extract Program-Footnote-1729626
+Node: Simple Sed729754
+Node: Igawk Program732816
+Ref: Igawk Program-Footnote-1747973
+Ref: Igawk Program-Footnote-2748174
+Node: Anagram Program748312
+Node: Signature Program751380
+Node: Debugger752480
+Node: Debugging753391
+Node: Debugging Concepts753804
+Node: Debugging Terms755660
+Node: Awk Debugging758283
+Node: Sample dgawk session759175
+Node: dgawk invocation759667
+Node: Finding The Bug760849
+Node: List of Debugger Commands767335
+Node: Breakpoint Control768646
+Node: Dgawk Execution Control772282
+Node: Viewing And Changing Data775633
+Node: Dgawk Stack778970
+Node: Dgawk Info780430
+Node: Miscellaneous Dgawk Commands784378
+Node: Readline Support789806
+Node: Dgawk Limitations790644
+Node: Language History792833
+Node: V7/SVR3.1794345
+Node: SVR4796666
+Node: POSIX798108
+Node: BTL799116
+Node: POSIX/GNU799850
+Node: Common Extensions805001
+Node: Ranges and Locales806108
+Ref: Ranges and Locales-Footnote-1810715
+Node: Contributors810936
+Node: Installation815198
+Node: Gawk Distribution816092
+Node: Getting816576
+Node: Extracting817402
+Node: Distribution contents819094
+Node: Unix Installation824316
+Node: Quick Installation824933
+Node: Additional Configuration Options826895
+Node: Configuration Philosophy828372
+Node: Non-Unix Installation830714
+Node: PC Installation831172
+Node: PC Binary Installation832471
+Node: PC Compiling834319
+Node: PC Testing837263
+Node: PC Using838439
+Node: Cygwin842624
+Node: MSYS843624
+Node: VMS Installation844138
+Node: VMS Compilation844741
+Ref: VMS Compilation-Footnote-1845748
+Node: VMS Installation Details845806
+Node: VMS Running847441
+Node: VMS Old Gawk849048
+Node: Bugs849522
++=======
+ Node: Top1346
+ Node: Foreword33440
+ Node: Preface37785
+ Ref: Preface-Footnote-140838
+ Ref: Preface-Footnote-240944
+ Node: History41176
+ Node: Names43567
+ Ref: Names-Footnote-145044
+ Node: This Manual45116
+ Ref: This Manual-Footnote-150063
+ Node: Conventions50163
+ Node: Manual History52297
+ Ref: Manual History-Footnote-155567
+ Ref: Manual History-Footnote-255608
+ Node: How To Contribute55682
+ Node: Acknowledgments56826
+ Node: Getting Started61157
+ Node: Running gawk63536
+ Node: One-shot64722
+ Node: Read Terminal65947
+ Ref: Read Terminal-Footnote-167597
+ Ref: Read Terminal-Footnote-267873
+ Node: Long68044
+ Node: Executable Scripts69420
+ Ref: Executable Scripts-Footnote-171289
+ Ref: Executable Scripts-Footnote-271391
+ Node: Comments71842
+ Node: Quoting74309
+ Node: DOS Quoting78932
+ Node: Sample Data Files79607
+ Node: Very Simple82639
+ Node: Two Rules87238
+ Node: More Complex89385
+ Ref: More Complex-Footnote-192315
+ Node: Statements/Lines92400
+ Ref: Statements/Lines-Footnote-196862
+ Node: Other Features97127
+ Node: When98055
+ Node: Invoking Gawk100202
+ Node: Command Line101587
+ Node: Options102370
+ Ref: Options-Footnote-1115807
+ Node: Other Arguments115832
+ Node: Naming Standard Input118490
+ Node: Environment Variables119584
+ Node: AWKPATH Variable120028
+ Ref: AWKPATH Variable-Footnote-1122625
+ Node: Other Environment Variables122885
+ Node: Exit Status125225
+ Node: Include Files125900
+ Node: Obsolete129385
+ Node: Undocumented130071
+ Node: Regexp130312
+ Node: Regexp Usage131701
+ Node: Escape Sequences133727
+ Node: Regexp Operators139490
+ Ref: Regexp Operators-Footnote-1146687
+ Ref: Regexp Operators-Footnote-2146834
+ Node: Bracket Expressions146932
+ Ref: table-char-classes148822
+ Node: GNU Regexp Operators151345
+ Node: Case-sensitivity155068
+ Ref: Case-sensitivity-Footnote-1158036
+ Ref: Case-sensitivity-Footnote-2158271
+ Node: Leftmost Longest158379
+ Node: Computed Regexps159580
+ Node: Reading Files162990
+ Node: Records164931
+ Ref: Records-Footnote-1173605
+ Node: Fields173642
+ Ref: Fields-Footnote-1176675
+ Node: Nonconstant Fields176761
+ Node: Changing Fields178963
+ Node: Field Separators184941
+ Node: Default Field Splitting187570
+ Node: Regexp Field Splitting188687
+ Node: Single Character Fields192029
+ Node: Command Line Field Separator193088
+ Node: Field Splitting Summary196529
+ Ref: Field Splitting Summary-Footnote-1199721
+ Node: Constant Size199822
+ Node: Splitting By Content204406
+ Ref: Splitting By Content-Footnote-1208132
+ Node: Multiple Line208172
+ Ref: Multiple Line-Footnote-1214019
+ Node: Getline214198
+ Node: Plain Getline216426
+ Node: Getline/Variable218515
+ Node: Getline/File219656
+ Node: Getline/Variable/File220978
+ Ref: Getline/Variable/File-Footnote-1222577
+ Node: Getline/Pipe222664
+ Node: Getline/Variable/Pipe225224
+ Node: Getline/Coprocess226331
+ Node: Getline/Variable/Coprocess227574
+ Node: Getline Notes228288
+ Node: Getline Summary230230
+ Ref: table-getline-variants230573
+ Node: Command line directories231429
+ Node: Printing232054
+ Node: Print233685
+ Node: Print Examples235022
+ Node: Output Separators237806
+ Node: OFMT239566
+ Node: Printf240924
+ Node: Basic Printf241830
+ Node: Control Letters243369
+ Node: Format Modifiers247181
+ Node: Printf Examples253190
+ Node: Redirection255905
+ Node: Special Files262889
+ Node: Special FD263422
+ Ref: Special FD-Footnote-1267047
+ Node: Special Network267121
+ Node: Special Caveats267971
+ Node: Close Files And Pipes268767
+ Ref: Close Files And Pipes-Footnote-1275790
+ Ref: Close Files And Pipes-Footnote-2275938
+ Node: Expressions276088
+ Node: Values277220
+ Node: Constants277896
+ Node: Scalar Constants278576
+ Ref: Scalar Constants-Footnote-1279435
+ Node: Nondecimal-numbers279617
+ Node: Regexp Constants282676
+ Node: Using Constant Regexps283151
+ Node: Variables286206
+ Node: Using Variables286861
+ Node: Assignment Options288585
+ Node: Conversion290457
+ Ref: table-locale-affects295833
+ Ref: Conversion-Footnote-1296457
+ Node: All Operators296566
+ Node: Arithmetic Ops297196
+ Node: Concatenation299701
+ Ref: Concatenation-Footnote-1302494
+ Node: Assignment Ops302614
+ Ref: table-assign-ops307602
+ Node: Increment Ops309010
+ Node: Truth Values and Conditions312480
+ Node: Truth Values313563
+ Node: Typing and Comparison314612
+ Node: Variable Typing315401
+ Ref: Variable Typing-Footnote-1319298
+ Node: Comparison Operators319420
+ Ref: table-relational-ops319830
+ Node: POSIX String Comparison323379
+ Ref: POSIX String Comparison-Footnote-1324335
+ Node: Boolean Ops324473
+ Ref: Boolean Ops-Footnote-1328551
+ Node: Conditional Exp328642
+ Node: Function Calls330374
+ Node: Precedence333968
+ Node: Locales337637
+ Node: Patterns and Actions338726
+ Node: Pattern Overview339780
+ Node: Regexp Patterns341446
+ Node: Expression Patterns341989
+ Node: Ranges345674
+ Node: BEGIN/END348640
+ Node: Using BEGIN/END349402
+ Ref: Using BEGIN/END-Footnote-1352133
+ Node: I/O And BEGIN/END352239
+ Node: BEGINFILE/ENDFILE354521
+ Node: Empty357414
+ Node: Using Shell Variables357730
+ Node: Action Overview360015
+ Node: Statements362372
+ Node: If Statement364226
+ Node: While Statement365725
+ Node: Do Statement367769
+ Node: For Statement368925
+ Node: Switch Statement372077
+ Node: Break Statement374174
+ Node: Continue Statement376164
+ Node: Next Statement377951
+ Node: Nextfile Statement380341
+ Node: Exit Statement382886
+ Node: Built-in Variables385302
+ Node: User-modified386397
+ Ref: User-modified-Footnote-1394423
+ Node: Auto-set394485
+ Ref: Auto-set-Footnote-1403776
+ Node: ARGC and ARGV403981
+ Node: Arrays407832
+ Node: Array Basics409337
+ Node: Array Intro410048
+ Node: Reference to Elements414366
+ Node: Assigning Elements416636
+ Node: Array Example417127
+ Node: Scanning an Array418859
+ Node: Delete421525
+ Ref: Delete-Footnote-1423960
+ Node: Numeric Array Subscripts424017
+ Node: Uninitialized Subscripts426200
+ Node: Multi-dimensional427828
+ Node: Multi-scanning430922
+ Node: Arrays of Arrays432506
+ Node: Functions437083
+ Node: Built-in437905
+ Node: Calling Built-in438983
+ Node: Numeric Functions440971
+ Ref: Numeric Functions-Footnote-1444736
+ Ref: Numeric Functions-Footnote-2445093
+ Ref: Numeric Functions-Footnote-3445141
+ Node: String Functions445410
+ Ref: String Functions-Footnote-1468907
+ Ref: String Functions-Footnote-2469036
+ Ref: String Functions-Footnote-3469284
+ Node: Gory Details469371
+ Ref: table-sub-escapes471050
+ Ref: table-sub-posix-92472404
+ Ref: table-sub-proposed473747
+ Ref: table-posix-sub475097
+ Ref: table-gensub-escapes476643
+ Ref: Gory Details-Footnote-1477850
+ Ref: Gory Details-Footnote-2477901
+ Node: I/O Functions478052
+ Ref: I/O Functions-Footnote-1484707
+ Node: Time Functions484854
+ Ref: Time Functions-Footnote-1495746
+ Ref: Time Functions-Footnote-2495814
+ Ref: Time Functions-Footnote-3495972
+ Ref: Time Functions-Footnote-4496083
+ Ref: Time Functions-Footnote-5496195
+ Ref: Time Functions-Footnote-6496422
+ Node: Bitwise Functions496688
+ Ref: table-bitwise-ops497246
+ Ref: Bitwise Functions-Footnote-1501406
+ Node: Type Functions501590
+ Node: I18N Functions502060
+ Node: User-defined503687
+ Node: Definition Syntax504491
+ Ref: Definition Syntax-Footnote-1509401
+ Node: Function Example509470
+ Node: Function Caveats512064
+ Node: Calling A Function512485
+ Node: Variable Scope513600
+ Node: Pass By Value/Reference515575
+ Node: Return Statement519015
+ Node: Dynamic Typing521996
+ Node: Indirect Calls522731
+ Node: Internationalization532416
+ Node: I18N and L10N533842
+ Node: Explaining gettext534528
+ Ref: Explaining gettext-Footnote-1539594
+ Ref: Explaining gettext-Footnote-2539778
+ Node: Programmer i18n539943
+ Node: Translator i18n544143
+ Node: String Extraction544936
+ Ref: String Extraction-Footnote-1545897
+ Node: Printf Ordering545983
+ Ref: Printf Ordering-Footnote-1548767
+ Node: I18N Portability548831
+ Ref: I18N Portability-Footnote-1551280
+ Node: I18N Example551343
+ Ref: I18N Example-Footnote-1553978
+ Node: Gawk I18N554050
+ Node: Advanced Features554667
+ Node: Nondecimal Data556180
+ Node: Array Sorting557763
+ Node: Controlling Array Traversal558463
+ Node: Controlling Scanning With A Function559210
+ Node: Controlling Scanning566913
+ Ref: Controlling Scanning-Footnote-1570714
+ Node: Array Sorting Functions571030
+ Ref: Array Sorting Functions-Footnote-1574546
+ Ref: Array Sorting Functions-Footnote-2574639
+ Node: Two-way I/O574833
+ Ref: Two-way I/O-Footnote-1580265
+ Node: TCP/IP Networking580335
+ Node: Profiling583179
+ Node: Library Functions590653
+ Ref: Library Functions-Footnote-1593660
+ Node: Library Names593831
+ Ref: Library Names-Footnote-1597302
+ Ref: Library Names-Footnote-2597522
+ Node: General Functions597608
+ Node: Strtonum Function598561
+ Node: Assert Function601491
+ Node: Round Function604817
+ Node: Cliff Random Function606360
+ Node: Ordinal Functions607376
+ Ref: Ordinal Functions-Footnote-1610446
+ Ref: Ordinal Functions-Footnote-2610698
+ Node: Join Function610907
+ Ref: Join Function-Footnote-1612678
+ Node: Gettimeofday Function612878
+ Node: Data File Management616593
+ Node: Filetrans Function617225
+ Node: Rewind Function621364
+ Node: File Checking622751
+ Node: Empty Files623845
+ Node: Ignoring Assigns626075
+ Node: Getopt Function627628
+ Ref: Getopt Function-Footnote-1638932
+ Node: Passwd Functions639135
+ Ref: Passwd Functions-Footnote-1648110
+ Node: Group Functions648198
+ Node: Walking Arrays656282
+ Node: Sample Programs657851
+ Node: Running Examples658516
+ Node: Clones659244
+ Node: Cut Program660468
+ Node: Egrep Program670313
+ Ref: Egrep Program-Footnote-1678086
+ Node: Id Program678196
+ Node: Split Program681812
+ Ref: Split Program-Footnote-1685331
+ Node: Tee Program685459
+ Node: Uniq Program688262
+ Node: Wc Program695691
+ Ref: Wc Program-Footnote-1699957
+ Ref: Wc Program-Footnote-2700157
+ Node: Miscellaneous Programs700249
+ Node: Dupword Program701437
+ Node: Alarm Program703468
+ Node: Translate Program708217
+ Ref: Translate Program-Footnote-1712604
+ Ref: Translate Program-Footnote-2712832
+ Node: Labels Program712966
+ Ref: Labels Program-Footnote-1716337
+ Node: Word Sorting716421
+ Node: History Sorting720305
+ Node: Extract Program722144
+ Ref: Extract Program-Footnote-1729627
+ Node: Simple Sed729755
+ Node: Igawk Program732817
+ Ref: Igawk Program-Footnote-1747974
+ Ref: Igawk Program-Footnote-2748175
+ Node: Anagram Program748313
+ Node: Signature Program751381
+ Node: Debugger752481
+ Node: Debugging753392
+ Node: Debugging Concepts753805
+ Node: Debugging Terms755661
+ Node: Awk Debugging758284
+ Node: Sample dgawk session759176
+ Node: dgawk invocation759668
+ Node: Finding The Bug760850
+ Node: List of Debugger Commands767336
+ Node: Breakpoint Control768647
+ Node: Dgawk Execution Control772283
+ Node: Viewing And Changing Data775634
+ Node: Dgawk Stack778971
+ Node: Dgawk Info780431
+ Node: Miscellaneous Dgawk Commands784379
+ Node: Readline Support789807
+ Node: Dgawk Limitations790645
+ Node: Language History792834
+ Node: V7/SVR3.1794346
+ Node: SVR4796667
+ Node: POSIX798109
+ Node: BTL799117
+ Node: POSIX/GNU799851
+ Node: Common Extensions805002
+ Node: Ranges and Locales806109
+ Ref: Ranges and Locales-Footnote-1810716
+ Node: Contributors810937
+ Node: Installation815199
+ Node: Gawk Distribution816093
+ Node: Getting816577
+ Node: Extracting817403
+ Node: Distribution contents819095
+ Node: Unix Installation824317
+ Node: Quick Installation824934
+ Node: Additional Configuration Options826896
+ Node: Configuration Philosophy828373
+ Node: Non-Unix Installation830715
+ Node: PC Installation831173
+ Node: PC Binary Installation832472
+ Node: PC Compiling834320
+ Node: PC Testing837264
+ Node: PC Using838440
+ Node: Cygwin842625
+ Node: MSYS843625
+ Node: VMS Installation844139
+ Node: VMS Compilation844742
+ Ref: VMS Compilation-Footnote-1845749
+ Node: VMS Installation Details845807
+ Node: VMS Running847442
+ Node: VMS Old Gawk849049
+ Node: Bugs849523
++>>>>>>> gawk-4.0-stable
Node: Other Versions853375
Node: Notes858656
Node: Compatibility Mode859348
@@@ -27830,26 -27842,26 +28216,50 @@@ Node: Adding Code86236
Node: New Ports868335
Node: Dynamic Extensions872448
Node: Internals873824
++<<<<<<< HEAD
+Node: Plugin License882343
+Node: Sample Library882977
+Node: Internal File Description883663
+Node: Internal File Ops887378
+Ref: Internal File Ops-Footnote-1892102
+Node: Using Internal File Ops892242
+Node: Future Extensions894619
+Node: Basic Concepts897123
+Node: Basic High Level897880
+Ref: Basic High Level-Footnote-1901915
+Node: Basic Data Typing902100
+Node: Floating Point Issues906625
+Node: String Conversion Precision907708
+Ref: String Conversion Precision-Footnote-1909408
+Node: Unexpected Results909517
+Node: POSIX Floating Point Problems911343
+Ref: POSIX Floating Point Problems-Footnote-1915048
+Node: Glossary915086
+Node: Copying940062
+Node: GNU Free Documentation License977619
+Node: Index1002756
++=======
+ Node: Plugin License882927
+ Node: Sample Library883561
+ Node: Internal File Description884247
+ Node: Internal File Ops887962
+ Ref: Internal File Ops-Footnote-1892743
+ Node: Using Internal File Ops892883
+ Node: Future Extensions895260
+ Node: Basic Concepts897764
+ Node: Basic High Level898521
+ Ref: Basic High Level-Footnote-1902556
+ Node: Basic Data Typing902741
+ Node: Floating Point Issues907266
+ Node: String Conversion Precision908349
+ Ref: String Conversion Precision-Footnote-1910049
+ Node: Unexpected Results910158
+ Node: POSIX Floating Point Problems911984
+ Ref: POSIX Floating Point Problems-Footnote-1915689
+ Node: Glossary915727
+ Node: Copying940703
+ Node: GNU Free Documentation License978260
+ Node: Index1003397
++>>>>>>> gawk-4.0-stable
End Tag Table
diff --cc int_array.c
index 9d85273,0000000..fd58de2
mode 100644,000000..100644
--- a/int_array.c
+++ b/int_array.c
@@@ -1,826 -1,0 +1,826 @@@
+/*
+ * int_array.c - routines for arrays of integer indices.
+ */
+
+/*
+ * Copyright (C) 1986, 1988, 1989, 1991-2011 the Free Software Foundation,
Inc.
+ *
+ * This file is part of GAWK, the GNU implementation of the
+ * AWK Programming Language.
+ *
+ * GAWK is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GAWK is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
USA
+ */
+
+#include "awk.h"
+
+extern FILE *output_fp;
+extern void indent(int indent_level);
+extern NODE **is_integer(NODE *symbol, NODE *subs);
+
+static size_t INT_CHAIN_MAX = 2;
+
+static NODE **int_array_init(NODE *symbol, NODE *subs);
+static NODE **int_lookup(NODE *symbol, NODE *subs);
+static NODE **int_exists(NODE *symbol, NODE *subs);
+static NODE **int_clear(NODE *symbol, NODE *subs);
+static NODE **int_remove(NODE *symbol, NODE *subs);
+static NODE **int_list(NODE *symbol, NODE *t);
+static NODE **int_copy(NODE *symbol, NODE *newsymb);
+static NODE **int_dump(NODE *symbol, NODE *ndump);
+
+#ifdef ARRAYDEBUG
+static NODE **int_option(NODE *opt, NODE *val);
+#endif
+
+static uint32_t int_hash(uint32_t k, uint32_t hsize);
+static inline NODE **int_find(NODE *symbol, long k, uint32_t hash1);
+static NODE **int_insert(NODE *symbol, long k, uint32_t hash1);
+static void grow_int_table(NODE *symbol);
+
+array_ptr int_array_func[] = {
+ int_array_init,
+ is_integer,
+ int_lookup,
+ int_exists,
+ int_clear,
+ int_remove,
+ int_list,
+ int_copy,
+ int_dump,
+#ifdef ARRAYDEBUG
+ int_option,
+#endif
+};
+
+
+/* int_array_init --- check relevant environment variables */
+
+static NODE **
+int_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED)
+{
+ long newval;
+
+ if ((newval = getenv_long("INT_CHAIN_MAX")) > 0)
+ INT_CHAIN_MAX = newval;
+ return (NODE **) ! NULL;
+}
+
+
+/* is_integer --- check if subscript is an integer */
+
+NODE **
+is_integer(NODE *symbol, NODE *subs)
+{
+ long l;
+ AWKNUM d;
+
+ if (subs == Nnull_string)
+ return NULL;
+
+ if ((subs->flags & NUMINT) != 0)
+ return (NODE **) ! NULL;
+
+ if ((subs->flags & NUMBER) != 0) {
+ d = subs->numbr;
+ if (d <= INT32_MAX && d >= INT32_MIN && d == (int32_t) d) {
+ subs->flags |= NUMINT;
+ return (NODE **) ! NULL;
+ }
+ return NULL;
+ }
+
+ /* a[3]=1; print "3" in a -- TRUE
+ * a[3]=1; print "+3" in a -- FALSE
+ * a[3]=1; print "03" in a -- FALSE
+ * a[-3]=1; print "-3" in a -- TRUE
+ */
+
+ if ((subs->flags & (STRING|STRCUR)) != 0) {
+ char *cp = subs->stptr, *cpend, *ptr;
+ char save;
+ size_t len = subs->stlen;
+
+ if (len == 0 || (! isdigit((unsigned char) *cp) && *cp != '-'))
+ return NULL;
+ if (len > 1 &&
+ ((*cp == '0') /* "00", "011" .. */
+ || (*cp == '-' && *(cp + 1) == '0') /*
"-0", "-011" .. */
+ )
+ )
+ return NULL;
+ if (len == 1 && *cp != '-') { /* single digit */
+ subs->numbr = (long) (*cp - '0');
+ if ((subs->flags & MAYBE_NUM) != 0) {
+ subs->flags &= ~MAYBE_NUM;
+ subs->flags |= NUMBER;
+ }
+ subs->flags |= (NUMCUR|NUMINT);
+ return (NODE **) ! NULL;
+ }
+
+ cpend = cp + len;
+ save = *cpend;
+ *cpend = '\0';
+
+ errno = 0;
+ l = strtol(cp, & ptr, 10);
+ *cpend = save;
+ if (errno != 0 || ptr != cpend)
+ return NULL;
+ subs->numbr = l;
+ if ((subs->flags & MAYBE_NUM) != 0) {
+ subs->flags &= ~MAYBE_NUM;
+ subs->flags |= NUMBER;
+ }
+ subs->flags |= NUMCUR;
+ if (l <= INT32_MAX && l >= INT32_MIN) {
+ subs->flags |= NUMINT;
+ return (NODE **) ! NULL;
+ }
+ }
+ return NULL;
+}
+
+
+/* int_lookup --- Find SYMBOL[SUBS] in the assoc array. Install it with
value ""
+ * if it isn't there. Returns a pointer ala get_lhs to where its value is
stored.
+ */
+
+static NODE **
+int_lookup(NODE *symbol, NODE *subs)
+{
+ uint32_t hash1;
+ long k;
+ unsigned long size;
+ NODE **lhs;
+ NODE *xn;
+
+ /* N.B: symbol->table_size is the total # of non-integers
(symbol->xarray)
+ * and integer elements. Also, symbol->xarray must have at least
one
+ * item in it, and can not exist if there are no integer elements.
+ * In that case, symbol->xarray is promoted to 'symbol' (See
int_remove).
+ */
+
+
+ if (! is_integer(symbol, subs)) {
+ xn = symbol->xarray;
+ if (xn == NULL) {
+ xn = symbol->xarray = make_array();
+ xn->vname = symbol->vname; /* shallow copy */
+ xn->flags |= XARRAY;
+ } else if ((lhs = xn->aexists(xn, subs)) != NULL)
+ return lhs;
+ symbol->table_size++;
+ return assoc_lookup(xn, subs);
+ }
+
+ k = subs->numbr;
+ if (symbol->buckets == NULL)
+ grow_int_table(symbol);
+
+ hash1 = int_hash(k, symbol->array_size);
+ if ((lhs = int_find(symbol, k, hash1)) != NULL)
+ return lhs;
+
+ /* It's not there, install it */
+
+ symbol->table_size++;
+
+ /* first see if we would need to grow the array, before installing */
+ size = symbol->table_size;
+ if ((xn = symbol->xarray) != NULL)
+ size -= xn->table_size;
+
+ if ((symbol->flags & ARRAYMAXED) == 0
+ && (size / symbol->array_size) > INT_CHAIN_MAX) {
+ grow_int_table(symbol);
+ /* have to recompute hash value for new size */
+ hash1 = int_hash(k, symbol->array_size);
+ }
+
+ return int_insert(symbol, k, hash1);
+}
+
+
+/* int_exists --- test whether the array element symbol[subs] exists or not,
+ * return pointer to value if it does.
+ */
+
+static NODE **
+int_exists(NODE *symbol, NODE *subs)
+{
+ long k;
+ uint32_t hash1;
+
+ if (! is_integer(symbol, subs)) {
+ NODE *xn = symbol->xarray;
+ if (xn == NULL)
+ return NULL;
+ return xn->aexists(xn, subs);
+ }
+ if (symbol->buckets == NULL)
+ return NULL;
+
+ k = subs->numbr;
+ hash1 = int_hash(k, symbol->array_size);
+ return int_find(symbol, k, hash1);
+}
+
+/* int_clear --- flush all the values in symbol[] */
+
+static NODE **
+int_clear(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)
+{
+ unsigned long i;
+ int j;
+ BUCKET *b, *next;
+ NODE *r;
+
+ if (symbol->xarray != NULL) {
+ NODE *xn = symbol->xarray;
+ assoc_clear(xn);
+ freenode(xn);
+ symbol->xarray = NULL;
+ }
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = next) {
+ next = b->ainext;
+ for (j = 0; j < b->aicount; j++) {
+ r = b->aivalue[j];
+ if (r->type == Node_var_array) {
+ assoc_clear(r); /* recursively clear
all sub-arrays */
+ efree(r->vname);
+ freenode(r);
+ } else
+ unref(r);
+ }
+ freebucket(b);
+ }
+ symbol->buckets[i] = NULL;
+ }
+ if (symbol->buckets != NULL)
+ efree(symbol->buckets);
+ init_array(symbol); /* re-initialize symbol */
+ symbol->flags &= ~ARRAYMAXED;
+ return NULL;
+}
+
+
+/* int_remove --- If SUBS is already in the table, remove it. */
+
+static NODE **
+int_remove(NODE *symbol, NODE *subs)
+{
+ uint32_t hash1;
+ BUCKET *b, *prev = NULL;
+ long k;
+ int i;
+ NODE *xn = symbol->xarray;
+
+ assert(symbol->buckets != NULL);
+
+ if (! is_integer(symbol, subs)) {
+ if (xn == NULL || xn->aremove(xn, subs) == NULL)
+ return NULL;
+ if (xn->table_size == 0) {
+ freenode(xn);
+ symbol->xarray = NULL;
+ }
+ symbol->table_size--;
+ assert(symbol->table_size > 0);
+ return (NODE **) ! NULL;
+ }
+
+ k = subs->numbr;
+ hash1 = int_hash(k, symbol->array_size);
+
+ for (b = symbol->buckets[hash1]; b != NULL; prev = b, b = b->ainext) {
+ for (i = 0; i < b->aicount; i++) {
+ if (k != b->ainum[i])
+ continue;
+
+ /* item found */
+ if (i == 0 && b->aicount == 2) {
+ /* removing the 1st item; move 2nd item from
position 1 to 0 */
+
+ b->ainum[0] = b->ainum[1];
+ b->aivalue[0] = b->aivalue[1];
+ } /* else
+ removing the only item or the 2nd item */
+
+ goto removed;
+ }
+ }
+
+ if (b == NULL) /* item not in array */
+ return NULL;
+
+removed:
+ b->aicount--;
+
+ if (b->aicount == 0) {
+ /* detach bucket */
+ if (prev != NULL)
+ prev->ainext = b->ainext;
+ else
+ symbol->buckets[hash1] = b->ainext;
+
+ /* delete bucket */
+ freebucket(b);
+ } else if (b != symbol->buckets[hash1]) {
+ BUCKET *head = symbol->buckets[hash1];
+
+ assert(b->aicount == 1);
+ /* move the last element from head
+ * to bucket to make it full.
+ */
+ i = --head->aicount; /* head has one less element */
+ b->ainum[1] = head->ainum[i];
+ b->aivalue[1] = head->aivalue[i];
+ b->aicount++; /* bucket has one more element */
+ if (i == 0) {
+ /* head is now empty; delete head */
+ symbol->buckets[hash1] = head->ainext;
+ freebucket(head);
+ }
+ } /* else
+ do nothing */
+
+ symbol->table_size--;
+ if (xn == NULL && symbol->table_size == 0) {
+ efree(symbol->buckets);
+ init_array(symbol); /* re-initialize array 'symbol' */
+ symbol->flags &= ~ARRAYMAXED;
+ } else if (xn != NULL && symbol->table_size == xn->table_size) {
+ /* promote xn (str_array) to symbol */
+ xn->flags &= ~XARRAY;
+ xn->parent_array = symbol->parent_array;
+ efree(symbol->buckets);
+ *symbol = *xn;
+ freenode(xn);
+ }
+
+ return (NODE **) ! NULL; /* return success */
+}
+
+
+/* int_copy --- duplicate input array "symbol" */
+
+static NODE **
+int_copy(NODE *symbol, NODE *newsymb)
+{
+ BUCKET **old, **new, **pnew;
+ BUCKET *chain, *newchain;
+ int j;
+ unsigned long i, cursize;
+
+ assert(symbol->buckets != NULL);
+
+ /* find the current hash size */
+ cursize = symbol->array_size;
+
+ /* allocate new table */
+ emalloc(new, BUCKET **, cursize * sizeof(BUCKET *), "int_copy");
+ memset(new, '\0', cursize * sizeof(BUCKET *));
+
+ old = symbol->buckets;
+
+ for (i = 0; i < cursize; i++) {
+ for (chain = old[i], pnew = & new[i]; chain != NULL;
+ chain = chain->ainext
+ ) {
+ getbucket(newchain);
+ newchain->aicount = chain->aicount;
+ for (j = 0; j < chain->aicount; j++) {
+ NODE *oldval;
+
+ /*
+ * copy the corresponding key and
+ * value from the original input list
+ */
+ newchain->ainum[j] = chain->ainum[j];
+
+ oldval = chain->aivalue[j];
+ if (oldval->type == Node_val)
+ newchain->aivalue[j] = dupnode(oldval);
+ else {
+ NODE *r;
+ r = make_array();
+ r->vname = estrdup(oldval->vname,
strlen(oldval->vname));
+ r->parent_array = newsymb;
+ newchain->aivalue[j] =
assoc_copy(oldval, r);
+ }
+ }
+
+ *pnew = newchain;
+ pnew = & newchain->ainext;
+ }
+ }
+
+ if (symbol->xarray != NULL) {
+ NODE *xn, *n;
+ xn = symbol->xarray;
+ n = make_array();
+ n->vname = newsymb->vname; /* shallow copy */
+ (void) xn->acopy(xn, n);
+ newsymb->xarray = n;
+ } else
+ newsymb->xarray = NULL;
+
+ newsymb->table_size = symbol->table_size;
+ newsymb->buckets = new;
+ newsymb->array_size = cursize;
+ newsymb->flags = symbol->flags;
+
+ return NULL;
+}
+
+
+/* int_list --- return a list of array items */
+
+static NODE**
+int_list(NODE *symbol, NODE *t)
+{
+ NODE **list = NULL;
+ unsigned long num_elems, list_size, i, k = 0;
+ BUCKET *b;
+ NODE *r, *subs, *xn;
+ int j, elem_size = 1;
+ long num;
+ static char buf[100];
+
+ assert(symbol->table_size > 0);
+
+ num_elems = symbol->table_size;
+ if ((t->flags & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))
+ num_elems = 1;
+
+ if ((t->flags & (AINDEX|AVALUE)) == (AINDEX|AVALUE))
+ elem_size = 2;
+ list_size = elem_size * num_elems;
+
+ if (symbol->xarray != NULL) {
+ xn = symbol->xarray;
+ list = xn->alist(xn, t);
+ assert(list != NULL);
+ if (num_elems == 1 || num_elems == xn->table_size)
+ return list;
+ erealloc(list, NODE **, list_size * sizeof(NODE *), "int_list");
+ k = elem_size * xn->table_size;
+ } else
+ emalloc(list, NODE **, list_size * sizeof(NODE *), "int_list");
+
+ /* populate it */
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = b->ainext) {
+ for (j = 0; j < b->aicount; j++) {
+ /* index */
+ num = b->ainum[j];
+ if (t->flags & AISTR) {
+ sprintf(buf, "%ld", num);
+ subs = make_string(buf, strlen(buf));
+ subs->numbr = num;
+ subs->flags |= (NUMCUR|NUMINT);
+ } else {
+ subs = make_number((AWKNUM) num);
+ subs->flags |= (INTIND|NUMINT);
+ }
+ list[k++] = subs;
+
+ /* value */
+ if (t->flags & AVALUE) {
+ r = b->aivalue[j];
+ if (r->type == Node_val) {
+ if ((t->flags & AVNUM) != 0)
+ (void) force_number(r);
+ else if ((t->flags & AVSTR) !=
0)
+ r = force_string(r);
+ }
+ list[k++] = r;
+ }
+
+ if (k >= list_size)
+ return list;
+ }
+ }
+ }
+ return list;
+}
+
+
+/* int_kilobytes --- calculate memory consumption of the assoc array */
+
+AWKNUM
+int_kilobytes(NODE *symbol)
+{
+ unsigned long i, bucket_cnt = 0;
+ BUCKET *b;
+ AWKNUM kb;
+ extern AWKNUM str_kilobytes(NODE *symbol);
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = b->ainext)
+ bucket_cnt++;
+ }
+ kb = (((AWKNUM) bucket_cnt) * sizeof (BUCKET) +
+ ((AWKNUM) symbol->array_size) * sizeof (BUCKET *)) /
1024.0;
+
+ if (symbol->xarray != NULL)
+ kb += str_kilobytes(symbol->xarray);
+
+ return kb;
+}
+
+
+/* int_dump --- dump array info */
+
+static NODE **
+int_dump(NODE *symbol, NODE *ndump)
+{
+#define HCNT 31
+
+ int indent_level;
+ BUCKET *b;
+ NODE *xn = NULL;
+ unsigned long str_size = 0, int_size = 0;
+ unsigned long i;
+ size_t j, bucket_cnt;
+ static size_t hash_dist[HCNT + 1];
+
+ indent_level = ndump->alevel;
+
+ if (symbol->xarray != NULL) {
+ xn = symbol->xarray;
+ str_size = xn->table_size;
+ }
+ int_size = symbol->table_size - str_size;
+
+ if ((symbol->flags & XARRAY) == 0)
+ fprintf(output_fp, "%s `%s'\n",
+ (symbol->parent_array == NULL) ? "array" :
"sub-array",
+ array_vname(symbol));
+
+ indent_level++;
+ indent(indent_level);
+ fprintf(output_fp, "array_func: int_array_func\n");
+ if (symbol->flags != 0) {
+ indent(indent_level);
+ fprintf(output_fp, "flags: %s\n", flags2str(symbol->flags));
+ }
+ indent(indent_level);
- fprintf(output_fp, "INT_CHAIN_MAX: %u\n", INT_CHAIN_MAX);
++ fprintf(output_fp, "INT_CHAIN_MAX: %lu\n", INT_CHAIN_MAX);
+ indent(indent_level);
+ fprintf(output_fp, "array_size: %lu (int)\n", (unsigned long)
symbol->array_size);
+ indent(indent_level);
+ fprintf(output_fp, "table_size: %lu (total), %lu (int), %lu (str)\n",
+ (unsigned long) symbol->table_size, int_size, str_size);
+ indent(indent_level);
+ fprintf(output_fp, "Avg # of items per chain (int): %.2g\n",
+ ((AWKNUM) int_size) / symbol->array_size);
+
+ indent(indent_level);
+ fprintf(output_fp, "memory: %.2g kB (total)\n", int_kilobytes(symbol));
+
+ /* hash value distribution */
+
+ memset(hash_dist, '\0', (HCNT + 1) * sizeof(size_t));
+ for (i = 0; i < symbol->array_size; i++) {
+ bucket_cnt = 0;
+ for (b = symbol->buckets[i]; b != NULL; b = b->ainext)
+ bucket_cnt += b->aicount;
+ if (bucket_cnt >= HCNT)
+ bucket_cnt = HCNT;
+ hash_dist[bucket_cnt]++;
+ }
+
+ indent(indent_level);
+ fprintf(output_fp, "Hash distribution:\n");
+ indent_level++;
+ for (j = 0; j <= HCNT; j++) {
+ if (hash_dist[j] > 0) {
+ indent(indent_level);
+ if (j == HCNT)
+ fprintf(output_fp, "[>=%lu]:%lu\n",
+ (unsigned long) HCNT, (unsigned long)
hash_dist[j]);
+ else
+ fprintf(output_fp, "[%lu]:%lu\n",
+ (unsigned long) j, (unsigned long)
hash_dist[j]);
+ }
+ }
+ indent_level--;
+
+ /* dump elements */
+
+ if (ndump->adepth >= 0) {
+ NODE *subs;
+ const char *aname;
+
+ fprintf(output_fp, "\n");
+
+ aname = make_aname(symbol);
+ subs = make_number((AWKNUM) 0);
+ subs->flags |= (INTIND|NUMINT);
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = b->ainext) {
+ for (j = 0; j < b->aicount; j++) {
+ subs->numbr = b->ainum[j];
+ assoc_info(subs, b->aivalue[j], ndump,
aname);
+ }
+ }
+ }
+ unref(subs);
+ }
+
+ if (xn != NULL) {
+ fprintf(output_fp, "\n");
+ xn->adump(xn, ndump);
+ }
+
+ return NULL;
+
+#undef HCNT
+}
+
+
+/* int_hash --- calculate the hash function of the integer subs */
+
+static uint32_t
+int_hash(uint32_t k, uint32_t hsize)
+{
+
+/* Code snippet copied from:
+ * Hash functions (http://www.azillionmonkeys.com/qed/hash.html).
+ * Copyright 2004-2008 by Paul Hsieh. Licenced under LGPL 2.1.
+ */
+
+ /* This is the final mixing function used by Paul Hsieh
+ * in SuperFastHash.
+ */
+
+ k ^= k << 3;
+ k += k >> 5;
+ k ^= k << 4;
+ k += k >> 17;
+ k ^= k << 25;
+ k += k >> 6;
+
+ if (k >= hsize)
+ k %= hsize;
+ return k;
+}
+
+/* int_find --- locate symbol[subs] */
+
+static inline NODE **
+int_find(NODE *symbol, long k, uint32_t hash1)
+{
+ BUCKET *b;
+ int i;
+
+ assert(symbol->buckets != NULL);
+ for (b = symbol->buckets[hash1]; b != NULL; b = b->ainext) {
+ for (i = 0; i < b->aicount; i++) {
+ if (b->ainum[i] == k)
+ return (b->aivalue + i);
+ }
+ }
+ return NULL;
+}
+
+
+/* int_insert --- install subs in the assoc array */
+
+static NODE **
+int_insert(NODE *symbol, long k, uint32_t hash1)
+{
+ BUCKET *b;
+ int i;
+
+ b = symbol->buckets[hash1];
+
+ /* Only the first bucket in the chain can be partially full,
+ * but is never empty.
+ */
+
+ if (b == NULL || (i = b->aicount) == 2) {
+ getbucket(b);
+ b->aicount = 0;
+ b->ainext = symbol->buckets[hash1];
+ symbol->buckets[hash1] = b;
+ i = 0;
+ }
+
+ b->ainum[i] = k;
+ b->aivalue[i] = dupnode(Nnull_string);
+ b->aicount++;
+ return & b->aivalue[i];
+}
+
+
+/* grow_int_table --- grow the hash table */
+
+static void
+grow_int_table(NODE *symbol)
+{
+ BUCKET **old, **new;
+ BUCKET *chain, *next;
+ int i, j;
+ unsigned long oldsize, newsize, k;
+
+ /*
+ * This is an array of primes. We grow the table by an order of
+ * magnitude each time (not just doubling) so that growing is a
+ * rare operation. We expect, on average, that it won't happen
+ * more than twice. The final size is also chosen to be small
+ * enough so that MS-DOG mallocs can handle it. When things are
+ * very large (> 8K), we just double more or less, instead of
+ * just jumping from 8K to 64K.
+ */
+
+ static const unsigned long sizes[] = {
+ 13, 127, 1021, 8191, 16381, 32749, 65497,
+ 131101, 262147, 524309, 1048583, 2097169,
+ 4194319, 8388617, 16777259, 33554467,
+ 67108879, 134217757, 268435459, 536870923,
+ 1073741827
+ };
+
+ /* find next biggest hash size */
+ newsize = oldsize = symbol->array_size;
+
+ for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
+ if (oldsize < sizes[i]) {
+ newsize = sizes[i];
+ break;
+ }
+ }
+ if (newsize == oldsize) { /* table already at max (!) */
+ symbol->flags |= ARRAYMAXED;
+ return;
+ }
+
+ /* allocate new table */
+ emalloc(new, BUCKET **, newsize * sizeof(BUCKET *), "grow_int_table");
+ memset(new, '\0', newsize * sizeof(BUCKET *));
+
+ old = symbol->buckets;
+ symbol->buckets = new;
+ symbol->array_size = newsize;
+
+ /* brand new hash table */
+ if (old == NULL)
+ return; /* DO NOT initialize symbol->table_size */
+
+ /* old hash table there, move stuff to new, free old */
+ /* note that symbol->table_size does not change if an old array. */
+
+ for (k = 0; k < oldsize; k++) {
+ long num;
+ for (chain = old[k]; chain != NULL; chain = next) {
+ for (i = 0; i < chain->aicount; i++) {
+ num = chain->ainum[i];
+ *int_insert(symbol, num, int_hash(num,
newsize)) = chain->aivalue[i];
+ }
+ next = chain->ainext;
+ freebucket(chain);
+ }
+ }
+ efree(old);
+}
+
+
+#ifdef ARRAYDEBUG
+
+static NODE **
+int_option(NODE *opt, NODE *val)
+{
+ int newval;
+ NODE *tmp;
+ NODE **ret = (NODE **) ! NULL;
+
+ tmp = force_string(opt);
+ (void) force_number(val);
+ if (STREQ(tmp->stptr, "INT_CHAIN_MAX")) {
+ newval = (int) val->numbr;
+ if (newval > 0)
+ INT_CHAIN_MAX = newval;
+ } else
+ ret = NULL;
+ return ret;
+}
+#endif
diff --cc str_array.c
index f7f35ef,0000000..8fb6ba8
mode 100644,000000..100644
--- a/str_array.c
+++ b/str_array.c
@@@ -1,759 -1,0 +1,759 @@@
+/*
+ * str_array.c - routines for associative arrays of string indices.
+ */
+
+/*
+ * Copyright (C) 1986, 1988, 1989, 1991-2011 the Free Software Foundation,
Inc.
+ *
+ * This file is part of GAWK, the GNU implementation of the
+ * AWK Programming Language.
+ *
+ * GAWK is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GAWK is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
USA
+ */
+
+#include "awk.h"
+
+/*
+ * Tree walks (``for (iggy in foo)'') and array deletions use expensive
+ * linear searching. So what we do is start out with small arrays and
+ * grow them as needed, so that our arrays are hopefully small enough,
+ * most of the time, that they're pretty full and we're not looking at
+ * wasted space.
+ *
+ * The decision is made to grow the array if the average chain length is
+ * ``too big''. This is defined as the total number of entries in the table
+ * divided by the size of the array being greater than some constant.
+ *
+ * 11/2002: We make the constant a variable, so that it can be tweaked
+ * via environment variable.
+ * 11/2002: Modern machines are bigger, cut this down from 10.
+ */
+
+static size_t STR_CHAIN_MAX = 2;
+
+extern FILE *output_fp;
+extern void indent(int indent_level);
+
+static NODE **str_array_init(NODE *symbol, NODE *subs);
+static NODE **str_lookup(NODE *symbol, NODE *subs);
+static NODE **str_exists(NODE *symbol, NODE *subs);
+static NODE **str_clear(NODE *symbol, NODE *subs);
+static NODE **str_remove(NODE *symbol, NODE *subs);
+static NODE **str_list(NODE *symbol, NODE *subs);
+static NODE **str_copy(NODE *symbol, NODE *newsymb);
+static NODE **str_dump(NODE *symbol, NODE *ndump);
+
+#ifdef ARRAYDEBUG
+static NODE **str_option(NODE *opt, NODE *val);
+#endif
+
+
+array_ptr str_array_func[] = {
+ str_array_init,
+ (array_ptr) 0,
+ str_lookup,
+ str_exists,
+ str_clear,
+ str_remove,
+ str_list,
+ str_copy,
+ str_dump,
+#ifdef ARRAYDEBUG
+ str_option
+#endif
+};
+
+static inline NODE **str_find(NODE *symbol, NODE *s1, size_t code1, unsigned
long hash1);
+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 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;
+
+
+/* str_array_init --- check relevant environment variables */
+
+static NODE **
+str_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED)
+{
+ long newval;
+ const char *val;
+
+ 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;
+ return (NODE **) ! NULL;
+}
+
+
+/*
+ * assoc_lookup:
+ * Find SYMBOL[SUBS] in the assoc array. Install it with value "" if it
+ * isn't there. Returns a pointer ala get_lhs to where its value is stored.
+ *
+ * SYMBOL is the address of the node (or other pointer) being dereferenced.
+ * SUBS is a number or string used as the subscript.
+ */
+
+static NODE **
+str_lookup(NODE *symbol, NODE *subs)
+{
+ unsigned long hash1;
+ NODE **lhs;
+ BUCKET *b;
+ size_t code1;
+
+ subs = force_string(subs);
+
+ if (symbol->buckets == NULL)
+ grow_table(symbol);
+ hash1 = hash(subs->stptr, subs->stlen,
+ (unsigned long) symbol->array_size, & code1);
+ if ((lhs = str_find(symbol, subs, code1, hash1)) != NULL)
+ return lhs;
+
+ /* It's not there, install it. */
+ /* first see if we would need to grow the array, before installing */
+
+ symbol->table_size++;
+ if ((symbol->flags & ARRAYMAXED) == 0
+ && (symbol->table_size / symbol->array_size) >
STR_CHAIN_MAX) {
+ grow_table(symbol);
+ /* have to recompute hash value for new size */
+ hash1 = code1 % (unsigned long) symbol->array_size;
+ }
+
+ if (subs->stfmt != -1) {
+ NODE *tmp;
+
+ /*
+ * Need to freeze this string value --- it must never
+ * change, no matter what happens to the value
+ * that created it or to CONVFMT, etc.; So, get
+ * a private copy.
+ */
+
+ tmp = make_string(subs->stptr, subs->stlen);
+
+ /*
+ * Set the numeric value for the index if it's available. Useful
+ * for numeric sorting by index. Do this only if the numeric
+ * value is available, instead of all the time, since doing it
+ * all the time is a big performance hit for something that may
+ * never be used.
+ */
+
+ if (subs->flags & NUMCUR) {
+ tmp->numbr = subs->numbr;
+ tmp->flags |= NUMCUR;
+ }
+ subs = tmp;
+ } else {
+ /* string value already "frozen" */
+
+ subs = dupnode(subs);
+ }
+
+ getbucket(b);
+ b->ahnext = symbol->buckets[hash1];
+ symbol->buckets[hash1] = b;
+ b->ahname = subs;
+ b->ahname_str = subs->stptr;
+ b->ahname_len = subs->stlen;
+ b->ahvalue = dupnode(Nnull_string);
+ b->ahcode = code1;
+ return & (b->ahvalue);
+}
+
+/* str_exists --- test whether the array element symbol[subs] exists or not,
+ * return pointer to value if it does.
+ */
+
+static NODE **
+str_exists(NODE *symbol, NODE *subs)
+{
+ NODE **lhs;
+ unsigned long hash1;
+ size_t code1;
+
+ assert(symbol->table_size > 0);
+
+ subs = force_string(subs);
+ hash1 = hash(subs->stptr, subs->stlen, (unsigned long)
symbol->array_size, & code1);
+ lhs = str_find(symbol, subs, code1, hash1);
+ return lhs;
+}
+
+/* str_clear --- flush all the values in symbol[] */
+
+static NODE **
+str_clear(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)
+{
+ unsigned long i;
+ BUCKET *b, *next;
+ NODE *r;
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = next) {
+ next = b->ahnext;
+ r = b->ahvalue;
+ if (r->type == Node_var_array) {
+ assoc_clear(r); /* recursively clear all
sub-arrays */
+ efree(r->vname);
+ freenode(r);
+ } else
+ unref(r);
+ unref(b->ahname);
+ freebucket(b);
+ }
+ symbol->buckets[i] = NULL;
+ }
+
+ if (symbol->buckets != NULL)
+ efree(symbol->buckets);
+ init_array(symbol); /* re-initialize symbol */
+ symbol->flags &= ~ARRAYMAXED;
+ return NULL;
+}
+
+
+/* str_remove --- If SUBS is already in the table, remove it. */
+
+static NODE **
+str_remove(NODE *symbol, NODE *subs)
+{
+ unsigned long hash1;
+ BUCKET *b, *prev;
+ NODE *s2;
+ size_t s1_len;
+
+ assert(symbol->table_size > 0);
+
+ s2 = force_string(subs);
+ hash1 = hash(s2->stptr, s2->stlen, (unsigned long) symbol->array_size,
NULL);
+
+ for (b = symbol->buckets[hash1], prev = NULL; b != NULL;
+ prev = b, b = b->ahnext) {
+
+ /* Array indexes are strings; compare as such, always! */
+ s1_len = b->ahname_len;
+
+ if (s1_len != s2->stlen)
+ continue;
+ if (s1_len == 0 /* "" is a valid index */
+ || memcmp(b->ahname_str, s2->stptr, s1_len) == 0) {
+ /* item found */
+
+ unref(b->ahname);
+ if (prev != NULL)
+ prev->ahnext = b->ahnext;
+ else
+ symbol->buckets[hash1] = b->ahnext;
+
+ /* delete bucket */
+ freebucket(b);
+
+ /* one less element in array */
+ if (--symbol->table_size == 0) {
+ if (symbol->buckets != NULL)
+ efree(symbol->buckets);
+ init_array(symbol); /* re-initialize symbol
*/
+ symbol->flags &= ~ARRAYMAXED;
+ }
+
+ return (NODE **) ! NULL; /* return success */
+ }
+ }
+
+ return NULL;
+}
+
+
+/* str_copy --- duplicate input array "symbol" */
+
+static NODE **
+str_copy(NODE *symbol, NODE *newsymb)
+{
+ BUCKET **old, **new, **pnew;
+ BUCKET *chain, *newchain;
+ unsigned long cursize, i;
+
+ assert(symbol->table_size > 0);
+
+ /* find the current hash size */
+ cursize = symbol->array_size;
+
+ /* allocate new table */
+ emalloc(new, BUCKET **, cursize * sizeof(BUCKET *), "str_copy");
+ memset(new, '\0', cursize * sizeof(BUCKET *));
+
+ old = symbol->buckets;
+
+ for (i = 0; i < cursize; i++) {
+ for (chain = old[i], pnew = & new[i]; chain != NULL;
+ chain = chain->ahnext
+ ) {
+ NODE *oldval, *newsubs;
+
+ getbucket(newchain);
+
+ /*
+ * copy the corresponding name and
+ * value from the original input list
+ */
+
+ newsubs = newchain->ahname = dupnode(chain->ahname);
+ newchain->ahname_str = newsubs->stptr;
+ newchain->ahname_len = newsubs->stlen;
+
+ oldval = chain->ahvalue;
+ if (oldval->type == Node_val)
+ newchain->ahvalue = dupnode(oldval);
+ else {
+ NODE *r;
+
+ r = make_array();
+ r->vname = estrdup(oldval->vname,
strlen(oldval->vname));
+ r->parent_array = newsymb;
+ newchain->ahvalue = assoc_copy(oldval, r);
+ }
+ newchain->ahcode = chain->ahcode;
+
+ *pnew = newchain;
+ pnew = & newchain->ahnext;
+ }
+ }
+
+ newsymb->table_size = symbol->table_size;
+ newsymb->buckets = new;
+ newsymb->array_size = cursize;
+ newsymb->flags = symbol->flags;
+ return NULL;
+}
+
+
+/* str_list --- return a list of array items */
+
+static NODE**
+str_list(NODE *symbol, NODE *t)
+{
+ NODE **list;
+ NODE *subs, *val;
+ BUCKET *b;
+ unsigned long num_elems, list_size, i, k = 0;
+ int elem_size = 1;
+
+ assert(symbol->table_size > 0);
+
+ if ((t->flags & (AINDEX|AVALUE)) == (AINDEX|AVALUE))
+ elem_size = 2;
+
+ /* allocate space for array */
+ num_elems = symbol->table_size;
+ if ((t->flags & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))
+ num_elems = 1;
+ list_size = elem_size * num_elems;
+
+ emalloc(list, NODE **, list_size * sizeof(NODE *), "str_list");
+
+ /* populate it */
+
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = b->ahnext) {
+ /* index */
+ subs = b->ahname;
+ if (t->flags & AINUM)
+ (void) force_number(subs);
+ list[k++] = dupnode(subs);
+
+ /* value */
+ if (t->flags & AVALUE) {
+ val = b->ahvalue;
+ if (val->type == Node_val) {
+ if ((t->flags & AVNUM) != 0)
+ (void) force_number(val);
+ else if ((t->flags & AVSTR) != 0)
+ val = force_string(val);
+ }
+ list[k++] = val;
+ }
+ if (k >= list_size)
+ return list;
+ }
+ }
+ return list;
+}
+
+
+/* str_kilobytes --- calculate memory consumption of the assoc array */
+
+AWKNUM
+str_kilobytes(NODE *symbol)
+{
+ unsigned long bucket_cnt;
+ AWKNUM kb;
+
+ bucket_cnt = symbol->table_size;
+
+ /* This does not include extra memory for indices with stfmt != -1 */
+ kb = (((AWKNUM) bucket_cnt) * sizeof (BUCKET) +
+ ((AWKNUM) symbol->array_size) * sizeof (BUCKET *)) / 1024.0;
+ return kb;
+}
+
+
+/* str_dump --- dump array info */
+
+static NODE **
+str_dump(NODE *symbol, NODE *ndump)
+{
+#define HCNT 31
+
+ int indent_level;
+ unsigned long i, bucket_cnt;
+ BUCKET *b;
+ static size_t hash_dist[HCNT + 1];
+
+ indent_level = ndump->alevel;
+
+ if ((symbol->flags & XARRAY) == 0)
+ fprintf(output_fp, "%s `%s'\n",
+ (symbol->parent_array == NULL) ? "array" :
"sub-array",
+ array_vname(symbol));
+ indent_level++;
+ indent(indent_level);
+ fprintf(output_fp, "array_func: str_array_func\n");
+ if (symbol->flags != 0) {
+ indent(indent_level);
+ fprintf(output_fp, "flags: %s\n", flags2str(symbol->flags));
+ }
+ indent(indent_level);
- fprintf(output_fp, "STR_CHAIN_MAX: %u\n", STR_CHAIN_MAX);
++ fprintf(output_fp, "STR_CHAIN_MAX: %lu\n", STR_CHAIN_MAX);
+ indent(indent_level);
+ fprintf(output_fp, "array_size: %lu\n", (unsigned long)
symbol->array_size);
+ indent(indent_level);
+ fprintf(output_fp, "table_size: %lu\n", (unsigned long)
symbol->table_size);
+ indent(indent_level);
+ fprintf(output_fp, "Avg # of items per chain: %.2g\n",
+ ((AWKNUM) symbol->table_size) /
symbol->array_size);
+
+ indent(indent_level);
+ fprintf(output_fp, "memory: %.2g kB\n", str_kilobytes(symbol));
+
+ /* hash value distribution */
+
+ memset(hash_dist, '\0', (HCNT + 1) * sizeof(size_t));
+ for (i = 0; i < symbol->array_size; i++) {
+ bucket_cnt = 0;
+ for (b = symbol->buckets[i]; b != NULL; b = b->ahnext)
+ bucket_cnt++;
+ if (bucket_cnt >= HCNT)
+ bucket_cnt = HCNT;
+ hash_dist[bucket_cnt]++;
+ }
+
+ indent(indent_level);
+ fprintf(output_fp, "Hash distribution:\n");
+ indent_level++;
+ for (i = 0; i <= HCNT; i++) {
+ if (hash_dist[i] > 0) {
+ indent(indent_level);
+ if (i == HCNT)
+ fprintf(output_fp, "[>=%lu]:%lu\n",
+ (unsigned long) HCNT, (unsigned long)
hash_dist[i]);
+ else
+ fprintf(output_fp, "[%lu]:%lu\n",
+ (unsigned long) i, (unsigned long)
hash_dist[i]);
+ }
+ }
+ indent_level--;
+
+ /* dump elements */
+
+ if (ndump->adepth >= 0) {
+ const char *aname;
+
+ fprintf(output_fp, "\n");
+ aname = make_aname(symbol);
+ for (i = 0; i < symbol->array_size; i++) {
+ for (b = symbol->buckets[i]; b != NULL; b = b->ahnext)
+ assoc_info(b->ahname, b->ahvalue, ndump, aname);
+ }
+ }
+
+ return NULL;
+
+#undef HCNT
+}
+
+
+/* awk_hash --- calculate the hash function of the string in subs */
+
+static unsigned long
+awk_hash(const char *s, size_t len, unsigned long hsize, size_t *code)
+{
+ unsigned long h = 0;
+ unsigned long htmp;
+
+ /*
+ * Ozan Yigit's original sdbm hash, copied from Margo Seltzers
+ * db package.
+ *
+ * This is INCREDIBLY ugly, but fast. We break the string up into
+ * 8 byte units. On the first time through the loop we get the
+ * "leftover bytes" (strlen % 8). On every other iteration, we
+ * perform 8 HASHC's so we handle all 8 bytes. Essentially, this
+ * saves us 7 cmp & branch instructions. If this routine is
+ * heavily used enough, it's worth the ugly coding.
+ */
+
+ /*
+ * Even more speed:
+ * #define HASHC h = *s++ + 65599 * h
+ * Because 65599 = pow(2, 6) + pow(2, 16) - 1 we multiply by shifts
+ *
+ * 4/2011: Force the results to 32 bits, to get the same
+ * result on both 32- and 64-bit systems. This may be a
+ * bad idea.
+ */
+#define HASHC htmp = (h << 6); \
+ h = *s++ + htmp + (htmp << 10) - h ; \
+ htmp &= 0xFFFFFFFF; \
+ h &= 0xFFFFFFFF
+
+ h = 0;
+
+ /* "Duff's Device" */
+ if (len > 0) {
+ size_t loop = (len + 8 - 1) >> 3;
+
+ switch (len & (8 - 1)) {
+ case 0:
+ do { /* All fall throughs */
+ HASHC;
+ case 7: HASHC;
+ case 6: HASHC;
+ case 5: HASHC;
+ case 4: HASHC;
+ case 3: HASHC;
+ case 2: HASHC;
+ case 1: HASHC;
+ } while (--loop);
+ }
+ }
+
+ if (code != NULL)
+ *code = h;
+
+ if (h >= hsize)
+ h %= hsize;
+ return h;
+}
+
+
+/* str_find --- locate symbol[subs] */
+
+static inline NODE **
+str_find(NODE *symbol, NODE *s1, size_t code1, unsigned long hash1)
+{
+ BUCKET *b;
+ size_t s2_len;
+
+ for (b = symbol->buckets[hash1]; b != NULL; b = b->ahnext) {
+ /*
+ * This used to use cmp_nodes() here. That's wrong.
+ * Array indexes are strings; compare as such, always!
+ */
+ s2_len = b->ahname_len;
+
+ if (code1 == b->ahcode
+ && s1->stlen == s2_len
+ && (s2_len == 0 /* "" is a valid index */
+ || memcmp(s1->stptr, b->ahname_str, s2_len) ==
0)
+ )
+ return & (b->ahvalue);
+ }
+ return NULL;
+}
+
+
+/* grow_table --- grow a hash table */
+
+static void
+grow_table(NODE *symbol)
+{
+ BUCKET **old, **new;
+ BUCKET *chain, *next;
+ int i, j;
+ unsigned long oldsize, newsize, k;
+ unsigned long hash1;
+
+ /*
+ * This is an array of primes. We grow the table by an order of
+ * magnitude each time (not just doubling) so that growing is a
+ * rare operation. We expect, on average, that it won't happen
+ * more than twice. The final size is also chosen to be small
+ * enough so that MS-DOG mallocs can handle it. When things are
+ * very large (> 8K), we just double more or less, instead of
+ * just jumping from 8K to 64K.
+ */
+
+ static const unsigned long sizes[] = {
+ 13, 127, 1021, 8191, 16381, 32749, 65497,
+ 131101, 262147, 524309, 1048583, 2097169,
+ 4194319, 8388617, 16777259, 33554467,
+ 67108879, 134217757, 268435459, 536870923,
+ 1073741827
+ };
+
+ /* find next biggest hash size */
+ newsize = oldsize = symbol->array_size;
+
+ for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
+ if (oldsize < sizes[i]) {
+ newsize = sizes[i];
+ break;
+ }
+ }
+ if (newsize == oldsize) { /* table already at max (!) */
+ symbol->flags |= ARRAYMAXED;
+ return;
+ }
+
+ /* allocate new table */
+ emalloc(new, BUCKET **, newsize * sizeof(BUCKET *), "grow_table");
+ memset(new, '\0', newsize * sizeof(BUCKET *));
+
+ old = symbol->buckets;
+ symbol->buckets = new;
+ symbol->array_size = newsize;
+
+ /* brand new hash table, set things up and return */
+ if (old == NULL) {
+ symbol->table_size = 0;
+ return;
+ }
+
+ /* old hash table there, move stuff to new, free old */
+
+ /*
+ * note that symbol->table_size does not change if an old array,
+ * and is explicitly set to 0 if a new one.
+ */
+
+ for (k = 0; k < oldsize; k++) {
+ for (chain = old[k]; chain != NULL; chain = next) {
+ next = chain->ahnext;
+ hash1 = chain->ahcode % newsize;
+
+ /* remove from old list, add to new */
+ chain->ahnext = new[hash1];
+ new[hash1] = chain;
+ }
+ }
+ efree(old);
+}
+
+
+#ifdef ARRAYDEBUG
+
+static NODE **
+str_option(NODE *opt, NODE *val)
+{
+ int newval;
+ NODE *tmp;
+ NODE **ret = (NODE **) ! NULL;
+
+ tmp = force_string(opt);
+ (void) force_number(val);
+ if (STREQ(tmp->stptr, "STR_CHAIN_MAX")) {
+ newval = (int) val->numbr;
+ if (newval > 0)
+ STR_CHAIN_MAX = newval;
+ } else
+ ret = NULL;
+ return ret;
+}
+#endif
+
+
+/*
+From address@hidden Mon Oct 28 16:05:26 2002
+Date: Mon, 28 Oct 2002 13:33:03 +0100
+From: Paolo Bonzini <address@hidden>
+To: address@hidden
+Subject: Hash function
+Message-ID: <address@hidden>
+
+Here is the hash function I'm using in GNU Smalltalk. The scrambling is
+needed if you use powers of two as the table sizes. If you use primes it
+is not needed.
+
+To use double-hashing with power-of-two size, you should use the
+_gst_hash_string(str, len) as the primary hash and
+scramble(_gst_hash_string (str, len)) | 1 as the secondary hash.
+
+Paolo
+
+*/
+/*
+ * ADR: Slightly modified to work w/in the context of gawk.
+ */
+
+static unsigned long
+gst_hash_string(const char *str, size_t len, unsigned long hsize, size_t
*code)
+{
+ unsigned long hashVal = 1497032417; /* arbitrary value */
+ unsigned long ret;
+
+ while (len--) {
+ hashVal += *str++;
+ hashVal += (hashVal << 10);
+ hashVal ^= (hashVal >> 6);
+ }
+
+ ret = scramble(hashVal);
+
+ if (code != NULL)
+ *code = ret;
+
+ if (ret >= hsize)
+ ret %= hsize;
+
+ return ret;
+}
+
+static unsigned long
+scramble(unsigned long x)
+{
+ if (sizeof(long) == 4) {
+ int y = ~x;
+
+ x += (y << 10) | (y >> 22);
+ x += (x << 6) | (x >> 26);
+ x -= (x << 16) | (x >> 16);
+ } else {
+ x ^= (~x) >> 31;
+ x += (x << 21) | (x >> 11);
+ x += (x << 5) | (x >> 27);
+ x += (x << 27) | (x >> 5);
+ x += (x << 31);
+ }
+
+ return x;
+}
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 65 +++++
Makefile.am | 11 +
Makefile.in | 14 +-
README | 2 +-
README.git | 13 +-
aclocal.m4 | 26 --
array.c | 2 +-
awklib/Makefile.in | 1 -
builtin.c | 8 +-
cint_array.c | 4 +-
configh.in | 6 -
configure | 41 +---
configure.ac | 3 -
custom.h | 2 +-
dfa.c | 90 ++++++-
doc/Makefile.in | 1 -
doc/gawk.info | 412 +++++++++++++++++++++++++++++-
doc/gawk.texi | 3 +-
eval.c | 2 +-
int_array.c | 2 +-
pc/ChangeLog | 23 ++
pc/Makefile | 74 +++++-
pc/config.h | 746 +++++++++++++++++++++++++++++-----------------------
pc/config.sed | 279 ++++++++++++++++++++
pc/configpk.sed | 9 +
pc/gawkmisc.pc | 22 ++
pc/make-config.bat | 6 +
pc/popen.h | 4 +
po/da.gmo | Bin 48739 -> 48739 bytes
po/da.po | 196 +++++++-------
po/de.gmo | Bin 52166 -> 52166 bytes
po/de.po | 196 +++++++-------
po/es.gmo | Bin 51471 -> 51471 bytes
po/es.po | 196 +++++++-------
po/fi.gmo | Bin 51684 -> 51684 bytes
po/fi.po | 196 +++++++-------
po/fr.gmo | Bin 53311 -> 53311 bytes
po/fr.po | 196 +++++++-------
po/gawk.pot | 198 +++++++-------
po/it.gmo | Bin 44316 -> 44316 bytes
po/it.po | 196 +++++++-------
po/ja.gmo | Bin 55596 -> 55596 bytes
po/ja.po | 196 +++++++-------
po/nl.gmo | Bin 49267 -> 49267 bytes
po/nl.po | 196 +++++++-------
po/pl.gmo | Bin 50946 -> 50946 bytes
po/pl.po | 196 +++++++-------
po/sv.gmo | Bin 48752 -> 48752 bytes
po/sv.po | 196 +++++++-------
str_array.c | 2 +-
test/ChangeLog | 15 +
test/Makefile.am | 2 +-
test/Makefile.in | 3 +-
test/beginfile2.in | 4 +-
test/beginfile2.ok | 9 +-
test/beginfile2.sh | 38 ++--
vms/ChangeLog | 5 +
vms/vms-conf.h | 6 -
vms/vmstest.com | 7 +-
59 files changed, 2591 insertions(+), 1529 deletions(-)
create mode 100644 pc/config.sed
create mode 100644 pc/configpk.sed
create mode 100755 pc/make-config.bat
hooks/post-receive
--
gawk
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gawk-diffs] [SCM] gawk branch, master, updated. 44cd8b0b374419f77febc504b0053b87c894810c,
Arnold Robbins <=