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