/
githubmirror
/
gawk
Обзор
Документация
Войти
/
githubmirror
/
gawk
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
cint_array.c
1 219 строк
28 KB
Arnold D. Robbins
Minor fixes for printf compile warnings.
06 июн 2012, 21:03
06 июн 2012, 21:03
fcc37ab
Код
Авторство
О чём код?
/* * 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 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, }; 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; if (symbol->table_size == 0) return NULL; if (! ISUINT(symbol, subs)) goto xremove; assert(symbol->nodes != NULL); 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 * seander@cs.stanford.edu * 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 /* 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, "%4lu:%s[%4lu:%-4lu]\n", (unsigned long) 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, "%4lu:L[%4lu:%-4lu]\n", (unsigned long) bi, (unsigned long) array->array_size, (unsigned long) array->table_size); } #endif