← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python3.4/trusty-proposed

« back to all changes in this revision

Viewing changes to Parser/node.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-11-25 09:44:27 UTC
  • Revision ID: package-import@ubuntu.com-20131125094427-lzxj8ap5w01lmo7f
Tags: upstream-3.4~b1
Import upstream version 3.4~b1

Show diffs side-by-side

added added

removed removed

Lines of Context:
Parser/node.c
 
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 ? _Py_SIZE_ROUND_UP((n), 4) : \
 
75
               fancy_roundup(n))
 
76
 
 
77
 
 
78
int
 
79
PyNode_AddChild(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
static Py_ssize_t sizeofchildren(node *n);
 
118
 
 
119
 
 
120
void
 
121
PyNode_Free(node *n)
 
122
{
 
123
    if (n != NULL) {
 
124
        freechildren(n);
 
125
        PyObject_FREE(n);
 
126
    }
 
127
}
 
128
 
 
129
Py_ssize_t
 
130
_PyNode_SizeOf(node *n)
 
131
{
 
132
    Py_ssize_t res = 0;
 
133
 
 
134
    if (n != NULL)
 
135
        res = sizeof(node) + sizeofchildren(n);
 
136
    return res;
 
137
}
 
138
 
 
139
static void
 
140
freechildren(node *n)
 
141
{
 
142
    int i;
 
143
    for (i = NCH(n); --i >= 0; )
 
144
        freechildren(CHILD(n, i));
 
145
    if (n->n_child != NULL)
 
146
        PyObject_FREE(n->n_child);
 
147
    if (STR(n) != NULL)
 
148
        PyObject_FREE(STR(n));
 
149
}
 
150
 
 
151
static Py_ssize_t
 
152
sizeofchildren(node *n)
 
153
{
 
154
    Py_ssize_t res = 0;
 
155
    int i;
 
156
    for (i = NCH(n); --i >= 0; )
 
157
        res += sizeofchildren(CHILD(n, i));
 
158
    if (n->n_child != NULL)
 
159
        /* allocated size of n->n_child array */
 
160
        res += XXXROUNDUP(NCH(n)) * sizeof(node);
 
161
    if (STR(n) != NULL)
 
162
        res += strlen(STR(n)) + 1;
 
163
    return res;
 
164
}