/* Parse tree node implementation */

#include "Python.h"

#include "node.h"

#include "errcode.h"

node *

PyNode_New(int type)

{

	node *n = (node *) PyObject_MALLOC(1 * sizeof(node));

	if (n == NULL)

		return NULL;

	n->n_type = type;

	n->n_str = NULL;

	n->n_lineno = 0;

	n->n_nchildren = 0;

	n->n_child = NULL;

	return n;

}

/* See comments at XXXROUNDUP below.  Returns -1 on overflow. */

static int

fancy_roundup(int n)

{

	/* Round up to the closest power of 2 >= n. */

	int result = 256;

	assert(n > 128);

	while (result < n) {

		result <<= 1;

		if (result <= 0)

			return -1;

	}

	return result;

}

/* A gimmick to make massive numbers of reallocs quicker.  The result is

 * a number >= the input.  In PyNode_AddChild, it's used like so, when

 * we're about to add child number current_size + 1:

 *

 *     if XXXROUNDUP(current_size) < XXXROUNDUP(current_size + 1):

 *         allocate space for XXXROUNDUP(current_size + 1) total children

 *     else:

 *         we already have enough space

 *

 * Since a node starts out empty, we must have

 *

 *     XXXROUNDUP(0) < XXXROUNDUP(1)

 *

 * so that we allocate space for the first child.  One-child nodes are very

 * common (presumably that would change if we used a more abstract form

 * of syntax tree), so to avoid wasting memory it's desirable that

 * XXXROUNDUP(1) == 1.  That in turn forces XXXROUNDUP(0) == 0.

 *

 * Else for 2 <= n <= 128, we round up to the closest multiple of 4.  Why 4?

 * Rounding up to a multiple of an exact power of 2 is very efficient, and

 * most nodes with more than one child have <= 4 kids.

 *

 * Else we call fancy_roundup() to grow proportionately to n.  We've got an

 * extreme case then (like test_longexp.py), and on many platforms doing

 * anything less than proportional growth leads to exorbitant runtime

 * (e.g., MacPython), or extreme fragmentation of user address space (e.g.,

 * Win98).

 *

 * In a run of compileall across the 2.3a0 Lib directory, Andrew MacIntyre

 * reported that, with this scheme, 89% of PyObject_REALLOC calls in

 * PyNode_AddChild passed 1 for the size, and 9% passed 4.  So this usually

 * wastes very little memory, but is very effective at sidestepping

 * platform-realloc disasters on vulnerable platforms.

 *

 * Note that this would be straightforward if a node stored its current

 * capacity.  The code is tricky to avoid that.

 */

#define XXXROUNDUP(n) ((n) <= 1 ? (n) : 		\

		       (n) <= 128 ? (((n) + 3) & ~3) :	\

		       fancy_roundup(n))

int

PyNode_AddChild(register node *n1, int type, char *str, int lineno, int col_offset)

{

	const int nch = n1->n_nchildren;

	int current_capacity;

	int required_capacity;

	node *n;

	if (nch == INT_MAX || nch < 0)

		return E_OVERFLOW;

	current_capacity = XXXROUNDUP(nch);

	required_capacity = XXXROUNDUP(nch + 1);

	if (current_capacity < 0 || required_capacity < 0)

		return E_OVERFLOW;

	if (current_capacity < required_capacity) {

		if (required_capacity > PY_SIZE_MAX / sizeof(node)) {

			return E_NOMEM;

		}

		n = n1->n_child;

		n = (node *) PyObject_REALLOC(n,

					      required_capacity * sizeof(node));

		if (n == NULL)

			return E_NOMEM;

		n1->n_child = n;

	}

	n = &n1->n_child[n1->n_nchildren++];

	n->n_type = type;

	n->n_str = str;

	n->n_lineno = lineno;

	n->n_col_offset = col_offset;

	n->n_nchildren = 0;

	n->n_child = NULL;

	return 0;

}

/* Forward */

static void freechildren(node *);

void

PyNode_Free(node *n)

{

	if (n != NULL) {

		freechildren(n);

		PyObject_FREE(n);

	}

}

static void

freechildren(node *n)

{

	int i;

	for (i = NCH(n); --i >= 0; )

		freechildren(CHILD(n, i));

	if (n->n_child != NULL)

		PyObject_FREE(n->n_child);

	if (STR(n) != NULL)

		PyObject_FREE(STR(n));

}