/*
libmawk changes (C) 2009-2014, Tibor 'Igor2' Palinkas;
based on mawk code coming with the below copyright:
copyright 1991-96, Michael D. Brennan
This is a source file for mawk, an implementation of
the AWK programming language.
Mawk is distributed without warranty under the terms of
the GNU General Public License, version 2, 1991.
*/
/*
This file had been originally generated with the command
notangle -R'"array.c"' array.w > array.c
but is maintained as .c in libmawk.
(Notangle is part of Norman Ramsey's noweb literate programming package
available from CTAN(ftp.shsu.edu)).
*/
#include <stdio.h>
#include <string.h>
#include "mawk.h"
#include "symtype.h"
#include "memory.h"
#include "zmalloc.h"
#include "field.h"
#include "bi_vars.h"
#include "num.h"
#include "array_orig.h"
#include "cell.h"
#include "split.h"
struct anode;
typedef struct {
struct anode *slink, *ilink;
} DUAL_LINK;
typedef struct anode {
struct anode *slink;
struct anode *ilink;
mawk_string_t *sval;
unsigned hval;
Int ival;
mawk_cell_t cell;
} ANODE;
#define NOT_AN_IVALUE (-Max_Int-1) /* usually 0x80000000 */
#define STARTING_HMASK 63 /* 2^6-1, must have form 2^n-1 */
#define MAX_AVE_LIST_LENGTH 12
#define hmask_to_limit(x) (((x)+1)*MAX_AVE_LIST_LENGTH)
static ANODE *mawk_find_by_ival(mawk_state_t *, mawk_array_t, Int, int);
static ANODE *mawk_find_by_sval(mawk_state_t *, mawk_array_t, mawk_string_t *, int);
static void add_string_associations(mawk_state_t *, mawk_array_t);
static void make_empty_table(mawk_state_t *, mawk_array_t, int);
static void convert_split_array_to_table(mawk_state_t *, mawk_array_t);
static void double_the_hash_table(mawk_state_t *, mawk_array_t);
static unsigned ahash(mawk_string_t *);
mawk_cell_t *mawk_array_find_orig_(mawk_state_t *MAWK, mawk_array_t A, const mawk_cell_t *cp, int create_flag)
{
ANODE *ap;
if (A->size == 0 && !create_flag)
/* eliminating this trivial case early avoids unnecessary conversions later */
return (mawk_cell_t *) 0;
switch (cp->type) {
case C_NUM:
{
mawk_num_t d = cp->d.dval;
Int ival = mawk_d_to_I(d);
if ((mawk_num_t) ival == d) {
if (A->type == AY_SPLIT) {
if (ival >= 1 && ival <= A->size)
return (mawk_cell_t *) A->ptr + (ival - 1);
if (!create_flag)
return (mawk_cell_t *) 0;
convert_split_array_to_table(MAWK, A);
}
else if (A->type == AY_NULL) {
make_empty_table(MAWK, A, AY_INT);
if (A->ptr == NULL)
return NULL;
}
ap = mawk_find_by_ival(MAWK, A, ival, create_flag);
}
else {
/* convert to string */
char buff[260];
mawk_string_t *sval;
sprintf(buff, string(MAWK_CONVFMT)->str, d);
sval = mawk_new_STRING(MAWK, buff);
ap = mawk_find_by_sval(MAWK, A, sval, create_flag);
free_STRING(sval);
}
}
break;
case C_NOINIT:
ap = mawk_find_by_sval(MAWK, A, &(MAWK->null_str), create_flag);
break;
default:
ap = mawk_find_by_sval(MAWK, A, string(cp), create_flag);
break;
}
return ap ? &ap->cell : (mawk_cell_t *) 0;
}
static int mawk_array_find_orig(mawk_state_t *MAWK, mawk_array_t A, const mawk_cell_t *idx, mawk_cell_t *result, int create)
{
mawk_cell_t *member;
member = mawk_array_find_orig_(MAWK, A, idx, create);
if (result != NULL) {
mawk_cell_destroy(MAWK, result);
result->type = C_NOINIT;
}
if (member == NULL)
return 0;
if (result != NULL)
mawk_cellcpy(MAWK, result, member);
return 1;
}
void mawk_array_set_orig(mawk_state_t *MAWK, mawk_array_t arr, const mawk_cell_t *idx, mawk_cell_t *val)
{
mawk_cell_t *member;
member = mawk_array_find_orig_(MAWK, arr, idx, MAWK_CREATE);
mawk_cell_destroy(MAWK, member);
mawk_cellcpy(MAWK, member, val);
}
static void mawk_array_delete_orig(mawk_state_t *MAWK, mawk_array_t A, const mawk_cell_t *cp)
{
ANODE *ap;
if (A->size == 0)
return;
switch (cp->type) {
case C_NUM:
{
mawk_num_t d = cp->d.dval;
Int ival = mawk_d_to_I(d);
if ((mawk_num_t) ival == d) {
if (A->type == AY_SPLIT) {
if (ival >= 1 && ival <= A->size) {
convert_split_array_to_table(MAWK, A);
}
else
return; /* ival not in range */
}
ap = mawk_find_by_ival(MAWK, A, ival, NO_MAWK_CREATE);
if (ap) { /* remove from the front of the ilist */
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
table[ap->ival & A->hmask].ilink = ap->ilink;
if (ap->sval) {
ANODE *p, *q = 0;
int index = ap->hval & A->hmask;
p = table[index].slink;
while (p != ap) {
q = p;
p = q->slink;
}
if (q)
q->slink = p->slink;
else
table[index].slink = p->slink;
free_STRING(ap->sval);
}
mawk_cell_destroy(MAWK, &ap->cell);
MAWK_ZFREE(MAWK, ap);
if (--A->size == 0)
mawk_array_clear(MAWK, A);
}
return;
}
else { /* get the string value */
char buff[260];
mawk_string_t *sval;
sprintf(buff, string(MAWK_CONVFMT)->str, d);
sval = mawk_new_STRING(MAWK, buff);
ap = mawk_find_by_sval(MAWK, A, sval, NO_MAWK_CREATE);
free_STRING(sval);
}
}
break;
case C_NOINIT:
ap = mawk_find_by_sval(MAWK, A, &(MAWK->null_str), NO_MAWK_CREATE);
break;
default:
ap = mawk_find_by_sval(MAWK, A, string(cp), NO_MAWK_CREATE);
break;
}
if (ap) { /* remove from the front of the slist */
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
table[ap->hval & A->hmask].slink = ap->slink;
if (ap->ival != NOT_AN_IVALUE) {
ANODE *p, *q = 0;
int index = ap->ival & A->hmask;
p = table[index].ilink;
while (p != ap) {
q = p;
p = q->ilink;
}
if (q)
q->ilink = p->ilink;
else
table[index].ilink = p->ilink;
}
free_STRING(ap->sval);
mawk_cell_destroy(MAWK, &ap->cell);
MAWK_ZFREE(MAWK, ap);
if (--A->size == 0)
mawk_array_clear(MAWK, A);
}
}
static void mawk_array_load_orig(mawk_state_t *MAWK, mawk_array_t A, int cnt)
{
mawk_cell_t *cells; /* storage for A[1..cnt] */
int i; /* index into cells[] */
/* destroy the original array and set up the new */
if (A->type != AY_SPLIT || A->limit < cnt) {
mawk_array_clear(MAWK, A);
A->limit = (cnt & ~3) + 4;
A->ptr = mawk_zmalloc(MAWK, A->limit * sizeof(mawk_cell_t));
A->type = AY_SPLIT;
}
else
for (i = 0; i < A->size; i++)
mawk_cell_destroy(MAWK, (mawk_cell_t *) A->ptr + i);
cells = (mawk_cell_t *) A->ptr;
A->size = cnt;
#define action(idx, sval) \
cells[idx].type = C_MBSTRN; \
cells[idx].ptr = (PTR) sval;
mawk_split_walk(MAWK, cnt, 1, action);
#undef action
}
static void mawk_array_clear_orig(mawk_state_t *MAWK, mawk_array_t A)
{
int i;
ANODE *p, *q;
if (A->type == AY_SPLIT) {
for (i = 0; i < A->size; i++)
mawk_cell_destroy(MAWK, (mawk_cell_t *) A->ptr + i);
mawk_zfree(MAWK, A->ptr, A->limit * sizeof(mawk_cell_t));
}
else if (A->type & AY_STR) {
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
for (i = 0; i <= A->hmask; i++) {
p = table[i].slink;
while (p) {
q = p;
p = q->slink;
free_STRING(q->sval);
mawk_cell_destroy(MAWK, &q->cell);
MAWK_ZFREE(MAWK, q);
}
}
mawk_zfree(MAWK, A->ptr, (A->hmask + 1) * sizeof(DUAL_LINK));
}
else if (A->type & AY_INT) {
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
for (i = 0; i <= A->hmask; i++) {
p = table[i].ilink;
while (p) {
q = p;
p = q->ilink;
mawk_cell_destroy(MAWK, &q->cell);
MAWK_ZFREE(MAWK, q);
}
}
mawk_zfree(MAWK, A->ptr, (A->hmask + 1) * sizeof(DUAL_LINK));
}
mawk_array_clear_common(MAWK, A);
}
static mawk_string_t **mawk_array_loop_vector_orig(mawk_state_t *MAWK, mawk_array_t A, unsigned *sizep)
{
mawk_string_t **ret;
*sizep = A->size;
if (A->size > 0) {
if (!(A->type & AY_STR))
add_string_associations(MAWK, A);
ret = (mawk_string_t **) mawk_malloc(MAWK, A->size * sizeof(mawk_string_t *));
{
int r = 0; /* indexes ret */
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
int i; /* indexes table */
ANODE *p; /* walks slists */
for (i = 0; i <= A->hmask; i++) {
for (p = table[i].slink; p; p = p->slink) {
ret[r++] = p->sval;
p->sval->ref_cnt++;
}
}
}
return ret;
}
else
return (mawk_string_t **) 0;
}
static ANODE *mawk_find_by_ival(mawk_state_t *MAWK, mawk_array_t A, Int ival, int create_flag)
{
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
unsigned index = ival & A->hmask;
ANODE *p = table[index].ilink; /* walks ilist */
ANODE *q = (ANODE *) 0; /* trails p */
while (1) {
if (!p) {
/* search failed */
if (A->type & AY_STR) {
/* need to search by string */
char buff[256];
mawk_string_t *sval;
sprintf(buff, INT_FMT, ival);
sval = mawk_new_STRING(MAWK, buff);
p = mawk_find_by_sval(MAWK, A, sval, create_flag);
free_STRING(sval);
if (!p)
return (ANODE *) 0;
}
else if (create_flag) {
p = MAWK_ZMALLOC(MAWK, ANODE);
p->sval = (mawk_string_t *) 0;
p->cell.type = C_NOINIT;
if (++A->size > A->limit) {
double_the_hash_table(MAWK, A); /* changes table, may change index */
table = (DUAL_LINK *) A->ptr;
index = A->hmask & ival;
}
}
else
return (ANODE *) 0;
p->ival = ival;
A->type |= AY_INT;
break;
}
else if (p->ival == ival) {
/* found it, now move to the front */
if (!q) /* already at the front */
return p;
/* delete for mawk_insertion at the front */
q->ilink = p->ilink;
break;
}
q = p;
p = q->ilink;
}
/* mawk_insert at the front */
p->ilink = table[index].ilink;
table[index].ilink = p;
return p;
}
static ANODE *mawk_find_by_sval(mawk_state_t *MAWK, mawk_array_t A, mawk_string_t *sval, int create_flag)
{
unsigned hval = ahash(sval);
char *str = sval->str;
DUAL_LINK *table;
int index;
ANODE *p; /* walks list */
ANODE *q = (ANODE *) 0; /* trails p */
if (!(A->type & AY_STR))
add_string_associations(MAWK, A);
table = (DUAL_LINK *) A->ptr;
index = hval & A->hmask;
p = table[index].slink;
while (1) {
if (!p) {
if (create_flag) {
{
p = MAWK_ZMALLOC(MAWK, ANODE);
p->sval = sval;
sval->ref_cnt++;
p->ival = NOT_AN_IVALUE;
p->hval = hval;
p->cell.type = C_NOINIT;
if (++A->size > A->limit) {
double_the_hash_table(MAWK, A); /* changes table, may change index */
table = (DUAL_LINK *) A->ptr;
index = hval & A->hmask;
}
}
break;
}
else
return (ANODE *) 0;
}
else if (p->hval == hval && strcmp(p->sval->str, str) == 0) {
/* found */
if (!q) /* already at the front */
return p;
else { /* delete for move to the front */
q->slink = p->slink;
break;
}
}
q = p;
p = q->slink;
}
p->slink = table[index].slink;
table[index].slink = p;
return p;
}
static void add_string_associations(mawk_state_t *MAWK, mawk_array_t A)
{
if (A->type == AY_NULL)
make_empty_table(MAWK, A, AY_STR);
else {
DUAL_LINK *table;
int i; /* walks table */
ANODE *p; /* walks ilist */
char buff[256];
if (A->type == AY_SPLIT)
convert_split_array_to_table(MAWK, A);
table = (DUAL_LINK *) A->ptr;
for (i = 0; i <= A->hmask; i++) {
p = table[i].ilink;
while (p) {
sprintf(buff, INT_FMT, p->ival);
p->sval = mawk_new_STRING(MAWK, buff);
p->hval = ahash(p->sval);
p->slink = table[A->hmask & p->hval].slink;
table[A->hmask & p->hval].slink = p;
p = p->ilink;
}
}
A->type |= AY_STR;
}
}
static void make_empty_table(mawk_state_t *MAWK, mawk_array_t A, int type)
{
/* type -> AY_INT or AY_STR */
size_t sz = (STARTING_HMASK + 1) * sizeof(DUAL_LINK);
A->ptr = mawk_zmalloc(MAWK, sz);
if (A->ptr != NULL) {
A->type = type;
A->hmask = STARTING_HMASK;
A->limit = hmask_to_limit(STARTING_HMASK);
memset(A->ptr, 0, sz);
}
else {
A->limit = 0;
}
}
static void convert_split_array_to_table(mawk_state_t *MAWK, mawk_array_t A)
{
mawk_cell_t *cells = (mawk_cell_t *) A->ptr;
int i; /* walks cells */
DUAL_LINK *table;
int j; /* walks table */
unsigned entry_limit = A->limit;
A->hmask = STARTING_HMASK;
A->limit = hmask_to_limit(STARTING_HMASK);
while (A->size > A->limit) {
A->hmask = (A->hmask << 1) + 1; /* double the size */
A->limit = hmask_to_limit(A->hmask);
}
{
size_t sz = (A->hmask + 1) * sizeof(DUAL_LINK);
A->ptr = memset(mawk_zmalloc(MAWK, sz), 0, sz);
table = (DUAL_LINK *) A->ptr;
}
/* mawk_insert each cells[i] in the new mawk_hash table on an ilist */
for (i = 0, j = 1; i < A->size; i++) {
ANODE *p = MAWK_ZMALLOC(MAWK, ANODE);
p->sval = (mawk_string_t *) 0;
p->ival = i + 1;
p->cell = cells[i];
p->ilink = table[j].ilink;
table[j].ilink = p;
j++;
j &= A->hmask;
}
A->type = AY_INT;
mawk_zfree(MAWK, cells, entry_limit * sizeof(mawk_cell_t));
}
static void double_the_hash_table(mawk_state_t *MAWK, mawk_array_t A)
{
unsigned old_hmask = A->hmask;
unsigned new_hmask = (old_hmask << 1) + 1;
DUAL_LINK *table;
A->ptr = mawk_zrealloc(MAWK, A->ptr, (old_hmask + 1) * sizeof(DUAL_LINK), (new_hmask + 1) * sizeof(DUAL_LINK));
table = (DUAL_LINK *) A->ptr;
/* zero out the new part which is the back half */
memset(&table[old_hmask + 1], 0, (old_hmask + 1) * sizeof(DUAL_LINK));
if (A->type & AY_STR) {
int i; /* index to old lists */
int j; /* index to new lists */
ANODE *p; /* walks an old list */
ANODE *q; /* trails p for deletion */
ANODE *tail; /* builds new list from the back */
ANODE dummy0, dummy1;
for (i = 0, j = old_hmask + 1; i <= old_hmask; i++, j++) {
q = &dummy0;
q->slink = p = table[i].slink;
tail = &dummy1;
while (p) {
if ((p->hval & new_hmask) != i) { /* move it */
q->slink = p->slink;
tail = tail->slink = p;
}
else
q = p;
p = q->slink;
}
table[i].slink = dummy0.slink;
tail->slink = (ANODE *) 0;
table[j].slink = dummy1.slink;
}
}
if (A->type & AY_INT) {
int i; /* index to old lists */
int j; /* index to new lists */
ANODE *p; /* walks an old list */
ANODE *q; /* trails p for deletion */
ANODE *tail; /* builds new list from the back */
ANODE dummy0, dummy1;
for (i = 0, j = old_hmask + 1; i <= old_hmask; i++, j++) {
q = &dummy0;
q->ilink = p = table[i].ilink;
tail = &dummy1;
while (p) {
if ((p->ival & new_hmask) != i) { /* move it */
q->ilink = p->ilink;
tail = tail->ilink = p;
}
else
q = p;
p = q->ilink;
}
table[i].ilink = dummy0.ilink;
tail->ilink = (ANODE *) 0;
table[j].ilink = dummy1.ilink;
}
}
A->hmask = new_hmask;
A->limit = hmask_to_limit(new_hmask);
}
static unsigned ahash(mawk_string_t *sval)
{
unsigned sum1 = sval->len;
unsigned sum2 = sum1;
unsigned char *p, *q;
if (sum1 <= 10) {
for (p = (unsigned char *) sval->str; *p; p++) {
sum1 += sum1 + *p;
sum2 += sum1;
}
}
else {
int cnt = 5;
p = (unsigned char *) sval->str; /* p starts at the front */
q = (unsigned char *) sval->str + (sum1 - 1); /* q starts at the back */
while (cnt) {
cnt--;
sum1 += sum1 + *p;
sum2 += sum1;
sum1 += sum1 + *q;
sum2 += sum1;
p++;
q--;
}
}
return sum2;
}
/* iterator for array_generic (for array implementations built on top or array_orig */
typedef struct {
int i; /* indexes table */
ANODE *p; /* walks slists */
mawk_cell_t ridx;
} array_it_orig_t;
void *mawk_array_it_start_orig(mawk_state_t *MAWK, mawk_array_t A)
{
array_it_orig_t *it;
if (A->size > 0) {
if (!(A->type & AY_STR))
add_string_associations(MAWK, A);
}
it = mawk_zmalloc(MAWK, sizeof(array_it_orig_t));
if (it == NULL)
return NULL;
it->i = -1;
it->p = NULL;
it->ridx.type = C_STRING;
return it;
}
const mawk_cell_t *mawk_array_it_next_orig(mawk_state_t *MAWK, mawk_array_t A, void *iterator)
{
DUAL_LINK *table = (DUAL_LINK *) A->ptr;
array_it_orig_t *it = iterator;
if (A->size <= 0)
return NULL;
if ((it->i >= 0) && (it->i > A->hmask))
return NULL;
if (it->p == NULL) {
/* this slot is over */
for(;;) {
it->i++; /* check next slot in the array of linked lists */
if (it->i > A->hmask)
return NULL; /* hit end of table */
it->p = table[it->i].slink;
if (it->p != NULL)
break; /* found an entry, go on returning it */
}
}
it->ridx.ptr = it->p->sval;
it->p = it->p->slink;
return &it->ridx;
}
void mawk_array_it_stop_orig(mawk_state_t *MAWK, mawk_array_t A, void *iterator)
{
array_it_orig_t *it = iterator;
mawk_zfree(MAWK, it, sizeof(array_it_orig_t));
}
/* public implementation array */
array_imp_t mawk_array_orig_imp = {
mawk_array_find_orig,
mawk_array_set_orig,
mawk_array_delete_orig,
mawk_array_clear_orig,
mawk_array_loop_vector_orig,
mawk_array_load_orig,
mawk_array_it_start_orig,
mawk_array_it_next_orig,
mawk_array_it_stop_orig
};