|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* cint_array.c - routines for arrays of (mostly) consecutive positive integer indices.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* Copyright (C) 1986, 1988, 1989, 1991-2013, 2016, 2017,
|
|
Packit Service |
f629e6 |
* the Free Software Foundation, Inc.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* This file is part of GAWK, the GNU implementation of the
|
|
Packit Service |
f629e6 |
* AWK Programming Language.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* GAWK is free software; you can redistribute it and/or modify
|
|
Packit Service |
f629e6 |
* it under the terms of the GNU General Public License as published by
|
|
Packit Service |
f629e6 |
* the Free Software Foundation; either version 3 of the License, or
|
|
Packit Service |
f629e6 |
* (at your option) any later version.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* GAWK is distributed in the hope that it will be useful,
|
|
Packit Service |
f629e6 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
f629e6 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
f629e6 |
* GNU General Public License for more details.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
f629e6 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
f629e6 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#include "awk.h"
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#define INT32_BIT 32
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
extern FILE *output_fp;
|
|
Packit Service |
f629e6 |
extern void indent(int indent_level);
|
|
Packit Service |
f629e6 |
extern NODE **is_integer(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* NHAT --- maximum size of a leaf array (2^NHAT).
|
|
Packit Service |
f629e6 |
* THRESHOLD --- Maximum capacity waste; THRESHOLD >= 2^(NHAT + 1).
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static int NHAT = 10;
|
|
Packit Service |
f629e6 |
static long THRESHOLD;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* What is the optimium NHAT ? timing results suggest that 10 is a good choice,
|
|
Packit Service |
f629e6 |
* although differences aren't that significant for > 10.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **cint_array_init(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **is_uinteger(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **cint_lookup(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **cint_exists(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **cint_clear(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **cint_remove(NODE *symbol, NODE *subs);
|
|
Packit Service |
f629e6 |
static NODE **cint_list(NODE *symbol, NODE *t);
|
|
Packit Service |
f629e6 |
static NODE **cint_copy(NODE *symbol, NODE *newsymb);
|
|
Packit Service |
f629e6 |
static NODE **cint_dump(NODE *symbol, NODE *ndump);
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
static void cint_print(NODE *symbol);
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
afunc_t cint_array_func[] = {
|
|
Packit Service |
f629e6 |
cint_array_init,
|
|
Packit Service |
f629e6 |
is_uinteger,
|
|
Packit Service |
f629e6 |
null_length,
|
|
Packit Service |
f629e6 |
cint_lookup,
|
|
Packit Service |
f629e6 |
cint_exists,
|
|
Packit Service |
f629e6 |
cint_clear,
|
|
Packit Service |
f629e6 |
cint_remove,
|
|
Packit Service |
f629e6 |
cint_list,
|
|
Packit Service |
f629e6 |
cint_copy,
|
|
Packit Service |
f629e6 |
cint_dump,
|
|
Packit Service |
f629e6 |
(afunc_t) 0,
|
|
Packit Service |
f629e6 |
};
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline int cint_hash(long k);
|
|
Packit Service |
f629e6 |
static inline NODE **cint_find(NODE *symbol, long k, int h1);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE *make_node(NODETYPE type);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **tree_lookup(NODE *symbol, NODE *tree, long k, int m, long base);
|
|
Packit Service |
f629e6 |
static NODE **tree_exists(NODE *tree, long k);
|
|
Packit Service |
f629e6 |
static void tree_clear(NODE *tree);
|
|
Packit Service |
f629e6 |
static int tree_remove(NODE *symbol, NODE *tree, long k);
|
|
Packit Service |
f629e6 |
static void tree_copy(NODE *newsymb, NODE *tree, NODE *newtree);
|
|
Packit Service |
f629e6 |
static long tree_list(NODE *tree, NODE **list, assoc_kind_t assoc_kind);
|
|
Packit Service |
f629e6 |
static inline NODE **tree_find(NODE *tree, long k, int i);
|
|
Packit Service |
f629e6 |
static void tree_info(NODE *tree, NODE *ndump, const char *aname);
|
|
Packit Service |
f629e6 |
static size_t tree_kilobytes(NODE *tree);
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
static void tree_print(NODE *tree, size_t bi, int indent_level);
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE **leaf_lookup(NODE *symbol, NODE *array, long k, long size, long base);
|
|
Packit Service |
f629e6 |
static inline NODE **leaf_exists(NODE *array, long k);
|
|
Packit Service |
f629e6 |
static void leaf_clear(NODE *array);
|
|
Packit Service |
f629e6 |
static int leaf_remove(NODE *symbol, NODE *array, long k);
|
|
Packit Service |
f629e6 |
static void leaf_copy(NODE *newsymb, NODE *array, NODE *newarray);
|
|
Packit Service |
f629e6 |
static long leaf_list(NODE *array, NODE **list, assoc_kind_t assoc_kind);
|
|
Packit Service |
f629e6 |
static void leaf_info(NODE *array, NODE *ndump, const char *aname);
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
static void leaf_print(NODE *array, size_t bi, int indent_level);
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* powers of 2 table upto 2^30 */
|
|
Packit Service |
f629e6 |
static const long power_two_table[] = {
|
|
Packit Service |
f629e6 |
1, 2, 4, 8, 16, 32, 64,
|
|
Packit Service |
f629e6 |
128, 256, 512, 1024, 2048, 4096,
|
|
Packit Service |
f629e6 |
8192, 16384, 32768, 65536, 131072, 262144,
|
|
Packit Service |
f629e6 |
524288, 1048576, 2097152, 4194304, 8388608, 16777216,
|
|
Packit Service |
f629e6 |
33554432, 67108864, 134217728, 268435456, 536870912, 1073741824
|
|
Packit Service |
f629e6 |
};
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#define ISUINT(a, s) ((((s)->flags & NUMINT) != 0 || is_integer(a, s) != NULL) \
|
|
Packit Service |
f629e6 |
&& (s)->numbr >= 0)
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* To store 2^n integers, allocate top-level array of size n, elements
|
|
Packit Service |
f629e6 |
* of which are 1-Dimensional (leaf-array) of geometrically increasing
|
|
Packit Service |
f629e6 |
* size (power of 2).
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* [0] --> [ 0 ]
|
|
Packit Service |
f629e6 |
* [1] --> [ 1 ]
|
|
Packit Service |
f629e6 |
* |2| --> [ 2 | 3 ]
|
|
Packit Service |
f629e6 |
* |3| --> [ 4 | 5 | 6 | 7 ]
|
|
Packit Service |
f629e6 |
* |.|
|
|
Packit Service |
f629e6 |
* |k| --> [ 2^(k - 1)| ... | 2^k - 1 ]
|
|
Packit Service |
f629e6 |
* ...
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* For a given integer n (> 0), the leaf-array is at 1 + floor(log2(n)).
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* The idea for the geometrically increasing array sizes is from:
|
|
Packit Service |
f629e6 |
* Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays.
|
|
Packit Service |
f629e6 |
* Bagwell, Phil (2002).
|
|
Packit Service |
f629e6 |
* http://infoscience.epfl.ch/record/64410/files/techlists.pdf
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* Disadvantage:
|
|
Packit Service |
f629e6 |
* Worst case memory waste > 99% and will happen when each of the
|
|
Packit Service |
f629e6 |
* leaf arrays contains only a single element. Even with consecutive
|
|
Packit Service |
f629e6 |
* integers, memory waste can be as high as 50%.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* Solution: Hashed Array Trees (HATs).
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_array_init --- array initialization routine */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_array_init(NODE *symbol ATTRIBUTE_UNUSED, NODE *subs ATTRIBUTE_UNUSED)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
if (symbol == NULL) {
|
|
Packit Service |
f629e6 |
long newval;
|
|
Packit Service |
f629e6 |
size_t nelems = (sizeof(power_two_table) / sizeof(power_two_table[0]));
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* check relevant environment variables */
|
|
Packit Service |
f629e6 |
if ((newval = getenv_long("NHAT")) > 1 && newval < INT32_BIT)
|
|
Packit Service |
f629e6 |
NHAT = newval;
|
|
Packit Service |
f629e6 |
/* don't allow overflow off the end of the table */
|
|
Packit Service |
f629e6 |
if (NHAT >= nelems)
|
|
Packit Service |
f629e6 |
NHAT = nelems - 2;
|
|
Packit Service |
f629e6 |
THRESHOLD = power_two_table[NHAT + 1];
|
|
Packit Service |
f629e6 |
} else
|
|
Packit Service |
f629e6 |
null_array(symbol);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return & success_node;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* is_uinteger --- test if the subscript is an integer >= 0 */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
NODE **
|
|
Packit Service |
f629e6 |
is_uinteger(NODE *symbol, NODE *subs)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
if (is_integer(symbol, subs) != NULL && subs->numbr >= 0)
|
|
Packit Service |
f629e6 |
return & success_node;
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_lookup --- Find the subscript in the array; Install it if it isn't there. */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_lookup(NODE *symbol, NODE *subs)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
long k;
|
|
Packit Service |
f629e6 |
int h1 = -1, m, li;
|
|
Packit Service |
f629e6 |
NODE *tn, *xn;
|
|
Packit Service |
f629e6 |
long cint_size, capacity;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
k = -1;
|
|
Packit Service |
f629e6 |
if (ISUINT(symbol, subs)) {
|
|
Packit Service |
f629e6 |
k = subs->numbr; /* k >= 0 */
|
|
Packit Service |
f629e6 |
h1 = cint_hash(k); /* h1 >= NHAT */
|
|
Packit Service |
f629e6 |
if ((lhs = cint_find(symbol, k, h1)) != NULL)
|
|
Packit Service |
f629e6 |
return lhs;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
if (xn != NULL && (lhs = xn->aexists(xn, subs)) != NULL)
|
|
Packit Service |
f629e6 |
return lhs;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* It's not there, install it */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (k < 0)
|
|
Packit Service |
f629e6 |
goto xinstall;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
m = h1 - 1; /* m >= (NHAT- 1) */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* Estimate capacity upper bound.
|
|
Packit Service |
f629e6 |
* capacity upper bound = current capacity + leaf array size.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
li = m > NHAT ? m : NHAT;
|
|
Packit Service |
f629e6 |
while (li >= NHAT) {
|
|
Packit Service |
f629e6 |
/* leaf-array of a HAT */
|
|
Packit Service |
f629e6 |
li = (li + 1) / 2;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
capacity = symbol->array_capacity + power_two_table[li];
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
cint_size = (xn == NULL) ? symbol->table_size
|
|
Packit Service |
f629e6 |
: (symbol->table_size - xn->table_size);
|
|
Packit Service |
f629e6 |
assert(cint_size >= 0);
|
|
Packit Service |
f629e6 |
if ((capacity - cint_size) > THRESHOLD)
|
|
Packit Service |
f629e6 |
goto xinstall;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->nodes == NULL) {
|
|
Packit Service |
f629e6 |
symbol->array_capacity = 0;
|
|
Packit Service |
f629e6 |
assert(symbol->table_size == 0);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* nodes[0] .. nodes[NHAT- 1] not used */
|
|
Packit Service |
f629e6 |
ezalloc(symbol->nodes, NODE **, INT32_BIT * sizeof(NODE *), "cint_lookup");
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
symbol->table_size++; /* one more element in array */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[h1];
|
|
Packit Service |
f629e6 |
if (tn == NULL) {
|
|
Packit Service |
f629e6 |
tn = make_node(Node_array_tree);
|
|
Packit Service |
f629e6 |
symbol->nodes[h1] = tn;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (m < NHAT)
|
|
Packit Service |
f629e6 |
return tree_lookup(symbol, tn, k, NHAT, 0);
|
|
Packit Service |
f629e6 |
return tree_lookup(symbol, tn, k, m, power_two_table[m]);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
xinstall:
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
symbol->table_size++;
|
|
Packit Service |
f629e6 |
if (xn == NULL) {
|
|
Packit Service |
f629e6 |
xn = symbol->xarray = make_array();
|
|
Packit Service |
f629e6 |
xn->vname = symbol->vname; /* shallow copy */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* Avoid using assoc_lookup(xn, subs) which may lead
|
|
Packit Service |
f629e6 |
* to infinite recursion.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (is_integer(xn, subs))
|
|
Packit Service |
f629e6 |
xn->array_funcs = int_array_func;
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
xn->array_funcs = str_array_func;
|
|
Packit Service |
f629e6 |
xn->flags |= XARRAY;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return xn->alookup(xn, subs);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_exists --- test whether an index is in the array or not. */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_exists(NODE *symbol, NODE *subs)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *xn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (ISUINT(symbol, subs)) {
|
|
Packit Service |
f629e6 |
long k = subs->numbr;
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
if ((lhs = cint_find(symbol, k, cint_hash(k))) != NULL)
|
|
Packit Service |
f629e6 |
return lhs;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
if ((xn = symbol->xarray) == NULL)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
return xn->aexists(xn, subs);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_clear --- flush all the values in symbol[] */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_clear(NODE *symbol, NODE *subs ATTRIBUTE_UNUSED)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
size_t i;
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(symbol->nodes != NULL);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->xarray != NULL) {
|
|
Packit Service |
f629e6 |
NODE *xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
assoc_clear(xn);
|
|
Packit Service |
f629e6 |
freenode(xn);
|
|
Packit Service |
f629e6 |
symbol->xarray = NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (i = NHAT; i < INT32_BIT; i++) {
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn != NULL) {
|
|
Packit Service |
f629e6 |
tree_clear(tn);
|
|
Packit Service |
f629e6 |
freenode(tn);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
efree(symbol->nodes);
|
|
Packit Service |
f629e6 |
symbol->ainit(symbol, NULL); /* re-initialize symbol */
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_remove --- remove an index from the array */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_remove(NODE *symbol, NODE *subs)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
long k;
|
|
Packit Service |
f629e6 |
int h1;
|
|
Packit Service |
f629e6 |
NODE *tn, *xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->table_size == 0)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (! ISUINT(symbol, subs))
|
|
Packit Service |
f629e6 |
goto xremove;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(symbol->nodes != NULL);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
k = subs->numbr;
|
|
Packit Service |
f629e6 |
h1 = cint_hash(k);
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[h1];
|
|
Packit Service |
f629e6 |
if (tn == NULL || ! tree_remove(symbol, tn, k))
|
|
Packit Service |
f629e6 |
goto xremove;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (tn->table_size == 0) {
|
|
Packit Service |
f629e6 |
freenode(tn);
|
|
Packit Service |
f629e6 |
symbol->nodes[h1] = NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
symbol->table_size--;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (xn == NULL && symbol->table_size == 0) {
|
|
Packit Service |
f629e6 |
efree(symbol->nodes);
|
|
Packit Service |
f629e6 |
symbol->ainit(symbol, NULL); /* re-initialize array 'symbol' */
|
|
Packit Service |
f629e6 |
} else if(xn != NULL && symbol->table_size == xn->table_size) {
|
|
Packit Service |
f629e6 |
/* promote xn to symbol */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
xn->flags &= ~XARRAY;
|
|
Packit Service |
f629e6 |
xn->parent_array = symbol->parent_array;
|
|
Packit Service |
f629e6 |
efree(symbol->nodes);
|
|
Packit Service |
f629e6 |
*symbol = *xn;
|
|
Packit Service |
f629e6 |
freenode(xn);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return & success_node;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
xremove:
|
|
Packit Service |
f629e6 |
xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
if (xn == NULL || xn->aremove(xn, subs) == NULL)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
if (xn->table_size == 0) {
|
|
Packit Service |
f629e6 |
freenode(xn);
|
|
Packit Service |
f629e6 |
symbol->xarray = NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
symbol->table_size--;
|
|
Packit Service |
f629e6 |
assert(symbol->table_size > 0);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return & success_node;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_copy --- duplicate input array "symbol" */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_copy(NODE *symbol, NODE *newsymb)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **old, **new;
|
|
Packit Service |
f629e6 |
size_t i;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(symbol->nodes != NULL);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* allocate new table */
|
|
Packit Service |
f629e6 |
ezalloc(new, NODE **, INT32_BIT * sizeof(NODE *), "cint_copy");
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
old = symbol->nodes;
|
|
Packit Service |
f629e6 |
for (i = NHAT; i < INT32_BIT; i++) {
|
|
Packit Service |
f629e6 |
if (old[i] == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
new[i] = make_node(Node_array_tree);
|
|
Packit Service |
f629e6 |
tree_copy(newsymb, old[i], new[i]);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->xarray != NULL) {
|
|
Packit Service |
f629e6 |
NODE *xn, *n;
|
|
Packit Service |
f629e6 |
xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
n = make_array();
|
|
Packit Service |
f629e6 |
n->vname = newsymb->vname;
|
|
Packit Service |
f629e6 |
(void) xn->acopy(xn, n);
|
|
Packit Service |
f629e6 |
newsymb->xarray = n;
|
|
Packit Service |
f629e6 |
} else
|
|
Packit Service |
f629e6 |
newsymb->xarray = NULL;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
newsymb->nodes = new;
|
|
Packit Service |
f629e6 |
newsymb->table_size = symbol->table_size;
|
|
Packit Service |
f629e6 |
newsymb->array_capacity = symbol->array_capacity;
|
|
Packit Service |
f629e6 |
newsymb->flags = symbol->flags;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_list --- return a list of items */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE**
|
|
Packit Service |
f629e6 |
cint_list(NODE *symbol, NODE *t)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **list = NULL;
|
|
Packit Service |
f629e6 |
NODE *tn, *xn;
|
|
Packit Service |
f629e6 |
unsigned long k = 0, num_elems, list_size;
|
|
Packit Service |
f629e6 |
size_t j, ja, jd;
|
|
Packit Service |
f629e6 |
int elem_size = 1;
|
|
Packit Service |
f629e6 |
assoc_kind_t assoc_kind;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
num_elems = symbol->table_size;
|
|
Packit Service |
f629e6 |
if (num_elems == 0)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
assoc_kind = (assoc_kind_t) t->flags;
|
|
Packit Service |
f629e6 |
if ((assoc_kind & (AINDEX|AVALUE|ADELETE)) == (AINDEX|ADELETE))
|
|
Packit Service |
f629e6 |
num_elems = 1;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if ((assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE))
|
|
Packit Service |
f629e6 |
elem_size = 2;
|
|
Packit Service |
f629e6 |
list_size = num_elems * elem_size;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->xarray != NULL) {
|
|
Packit Service |
f629e6 |
xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
list = xn->alist(xn, t);
|
|
Packit Service |
f629e6 |
assert(list != NULL);
|
|
Packit Service |
f629e6 |
assoc_kind &= ~(AASC|ADESC);
|
|
Packit Service |
f629e6 |
t->flags = (unsigned int) assoc_kind;
|
|
Packit Service |
f629e6 |
if (num_elems == 1 || num_elems == xn->table_size)
|
|
Packit Service |
f629e6 |
return list;
|
|
Packit Service |
f629e6 |
erealloc(list, NODE **, list_size * sizeof(NODE *), "cint_list");
|
|
Packit Service |
f629e6 |
k = elem_size * xn->table_size;
|
|
Packit Service |
f629e6 |
} else
|
|
Packit Service |
f629e6 |
emalloc(list, NODE **, list_size * sizeof(NODE *), "cint_list");
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if ((assoc_kind & AINUM) == 0) {
|
|
Packit Service |
f629e6 |
/* not sorting by "index num" */
|
|
Packit Service |
f629e6 |
assoc_kind &= ~(AASC|ADESC);
|
|
Packit Service |
f629e6 |
t->flags = (unsigned int) assoc_kind;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* populate it with index in ascending or descending order */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (ja = NHAT, jd = INT32_BIT - 1; ja < INT32_BIT && jd >= NHAT; ) {
|
|
Packit Service |
f629e6 |
j = (assoc_kind & ADESC) != 0 ? jd-- : ja++;
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[j];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
k += tree_list(tn, list + k, assoc_kind);
|
|
Packit Service |
f629e6 |
if (k >= list_size)
|
|
Packit Service |
f629e6 |
return list;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return list;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_dump --- dump array info */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
cint_dump(NODE *symbol, NODE *ndump)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn, *xn = NULL;
|
|
Packit Service |
f629e6 |
int indent_level;
|
|
Packit Service |
f629e6 |
size_t i;
|
|
Packit Service |
f629e6 |
long cint_size = 0, xsize = 0;
|
|
Packit Service |
f629e6 |
AWKNUM kb = 0;
|
|
Packit Service |
f629e6 |
extern AWKNUM int_kilobytes(NODE *symbol);
|
|
Packit Service |
f629e6 |
extern AWKNUM str_kilobytes(NODE *symbol);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
indent_level = ndump->alevel;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->xarray != NULL) {
|
|
Packit Service |
f629e6 |
xn = symbol->xarray;
|
|
Packit Service |
f629e6 |
xsize = xn->table_size;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
cint_size = symbol->table_size - xsize;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if ((symbol->flags & XARRAY) == 0)
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "%s `%s'\n",
|
|
Packit Service |
f629e6 |
(symbol->parent_array == NULL) ? "array" : "sub-array",
|
|
Packit Service |
f629e6 |
array_vname(symbol));
|
|
Packit Service |
f629e6 |
indent_level++;
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "array_func: cint_array_func\n");
|
|
Packit Service |
f629e6 |
if (symbol->flags != 0) {
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "flags: %s\n", flags2str(symbol->flags));
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "NHAT: %d\n", NHAT);
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "THRESHOLD: %ld\n", THRESHOLD);
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "table_size: %ld (total), %ld (cint), %ld (int + str)\n",
|
|
Packit Service |
f629e6 |
symbol->table_size, cint_size, xsize);
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "array_capacity: %lu\n", (unsigned long) symbol->array_capacity);
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "Load Factor: %.2g\n", (AWKNUM) cint_size / symbol->array_capacity);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (i = NHAT; i < INT32_BIT; i++) {
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
/* Node_array_tree + HAT */
|
|
Packit Service |
f629e6 |
kb += (sizeof(NODE) + tree_kilobytes(tn)) / 1024.0;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
kb += (INT32_BIT * sizeof(NODE *)) / 1024.0; /* symbol->nodes */
|
|
Packit Service |
f629e6 |
kb += (symbol->array_capacity * sizeof(NODE *)) / 1024.0; /* value nodes in Node_array_leaf(s) */
|
|
Packit Service |
f629e6 |
if (xn != NULL) {
|
|
Packit Service |
f629e6 |
if (xn->array_funcs == int_array_func)
|
|
Packit Service |
f629e6 |
kb += int_kilobytes(xn);
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
kb += str_kilobytes(xn);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "memory: %.2g kB (total)\n", kb);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* dump elements */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (ndump->adepth >= 0) {
|
|
Packit Service |
f629e6 |
const char *aname;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "\n");
|
|
Packit Service |
f629e6 |
aname = make_aname(symbol);
|
|
Packit Service |
f629e6 |
for (i = NHAT; i < INT32_BIT; i++) {
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn != NULL)
|
|
Packit Service |
f629e6 |
tree_info(tn, ndump, aname);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (xn != NULL) {
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "\n");
|
|
Packit Service |
f629e6 |
xn->adump(xn, ndump);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
if (ndump->adepth < -999)
|
|
Packit Service |
f629e6 |
cint_print(symbol);
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_hash --- locate the HAT for a given number 'k' */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline int
|
|
Packit Service |
f629e6 |
cint_hash(long k)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
uint32_t num, r, shift;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(k >= 0);
|
|
Packit Service |
f629e6 |
if (k == 0)
|
|
Packit Service |
f629e6 |
return NHAT;
|
|
Packit Service |
f629e6 |
num = k;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* Find the Floor(log base 2 of 32-bit integer) */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* Warren Jr., Henry S. (2002). Hacker's Delight.
|
|
Packit Service |
f629e6 |
* Addison Wesley. pp. pp. 215. ISBN 978-0201914658.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* r = 0;
|
|
Packit Service |
f629e6 |
* if (num >= 1<<16) { num >>= 16; r += 16; }
|
|
Packit Service |
f629e6 |
* if (num >= 1<< 8) { num >>= 8; r += 8; }
|
|
Packit Service |
f629e6 |
* if (num >= 1<< 4) { num >>= 4; r += 4; }
|
|
Packit Service |
f629e6 |
* if (num >= 1<< 2) { num >>= 2; r += 2; }
|
|
Packit Service |
f629e6 |
* if (num >= 1<< 1) { r += 1; }
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* Slightly different code copied from:
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* http://www-graphics.stanford.edu/~seander/bithacks.html
|
|
Packit Service |
f629e6 |
* Bit Twiddling Hacks
|
|
Packit Service |
f629e6 |
* By Sean Eron Anderson
|
|
Packit Service |
f629e6 |
* seander@cs.stanford.edu
|
|
Packit Service |
f629e6 |
* Individually, the code snippets here are in the public domain
|
|
Packit Service |
f629e6 |
* (unless otherwise noted) --- feel free to use them however you please.
|
|
Packit Service |
f629e6 |
* The aggregate collection and descriptions are (C) 1997-2005
|
|
Packit Service |
f629e6 |
* Sean Eron Anderson. The code and descriptions are distributed in the
|
|
Packit Service |
f629e6 |
* hope that they will be useful, but WITHOUT ANY WARRANTY and without
|
|
Packit Service |
f629e6 |
* even the implied warranty of merchantability or fitness for a particular
|
|
Packit Service |
f629e6 |
* purpose.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
r = (num > 0xFFFF) << 4; num >>= r;
|
|
Packit Service |
f629e6 |
shift = (num > 0xFF) << 3; num >>= shift; r |= shift;
|
|
Packit Service |
f629e6 |
shift = (num > 0x0F) << 2; num >>= shift; r |= shift;
|
|
Packit Service |
f629e6 |
shift = (num > 0x03) << 1; num >>= shift; r |= shift;
|
|
Packit Service |
f629e6 |
r |= (num >> 1);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* We use a single HAT for 0 <= num < 2^NHAT */
|
|
Packit Service |
f629e6 |
if (r < NHAT)
|
|
Packit Service |
f629e6 |
return NHAT;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return (1 + r);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_find --- locate the integer subscript */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE **
|
|
Packit Service |
f629e6 |
cint_find(NODE *symbol, long k, int h1)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (symbol->nodes == NULL || (tn = symbol->nodes[h1]) == NULL)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
return tree_exists(tn, k);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* cint_print --- print structural info */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
cint_print(NODE *symbol)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t i;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "I[%4lu:%-4lu]\n", (unsigned long) INT32_BIT,
|
|
Packit Service |
f629e6 |
(unsigned long) symbol->table_size);
|
|
Packit Service |
f629e6 |
for (i = NHAT; i < INT32_BIT; i++) {
|
|
Packit Service |
f629e6 |
tn = symbol->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
tree_print(tn, i, 1);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*------------------------ Hashed Array Trees -----------------------------*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* HATs: Hashed Array Trees
|
|
Packit Service |
f629e6 |
* Fast variable-length arrays
|
|
Packit Service |
f629e6 |
* Edward Sitarski
|
|
Packit Service |
f629e6 |
* http://www.drdobbs.com/architecture-and-design/184409965
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* HAT has a top-level array containing a power of two
|
|
Packit Service |
f629e6 |
* number of leaf arrays. All leaf arrays are the same size as the
|
|
Packit Service |
f629e6 |
* top-level array. A full HAT can hold n^2 elements,
|
|
Packit Service |
f629e6 |
* where n (some power of 2) is the size of each leaf array.
|
|
Packit Service |
f629e6 |
* [i/n][i & (n - 1)] locates the `i th' element in a HAT.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* A half HAT is defined here as a HAT with a top-level array of size n^2/2
|
|
Packit Service |
f629e6 |
* and holds the first n^2/2 elements.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* 1. 2^8 elements can be stored in a full HAT of size 2^4.
|
|
Packit Service |
f629e6 |
* 2. 2^9 elements can be stored in a half HAT of size 2^5.
|
|
Packit Service |
f629e6 |
* 3. When the number of elements is some power of 2, it
|
|
Packit Service |
f629e6 |
* can be stored in a full or a half HAT.
|
|
Packit Service |
f629e6 |
* 4. When the number of elements is some power of 2, it
|
|
Packit Service |
f629e6 |
* can be stored in a HAT (full or half) with HATs as leaf elements
|
|
Packit Service |
f629e6 |
* (full or half), and so on (e.g. 2^8 elements in a HAT of size 2^4 (top-level
|
|
Packit Service |
f629e6 |
* array dimension) with each leaf array being a HAT of size 2^2).
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* IMPLEMENTATION DETAILS:
|
|
Packit Service |
f629e6 |
* 1. A HAT of 2^12 elements needs 2^6 house-keeping NODEs
|
|
Packit Service |
f629e6 |
* of Node_array_leaf.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* 2. A HAT of HATS of 2^12 elements needs
|
|
Packit Service |
f629e6 |
* 2^6 * (1 Node_array_tree + 2^3 Node_array_leaf)
|
|
Packit Service |
f629e6 |
* ~ 2^9 house-keeping NODEs.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* 3. When a leaf array (or leaf HAT) becomes empty, the memory
|
|
Packit Service |
f629e6 |
* is deallocated, and when there is no leaf array (or leaf HAT) left,
|
|
Packit Service |
f629e6 |
* the HAT is deleted.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
* 4. A HAT stores the base (first) element, and locates the leaf array/HAT
|
|
Packit Service |
f629e6 |
* for the `i th' element using integer division
|
|
Packit Service |
f629e6 |
* (i - base)/n where n is the size of the top-level array.
|
|
Packit Service |
f629e6 |
*
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* make_node --- initialize a NODE */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE *
|
|
Packit Service |
f629e6 |
make_node(NODETYPE type)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *n;
|
|
Packit Service |
f629e6 |
getnode(n);
|
|
Packit Service |
f629e6 |
memset(n, '\0', sizeof(NODE));
|
|
Packit Service |
f629e6 |
n->type = type;
|
|
Packit Service |
f629e6 |
return n;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_lookup --- Find an integer subscript in a HAT; Install it if it isn't there */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
tree_lookup(NODE *symbol, NODE *tree, long k, int m, long base)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
int i, n;
|
|
Packit Service |
f629e6 |
size_t size;
|
|
Packit Service |
f629e6 |
long num = k;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* HAT size (size of Top & Leaf array) = 2^n
|
|
Packit Service |
f629e6 |
* where n = Floor ((m + 1)/2). For an odd value of m,
|
|
Packit Service |
f629e6 |
* only the first half of the HAT is needed.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
n = (m + 1) / 2;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (tree->table_size == 0) {
|
|
Packit Service |
f629e6 |
size_t actual_size;
|
|
Packit Service |
f629e6 |
NODE **table;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(tree->nodes == NULL);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* initialize top-level array */
|
|
Packit Service |
f629e6 |
size = actual_size = power_two_table[n];
|
|
Packit Service |
f629e6 |
tree->array_base = base;
|
|
Packit Service |
f629e6 |
tree->array_size = size;
|
|
Packit Service |
f629e6 |
tree->table_size = 0; /* # of elements in the array */
|
|
Packit Service |
f629e6 |
if (n > m/2) {
|
|
Packit Service |
f629e6 |
/* only first half of the array used */
|
|
Packit Service |
f629e6 |
actual_size /= 2;
|
|
Packit Service |
f629e6 |
tree->flags |= HALFHAT;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
ezalloc(table, NODE **, actual_size * sizeof(NODE *), "tree_lookup");
|
|
Packit Service |
f629e6 |
tree->nodes = table;
|
|
Packit Service |
f629e6 |
} else
|
|
Packit Service |
f629e6 |
size = tree->array_size;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
num -= tree->array_base;
|
|
Packit Service |
f629e6 |
i = num / size; /* top-level array index */
|
|
Packit Service |
f629e6 |
assert(i >= 0);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if ((lhs = tree_find(tree, k, i)) != NULL)
|
|
Packit Service |
f629e6 |
return lhs;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* It's not there, install it */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
tree->table_size++;
|
|
Packit Service |
f629e6 |
base += (size * i);
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i];
|
|
Packit Service |
f629e6 |
if (n > NHAT) {
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i] = make_node(Node_array_tree);
|
|
Packit Service |
f629e6 |
return tree_lookup(symbol, tn, k, n, base);
|
|
Packit Service |
f629e6 |
} else {
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i] = make_node(Node_array_leaf);
|
|
Packit Service |
f629e6 |
return leaf_lookup(symbol, tn, k, size, base);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_exists --- test whether integer subscript `k' exists or not */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static NODE **
|
|
Packit Service |
f629e6 |
tree_exists(NODE *tree, long k)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
int i;
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
i = (k - tree->array_base) / tree->array_size;
|
|
Packit Service |
f629e6 |
assert(i >= 0);
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
return tree_exists(tn, k);
|
|
Packit Service |
f629e6 |
return leaf_exists(tn, k);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_clear --- flush all the values */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
tree_clear(NODE *tree)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t j, hsize;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
tn = tree->nodes[j];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
tree_clear(tn);
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
leaf_clear(tn);
|
|
Packit Service |
f629e6 |
freenode(tn);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
efree(tree->nodes);
|
|
Packit Service |
f629e6 |
memset(tree, '\0', sizeof(NODE));
|
|
Packit Service |
f629e6 |
tree->type = Node_array_tree;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_remove --- If the integer subscript is in the HAT, remove it */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static int
|
|
Packit Service |
f629e6 |
tree_remove(NODE *symbol, NODE *tree, long k)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
int i;
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
i = (k - tree->array_base) / tree->array_size;
|
|
Packit Service |
f629e6 |
assert(i >= 0);
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
return false;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree
|
|
Packit Service |
f629e6 |
&& ! tree_remove(symbol, tn, k))
|
|
Packit Service |
f629e6 |
return false;
|
|
Packit Service |
f629e6 |
else if (tn->type == Node_array_leaf
|
|
Packit Service |
f629e6 |
&& ! leaf_remove(symbol, tn, k))
|
|
Packit Service |
f629e6 |
return false;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (tn->table_size == 0) {
|
|
Packit Service |
f629e6 |
freenode(tn);
|
|
Packit Service |
f629e6 |
tree->nodes[i] = NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* one less item in array */
|
|
Packit Service |
f629e6 |
if (--tree->table_size == 0) {
|
|
Packit Service |
f629e6 |
efree(tree->nodes);
|
|
Packit Service |
f629e6 |
memset(tree, '\0', sizeof(NODE));
|
|
Packit Service |
f629e6 |
tree->type = Node_array_tree;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return true;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_find --- locate an interger subscript in the HAT */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE **
|
|
Packit Service |
f629e6 |
tree_find(NODE *tree, long k, int i)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(tree->nodes != NULL);
|
|
Packit Service |
f629e6 |
tn = tree->nodes[i];
|
|
Packit Service |
f629e6 |
if (tn != NULL) {
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
return tree_exists(tn, k);
|
|
Packit Service |
f629e6 |
return leaf_exists(tn, k);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_list --- return a list of items in the HAT */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static long
|
|
Packit Service |
f629e6 |
tree_list(NODE *tree, NODE **list, assoc_kind_t assoc_kind)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t j, cj, hsize;
|
|
Packit Service |
f629e6 |
long k = 0;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
assert(list != NULL);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
cj = (assoc_kind & ADESC) != 0 ? (hsize - 1 - j) : j;
|
|
Packit Service |
f629e6 |
tn = tree->nodes[cj];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
k += tree_list(tn, list + k, assoc_kind);
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
k += leaf_list(tn, list + k, assoc_kind);
|
|
Packit Service |
f629e6 |
if ((assoc_kind & ADELETE) != 0 && k >= 1)
|
|
Packit Service |
f629e6 |
return k;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return k;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_copy --- duplicate a HAT */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
tree_copy(NODE *newsymb, NODE *tree, NODE *newtree)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **old, **new;
|
|
Packit Service |
f629e6 |
size_t j, hsize;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
ezalloc(new, NODE **, hsize * sizeof(NODE *), "tree_copy");
|
|
Packit Service |
f629e6 |
newtree->nodes = new;
|
|
Packit Service |
f629e6 |
newtree->array_base = tree->array_base;
|
|
Packit Service |
f629e6 |
newtree->array_size = tree->array_size;
|
|
Packit Service |
f629e6 |
newtree->table_size = tree->table_size;
|
|
Packit Service |
f629e6 |
newtree->flags = tree->flags;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
old = tree->nodes;
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
if (old[j] == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (old[j]->type == Node_array_tree) {
|
|
Packit Service |
f629e6 |
new[j] = make_node(Node_array_tree);
|
|
Packit Service |
f629e6 |
tree_copy(newsymb, old[j], new[j]);
|
|
Packit Service |
f629e6 |
} else {
|
|
Packit Service |
f629e6 |
new[j] = make_node(Node_array_leaf);
|
|
Packit Service |
f629e6 |
leaf_copy(newsymb, old[j], new[j]);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_info --- print index, value info */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
tree_info(NODE *tree, NODE *ndump, const char *aname)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t j, hsize;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
tn = tree->nodes[j];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
tree_info(tn, ndump, aname);
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
leaf_info(tn, ndump, aname);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_kilobytes --- calculate memory consumption of a HAT */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static size_t
|
|
Packit Service |
f629e6 |
tree_kilobytes(NODE *tree)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t j, hsize;
|
|
Packit Service |
f629e6 |
size_t sz = 0;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
tn = tree->nodes[j];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
sz += sizeof(NODE); /* Node_array_tree or Node_array_leaf */
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
sz += tree_kilobytes(tn);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
sz += hsize * sizeof(NODE *); /* tree->nodes */
|
|
Packit Service |
f629e6 |
return sz;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* tree_print --- print the HAT structures */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
tree_print(NODE *tree, size_t bi, int indent_level)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *tn;
|
|
Packit Service |
f629e6 |
size_t j, hsize;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
hsize = tree->array_size;
|
|
Packit Service |
f629e6 |
if ((tree->flags & HALFHAT) != 0)
|
|
Packit Service |
f629e6 |
hsize /= 2;
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "%4lu:%s[%4lu:%-4lu]\n",
|
|
Packit Service |
f629e6 |
(unsigned long) bi,
|
|
Packit Service |
f629e6 |
(tree->flags & HALFHAT) != 0 ? "HH" : "H",
|
|
Packit Service |
f629e6 |
(unsigned long) hsize, (unsigned long) tree->table_size);
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (j = 0; j < hsize; j++) {
|
|
Packit Service |
f629e6 |
tn = tree->nodes[j];
|
|
Packit Service |
f629e6 |
if (tn == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (tn->type == Node_array_tree)
|
|
Packit Service |
f629e6 |
tree_print(tn, j, indent_level + 1);
|
|
Packit Service |
f629e6 |
else
|
|
Packit Service |
f629e6 |
leaf_print(tn, j, indent_level + 1);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
#endif
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*--------------------- leaf (linear 1-D) array --------------------*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/*
|
|
Packit Service |
f629e6 |
* leaf_lookup --- find an integer subscript in the array; Install it if
|
|
Packit Service |
f629e6 |
* it isn't there.
|
|
Packit Service |
f629e6 |
*/
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE **
|
|
Packit Service |
f629e6 |
leaf_lookup(NODE *symbol, NODE *array, long k, long size, long base)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
if (array->nodes == NULL) {
|
|
Packit Service |
f629e6 |
array->table_size = 0; /* sanity */
|
|
Packit Service |
f629e6 |
array->array_size = size;
|
|
Packit Service |
f629e6 |
array->array_base = base;
|
|
Packit Service |
f629e6 |
ezalloc(array->nodes, NODE **, size * sizeof(NODE *), "leaf_lookup");
|
|
Packit Service |
f629e6 |
symbol->array_capacity += size;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
lhs = array->nodes + (k - base); /* leaf element */
|
|
Packit Service |
f629e6 |
if (*lhs == NULL) {
|
|
Packit Service |
f629e6 |
array->table_size++; /* one more element in leaf array */
|
|
Packit Service |
f629e6 |
*lhs = dupnode(Nnull_string);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return lhs;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_exists --- check if the array contains an integer subscript */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static inline NODE **
|
|
Packit Service |
f629e6 |
leaf_exists(NODE *array, long k)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
lhs = array->nodes + (k - array->array_base);
|
|
Packit Service |
f629e6 |
return (*lhs != NULL) ? lhs : NULL;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_clear --- flush all values in the array */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
leaf_clear(NODE *array)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
long i, size = array->array_size;
|
|
Packit Service |
f629e6 |
NODE *r;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (i = 0; i < size; i++) {
|
|
Packit Service |
f629e6 |
r = array->nodes[i];
|
|
Packit Service |
f629e6 |
if (r == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (r->type == Node_var_array) {
|
|
Packit Service |
f629e6 |
assoc_clear(r); /* recursively clear all sub-arrays */
|
|
Packit Service |
f629e6 |
efree(r->vname);
|
|
Packit Service |
f629e6 |
freenode(r);
|
|
Packit Service |
f629e6 |
} else
|
|
Packit Service |
f629e6 |
unref(r);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
efree(array->nodes);
|
|
Packit Service |
f629e6 |
array->nodes = NULL;
|
|
Packit Service |
f629e6 |
array->array_size = array->table_size = 0;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_remove --- remove an integer subscript from the array */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static int
|
|
Packit Service |
f629e6 |
leaf_remove(NODE *symbol, NODE *array, long k)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **lhs;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
lhs = array->nodes + (k - array->array_base);
|
|
Packit Service |
f629e6 |
if (*lhs == NULL)
|
|
Packit Service |
f629e6 |
return false;
|
|
Packit Service |
f629e6 |
*lhs = NULL;
|
|
Packit Service |
f629e6 |
if (--array->table_size == 0) {
|
|
Packit Service |
f629e6 |
efree(array->nodes);
|
|
Packit Service |
f629e6 |
array->nodes = NULL;
|
|
Packit Service |
f629e6 |
symbol->array_capacity -= array->array_size;
|
|
Packit Service |
f629e6 |
array->array_size = 0; /* sanity */
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
return true;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_copy --- duplicate a leaf array */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
leaf_copy(NODE *newsymb, NODE *array, NODE *newarray)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE **old, **new;
|
|
Packit Service |
f629e6 |
long size, i;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
size = array->array_size;
|
|
Packit Service |
f629e6 |
ezalloc(new, NODE **, size * sizeof(NODE *), "leaf_copy");
|
|
Packit Service |
f629e6 |
newarray->nodes = new;
|
|
Packit Service |
f629e6 |
newarray->array_size = size;
|
|
Packit Service |
f629e6 |
newarray->array_base = array->array_base;
|
|
Packit Service |
f629e6 |
newarray->flags = array->flags;
|
|
Packit Service |
f629e6 |
newarray->table_size = array->table_size;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
old = array->nodes;
|
|
Packit Service |
f629e6 |
for (i = 0; i < size; i++) {
|
|
Packit Service |
f629e6 |
if (old[i] == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
if (old[i]->type == Node_val)
|
|
Packit Service |
f629e6 |
new[i] = dupnode(old[i]);
|
|
Packit Service |
f629e6 |
else {
|
|
Packit Service |
f629e6 |
NODE *r;
|
|
Packit Service |
f629e6 |
r = make_array();
|
|
Packit Service |
f629e6 |
r->vname = estrdup(old[i]->vname, strlen(old[i]->vname));
|
|
Packit Service |
f629e6 |
r->parent_array = newsymb;
|
|
Packit Service |
f629e6 |
new[i] = assoc_copy(old[i], r);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_list --- return a list of items */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static long
|
|
Packit Service |
f629e6 |
leaf_list(NODE *array, NODE **list, assoc_kind_t assoc_kind)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *r, *subs;
|
|
Packit Service |
f629e6 |
long num, i, ci, k = 0;
|
|
Packit Service |
f629e6 |
long size = array->array_size;
|
|
Packit Service |
f629e6 |
static char buf[100];
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
for (i = 0; i < size; i++) {
|
|
Packit Service |
f629e6 |
ci = (assoc_kind & ADESC) != 0 ? (size - 1 - i) : i;
|
|
Packit Service |
f629e6 |
r = array->nodes[ci];
|
|
Packit Service |
f629e6 |
if (r == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* index */
|
|
Packit Service |
f629e6 |
num = array->array_base + ci;
|
|
Packit Service |
f629e6 |
if ((assoc_kind & AISTR) != 0) {
|
|
Packit Service |
f629e6 |
sprintf(buf, "%ld", num);
|
|
Packit Service |
f629e6 |
subs = make_string(buf, strlen(buf));
|
|
Packit Service |
f629e6 |
subs->numbr = num;
|
|
Packit Service |
f629e6 |
subs->flags |= (NUMCUR|NUMINT);
|
|
Packit Service |
f629e6 |
} else {
|
|
Packit Service |
f629e6 |
subs = make_number((AWKNUM) num);
|
|
Packit Service |
f629e6 |
subs->flags |= (INTIND|NUMINT);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
list[k++] = subs;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* value */
|
|
Packit Service |
f629e6 |
if ((assoc_kind & AVALUE) != 0) {
|
|
Packit Service |
f629e6 |
if (r->type == Node_val) {
|
|
Packit Service |
f629e6 |
if ((assoc_kind & AVNUM) != 0)
|
|
Packit Service |
f629e6 |
(void) force_number(r);
|
|
Packit Service |
f629e6 |
else if ((assoc_kind & AVSTR) != 0)
|
|
Packit Service |
f629e6 |
r = force_string(r);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
list[k++] = r;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
if ((assoc_kind & ADELETE) != 0 && k >= 1)
|
|
Packit Service |
f629e6 |
return k;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
return k;
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_info --- print index, value info */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
leaf_info(NODE *array, NODE *ndump, const char *aname)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
NODE *subs, *val;
|
|
Packit Service |
f629e6 |
size_t i, size;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
size = array->array_size;
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
subs = make_number((AWKNUM) 0.0);
|
|
Packit Service |
f629e6 |
subs->flags |= (INTIND|NUMINT);
|
|
Packit Service |
f629e6 |
for (i = 0; i < size; i++) {
|
|
Packit Service |
f629e6 |
val = array->nodes[i];
|
|
Packit Service |
f629e6 |
if (val == NULL)
|
|
Packit Service |
f629e6 |
continue;
|
|
Packit Service |
f629e6 |
subs->numbr = array->array_base + i;
|
|
Packit Service |
f629e6 |
assoc_info(subs, val, ndump, aname);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
unref(subs);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
#ifdef ARRAYDEBUG
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
/* leaf_print --- print the leaf-array structure */
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
|
|
Packit Service |
f629e6 |
static void
|
|
Packit Service |
f629e6 |
leaf_print(NODE *array, size_t bi, int indent_level)
|
|
Packit Service |
f629e6 |
{
|
|
Packit Service |
f629e6 |
indent(indent_level);
|
|
Packit Service |
f629e6 |
fprintf(output_fp, "%4lu:L[%4lu:%-4lu]\n",
|
|
Packit Service |
f629e6 |
(unsigned long) bi,
|
|
Packit Service |
f629e6 |
(unsigned long) array->array_size,
|
|
Packit Service |
f629e6 |
(unsigned long) array->table_size);
|
|
Packit Service |
f629e6 |
}
|
|
Packit Service |
f629e6 |
#endif
|