GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — cpython/Parser/node.c at master · python-emscripten/cpython Expand file tree/ Copy pathnode.cMore file actions 189 lines (171 loc) · 5.1 KB / Copy pathnode.cFile metadata and controls189 lines (171 loc) · 5.1 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 /* 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_end_lineno = 0; n->n_col_offset = 0; n->n_end_col_offset = -1; 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 ? (int)_Py_SIZE_ROUND_UP((n), 4) : \ fancy_roundup(n)) void _PyNode_FinalizeEndPos(node *n) { int nch = NCH(n); node *last; if (nch == 0) { return; } last = CHILD(n, nch - 1); _PyNode_FinalizeEndPos(last); n->n_end_lineno = last->n_end_lineno; n->n_end_col_offset = last->n_end_col_offset; } int PyNode_AddChild(node *n1, int type, char *str, int lineno, int col_offset, int end_lineno, int end_col_offset) { const int nch = n1->n_nchildren; int current_capacity; int required_capacity; node *n; // finalize end position of previous node (if any) if (nch > 0) { _PyNode_FinalizeEndPos(CHILD(n1, nch - 1)); } 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 ((size_t)required_capacity > 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_end_lineno = end_lineno; // this and below will be updates after all children are added. n->n_end_col_offset = end_col_offset; n->n_nchildren = 0; n->n_child = NULL; return 0; } /* Forward */ static void freechildren(node *); static Py_ssize_t sizeofchildren(node *n); void PyNode_Free(node *n) { if (n != NULL) { freechildren(n); PyObject_FREE(n); } } Py_ssize_t _PyNode_SizeOf(node *n) { Py_ssize_t res = 0; if (n != NULL) res = sizeof(node) + sizeofchildren(n); return res; } 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)); } static Py_ssize_t sizeofchildren(node *n) { Py_ssize_t res = 0; int i; for (i = NCH(n); --i >= 0; ) res += sizeofchildren(CHILD(n, i)); if (n->n_child != NULL) /* allocated size of n->n_child array */ res += XXXROUNDUP(NCH(n)) * sizeof(node); if (STR(n) != NULL) res += strlen(STR(n)) + 1; return res; } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |