Vladimir Marangozov | 58e64a8 | 2000-09-03 23:47:08 +0000 | [diff] [blame] | 1 | /* Parse tree node implementation */ |
| 2 | |
Tim Peters | 1d6a729 | 2000-09-26 06:11:54 +0000 | [diff] [blame] | 3 | #include "Python.h" |
Vladimir Marangozov | 58e64a8 | 2000-09-03 23:47:08 +0000 | [diff] [blame] | 4 | #include "node.h" |
| 5 | #include "errcode.h" |
| 6 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 7 | node * |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 8 | PyNode_New(int type) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 9 | { |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 10 | node *n = PyMem_NEW(node, 1); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 11 | if (n == NULL) |
| 12 | return NULL; |
| 13 | n->n_type = type; |
| 14 | n->n_str = NULL; |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 15 | n->n_lineno = 0; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 16 | n->n_nchildren = 0; |
| 17 | n->n_child = NULL; |
| 18 | return n; |
| 19 | } |
| 20 | |
Tim Peters | 755ebea | 2002-07-08 06:32:09 +0000 | [diff] [blame^] | 21 | /* See comments at XXXROUNDUP below. */ |
| 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 | return result; |
| 31 | } |
| 32 | |
| 33 | /* A gimmick to make massive numbers of reallocs quicker. The result is |
| 34 | * a number >= the input. For n=0 we must return 0. |
| 35 | * For n=1, we return 1, to avoid wasting memory in common 1-child nodes |
| 36 | * (XXX are those actually common?). |
| 37 | * Else for n <= 128, round up to the closest multiple of 4. Why 4? |
| 38 | * Rounding up to a multiple of an exact power of 2 is very efficient. |
| 39 | * Else call fancy_roundup() to grow proportionately to n. We've got an |
| 40 | * extreme case then (like test_longexp.py), and on many platforms doing |
| 41 | * anything less than proportional growth leads to exorbitant runtime |
| 42 | * (e.g., MacPython), or extreme fragmentation of user address space (e.g., |
| 43 | * Win98). |
| 44 | * This would be straightforward if a node stored its current capacity. The |
| 45 | * code is tricky to avoid that. |
| 46 | */ |
| 47 | #define XXXROUNDUP(n) ((n) == 1 ? 1 : \ |
| 48 | (n) <= 128 ? (((n) + 3) & ~3) : \ |
| 49 | fancy_roundup(n)) |
| 50 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 51 | |
Jeremy Hylton | 9498806 | 2000-06-20 19:10:44 +0000 | [diff] [blame] | 52 | int |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 53 | PyNode_AddChild(register node *n1, int type, char *str, int lineno) |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 54 | { |
Tim Peters | 755ebea | 2002-07-08 06:32:09 +0000 | [diff] [blame^] | 55 | const int nch = n1->n_nchildren; |
| 56 | int current_capacity; |
| 57 | int required_capacity; |
| 58 | node *n; |
| 59 | |
Fred Drake | ef8ace3 | 2000-08-24 00:32:09 +0000 | [diff] [blame] | 60 | if (nch == INT_MAX || nch < 0) |
Jeremy Hylton | 9498806 | 2000-06-20 19:10:44 +0000 | [diff] [blame] | 61 | return E_OVERFLOW; |
Tim Peters | 755ebea | 2002-07-08 06:32:09 +0000 | [diff] [blame^] | 62 | |
| 63 | current_capacity = XXXROUNDUP(nch); |
| 64 | required_capacity = XXXROUNDUP(nch + 1); |
| 65 | if (current_capacity < required_capacity) { |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 66 | n = n1->n_child; |
Tim Peters | 755ebea | 2002-07-08 06:32:09 +0000 | [diff] [blame^] | 67 | PyMem_RESIZE(n, node, required_capacity); |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 68 | if (n == NULL) |
Jeremy Hylton | 9498806 | 2000-06-20 19:10:44 +0000 | [diff] [blame] | 69 | return E_NOMEM; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 70 | n1->n_child = n; |
| 71 | } |
Tim Peters | 755ebea | 2002-07-08 06:32:09 +0000 | [diff] [blame^] | 72 | |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 73 | n = &n1->n_child[n1->n_nchildren++]; |
| 74 | n->n_type = type; |
| 75 | n->n_str = str; |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 76 | n->n_lineno = lineno; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 77 | n->n_nchildren = 0; |
| 78 | n->n_child = NULL; |
Jeremy Hylton | 9498806 | 2000-06-20 19:10:44 +0000 | [diff] [blame] | 79 | return 0; |
Guido van Rossum | 85a5fbb | 1990-10-14 12:07:46 +0000 | [diff] [blame] | 80 | } |
Guido van Rossum | 03a24cd | 1990-11-18 17:37:06 +0000 | [diff] [blame] | 81 | |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 82 | /* Forward */ |
Tim Peters | dbd9ba6 | 2000-07-09 03:09:57 +0000 | [diff] [blame] | 83 | static void freechildren(node *); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 84 | |
| 85 | |
| 86 | void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 87 | PyNode_Free(node *n) |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 88 | { |
| 89 | if (n != NULL) { |
| 90 | freechildren(n); |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 91 | PyMem_DEL(n); |
Guido van Rossum | 3f5da24 | 1990-12-20 15:06:42 +0000 | [diff] [blame] | 92 | } |
| 93 | } |
| 94 | |
Guido van Rossum | 03a24cd | 1990-11-18 17:37:06 +0000 | [diff] [blame] | 95 | static void |
Thomas Wouters | 23c9e00 | 2000-07-22 19:20:54 +0000 | [diff] [blame] | 96 | freechildren(node *n) |
Guido van Rossum | 03a24cd | 1990-11-18 17:37:06 +0000 | [diff] [blame] | 97 | { |
| 98 | int i; |
| 99 | for (i = NCH(n); --i >= 0; ) |
| 100 | freechildren(CHILD(n, i)); |
| 101 | if (n->n_child != NULL) |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 102 | PyMem_DEL(n->n_child); |
Guido van Rossum | 03a24cd | 1990-11-18 17:37:06 +0000 | [diff] [blame] | 103 | if (STR(n) != NULL) |
Guido van Rossum | 86bea46 | 1997-04-29 21:03:06 +0000 | [diff] [blame] | 104 | PyMem_DEL(STR(n)); |
Guido van Rossum | 03a24cd | 1990-11-18 17:37:06 +0000 | [diff] [blame] | 105 | } |