1 /* Parse tree node implementation */

     2 

     3 #include "Python.h"

     4 #include "node.h"

     5 #include "errcode.h"

     6 

     7 node *

     8 PyNode_New(int type)

     9 {

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

    11 	if (n == NULL)

    12 		return NULL;

    13 	n->n_type = type;

    14 	n->n_str = NULL;

    15 	n->n_lineno = 0;

    16 	n->n_nchildren = 0;

    17 	n->n_child = NULL;

    18 	return n;

    19 }

    20 

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

    22 static int

    23 fancy_roundup(int n)

    24 {

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

    26 	int result = 256;

    27 	assert(n > 128);

    28 	while (result < n) {

    29 		result <<= 1;

    30 		if (result <= 0)

    31 			return -1;

    32 	}

    33 	return result;

    34 }

    35 

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

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

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

    39  *

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

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

    42  *     else:

    43  *         we already have enough space

    44  *

    45  * Since a node starts out empty, we must have

    46  *

    47  *     XXXROUNDUP(0) < XXXROUNDUP(1)

    48  *

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

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

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

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

    53  *

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

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

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

    57  *

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

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

    60  * anything less than proportional growth leads to exorbitant runtime

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

    62  * Win98).

    63  *

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

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

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

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

    68  * platform-realloc disasters on vulnerable platforms.

    69  *

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

    71  * capacity.  The code is tricky to avoid that.

    72  */

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

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

    75 		       fancy_roundup(n))

    76 

    77 

    78 int

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

    80 {

    81 	const int nch = n1->n_nchildren;

    82 	int current_capacity;

    83 	int required_capacity;

    84 	node *n;

    85 

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

    87 		return E_OVERFLOW;

    88 

    89 	current_capacity = XXXROUNDUP(nch);

    90 	required_capacity = XXXROUNDUP(nch + 1);

    91 	if (current_capacity < 0 || required_capacity < 0)

    92 		return E_OVERFLOW;

    93 	if (current_capacity < required_capacity) {

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

    95 			return E_NOMEM;

    96 		}

    97 		n = n1->n_child;

    98 		n = (node *) PyObject_REALLOC(n,

    99 					      required_capacity * sizeof(node));

   100 		if (n == NULL)

   101 			return E_NOMEM;

   102 		n1->n_child = n;

   103 	}

   104 

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

   106 	n->n_type = type;

   107 	n->n_str = str;

   108 	n->n_lineno = lineno;

   109 	n->n_col_offset = col_offset;

   110 	n->n_nchildren = 0;

   111 	n->n_child = NULL;

   112 	return 0;

   113 }

   114 

   115 /* Forward */

   116 static void freechildren(node *);

   117 

   118 

   119 void

   120 PyNode_Free(node *n)

   121 {

   122 	if (n != NULL) {

   123 		freechildren(n);

   124 		PyObject_FREE(n);

   125 	}

   126 }

   127 

   128 static void

   129 freechildren(node *n)

   130 {

   131 	int i;

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

   133 		freechildren(CHILD(n, i));

   134 	if (n->n_child != NULL)

   135 		PyObject_FREE(n->n_child);

   136 	if (STR(n) != NULL)

   137 		PyObject_FREE(STR(n));

   138 }