Staging
v0.5.1
v0.5.1
https://github.com/python/cpython
Revision 328e3775df24c418b921c140c78e4e964f85b09d authored by Benjamin Peterson on 06 May 2010, 22:49:28 UTC, committed by Benjamin Peterson on 06 May 2010, 22:49:28 UTC
1 parent 7aaef84
Tip revision: 328e3775df24c418b921c140c78e4e964f85b09d authored by Benjamin Peterson on 06 May 2010, 22:49:28 UTC
ensure that availability information is on its own line at the end of the function docs
ensure that availability information is on its own line at the end of the function docs
Tip revision: 328e377
node.c
/* 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));
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...