diff options
Diffstat (limited to 'Python')
| -rw-r--r-- | Python/ast.c | 13 | ||||
| -rw-r--r-- | Python/hashtable.c | 180 | ||||
| -rw-r--r-- | Python/marshal.c | 2 |
3 files changed, 74 insertions, 121 deletions
diff --git a/Python/ast.c b/Python/ast.c index 1a4a3110e6..2d20ca62aa 100644 --- a/Python/ast.c +++ b/Python/ast.c @@ -3164,10 +3164,7 @@ ast_for_expr_stmt(struct compiling *c, const node *n) expr1 = ast_for_testlist(c, ch); if (!expr1) return NULL; - if(!set_context(c, expr1, Store, ch)) - return NULL; - /* set_context checks that most expressions are not the left side. - Augmented assignments can only have a name, a subscript, or an + /* Augmented assignments can only have a name, a subscript, or an attribute on the left, though, so we have to explicitly check for those. */ switch (expr1->kind) { @@ -3176,10 +3173,16 @@ ast_for_expr_stmt(struct compiling *c, const node *n) case Subscript_kind: break; default: - ast_error(c, ch, "illegal expression for augmented assignment"); + ast_error(c, ch, "'%s' is an illegal expression for augmented assignment", + get_expr_name(expr1)); return NULL; } + /* set_context checks that most expressions are not the left side. */ + if(!set_context(c, expr1, Store, ch)) { + return NULL; + } + ch = CHILD(n, 2); if (TYPE(ch) == testlist) expr2 = ast_for_testlist(c, ch); diff --git a/Python/hashtable.c b/Python/hashtable.c index d1467ad94e..b92e8ca08c 100644 --- a/Python/hashtable.c +++ b/Python/hashtable.c @@ -60,7 +60,7 @@ ((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY)) /* Forward declaration */ -static void hashtable_rehash(_Py_hashtable_t *ht); +static int hashtable_rehash(_Py_hashtable_t *ht); static void _Py_slist_init(_Py_slist_t *list) @@ -119,66 +119,20 @@ round_size(size_t s) size_t _Py_hashtable_size(const _Py_hashtable_t *ht) { - size_t size; - - size = sizeof(_Py_hashtable_t); - + size_t size = sizeof(_Py_hashtable_t); /* buckets */ - size += ht->num_buckets * sizeof(_Py_hashtable_entry_t *); - + size += ht->nbuckets * sizeof(_Py_hashtable_entry_t *); /* entries */ - size += ht->entries * sizeof(_Py_hashtable_entry_t); - + size += ht->nentries * sizeof(_Py_hashtable_entry_t); return size; } -#ifdef Py_DEBUG -void -_Py_hashtable_print_stats(_Py_hashtable_t *ht) -{ - size_t size; - size_t chain_len, max_chain_len, total_chain_len, nchains; - _Py_hashtable_entry_t *entry; - size_t hv; - double load; - - size = _Py_hashtable_size(ht); - - load = (double)ht->entries / ht->num_buckets; - - max_chain_len = 0; - total_chain_len = 0; - nchains = 0; - for (hv = 0; hv < ht->num_buckets; hv++) { - entry = TABLE_HEAD(ht, hv); - if (entry != NULL) { - chain_len = 0; - for (; entry; entry = ENTRY_NEXT(entry)) { - chain_len++; - } - if (chain_len > max_chain_len) - max_chain_len = chain_len; - total_chain_len += chain_len; - nchains++; - } - } - printf("hash table %p: entries=%" - PY_FORMAT_SIZE_T "u/%" PY_FORMAT_SIZE_T "u (%.0f%%), ", - (void *)ht, ht->entries, ht->num_buckets, load * 100.0); - if (nchains) - printf("avg_chain_len=%.1f, ", (double)total_chain_len / nchains); - printf("max_chain_len=%" PY_FORMAT_SIZE_T "u, %" PY_FORMAT_SIZE_T "u KiB\n", - max_chain_len, size / 1024); -} -#endif - - _Py_hashtable_entry_t * _Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key) { Py_uhash_t key_hash = ht->hash_func(key); - size_t index = key_hash & (ht->num_buckets - 1); + size_t index = key_hash & (ht->nbuckets - 1); _Py_hashtable_entry_t *entry = entry = TABLE_HEAD(ht, index); while (1) { if (entry == NULL) { @@ -200,7 +154,7 @@ static _Py_hashtable_entry_t * _Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key) { Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key); - size_t index = key_hash & (ht->num_buckets - 1); + size_t index = key_hash & (ht->nbuckets - 1); _Py_hashtable_entry_t *entry = entry = TABLE_HEAD(ht, index); while (1) { if (entry == NULL) { @@ -220,7 +174,7 @@ void* _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key) { Py_uhash_t key_hash = ht->hash_func(key); - size_t index = key_hash & (ht->num_buckets - 1); + size_t index = key_hash & (ht->nbuckets - 1); _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index); _Py_hashtable_entry_t *previous = NULL; @@ -238,12 +192,13 @@ _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key) _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous, (_Py_slist_item_t *)entry); - ht->entries--; + ht->nentries--; void *value = entry->value; ht->alloc.free(entry); - if ((float)ht->entries / (float)ht->num_buckets < HASHTABLE_LOW) { + if ((float)ht->nentries / (float)ht->nbuckets < HASHTABLE_LOW) { + // Ignore failure: error cannot be reported to the caller hashtable_rehash(ht); } return value; @@ -263,8 +218,6 @@ _Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value) assert(entry == NULL); #endif - Py_uhash_t key_hash = ht->hash_func(key); - size_t index = key_hash & (ht->num_buckets - 1); entry = ht->alloc.malloc(sizeof(_Py_hashtable_entry_t)); if (entry == NULL) { @@ -272,15 +225,21 @@ _Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value) return -1; } - entry->key_hash = key_hash; + entry->key_hash = ht->hash_func(key); entry->key = (void *)key; entry->value = value; - _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); - ht->entries++; + ht->nentries++; + if ((float)ht->nentries / (float)ht->nbuckets > HASHTABLE_HIGH) { + if (hashtable_rehash(ht) < 0) { + ht->nentries--; + ht->alloc.free(entry); + return -1; + } + } - if ((float)ht->entries / (float)ht->num_buckets > HASHTABLE_HIGH) - hashtable_rehash(ht); + size_t index = entry->key_hash & (ht->nbuckets - 1); + _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry); return 0; } @@ -303,61 +262,53 @@ _Py_hashtable_foreach(_Py_hashtable_t *ht, _Py_hashtable_foreach_func func, void *user_data) { - _Py_hashtable_entry_t *entry; - size_t hv; - - for (hv = 0; hv < ht->num_buckets; hv++) { - for (entry = TABLE_HEAD(ht, hv); entry; entry = ENTRY_NEXT(entry)) { + for (size_t hv = 0; hv < ht->nbuckets; hv++) { + _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, hv); + while (entry != NULL) { int res = func(ht, entry->key, entry->value, user_data); - if (res) + if (res) { return res; + } + entry = ENTRY_NEXT(entry); } } return 0; } -static void +static int hashtable_rehash(_Py_hashtable_t *ht) { - size_t buckets_size, new_size, bucket; - _Py_slist_t *old_buckets = NULL; - size_t old_num_buckets; - - new_size = round_size((size_t)(ht->entries * HASHTABLE_REHASH_FACTOR)); - if (new_size == ht->num_buckets) - return; - - old_num_buckets = ht->num_buckets; + size_t new_size = round_size((size_t)(ht->nentries * HASHTABLE_REHASH_FACTOR)); + if (new_size == ht->nbuckets) { + return 0; + } - buckets_size = new_size * sizeof(ht->buckets[0]); - old_buckets = ht->buckets; - ht->buckets = ht->alloc.malloc(buckets_size); - if (ht->buckets == NULL) { - /* cancel rehash on memory allocation failure */ - ht->buckets = old_buckets ; + size_t buckets_size = new_size * sizeof(ht->buckets[0]); + _Py_slist_t *new_buckets = ht->alloc.malloc(buckets_size); + if (new_buckets == NULL) { /* memory allocation failed */ - return; + return -1; } - memset(ht->buckets, 0, buckets_size); - - ht->num_buckets = new_size; - - for (bucket = 0; bucket < old_num_buckets; bucket++) { - _Py_hashtable_entry_t *entry, *next; - for (entry = BUCKETS_HEAD(old_buckets[bucket]); entry != NULL; entry = next) { - size_t entry_index; - + memset(new_buckets, 0, buckets_size); + for (size_t bucket = 0; bucket < ht->nbuckets; bucket++) { + _Py_hashtable_entry_t *entry = BUCKETS_HEAD(ht->buckets[bucket]); + while (entry != NULL) { assert(ht->hash_func(entry->key) == entry->key_hash); - next = ENTRY_NEXT(entry); - entry_index = entry->key_hash & (new_size - 1); + _Py_hashtable_entry_t *next = ENTRY_NEXT(entry); + size_t entry_index = entry->key_hash & (new_size - 1); + + _Py_slist_prepend(&new_buckets[entry_index], (_Py_slist_item_t*)entry); - _Py_slist_prepend(&ht->buckets[entry_index], (_Py_slist_item_t*)entry); + entry = next; } } - ht->alloc.free(old_buckets); + ht->alloc.free(ht->buckets); + ht->nbuckets = new_size; + ht->buckets = new_buckets; + return 0; } @@ -368,10 +319,7 @@ _Py_hashtable_new_full(_Py_hashtable_hash_func hash_func, _Py_hashtable_destroy_func value_destroy_func, _Py_hashtable_allocator_t *allocator) { - _Py_hashtable_t *ht; - size_t buckets_size; _Py_hashtable_allocator_t alloc; - if (allocator == NULL) { alloc.malloc = PyMem_Malloc; alloc.free = PyMem_Free; @@ -380,14 +328,15 @@ _Py_hashtable_new_full(_Py_hashtable_hash_func hash_func, alloc = *allocator; } - ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); - if (ht == NULL) + _Py_hashtable_t *ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t)); + if (ht == NULL) { return ht; + } - ht->num_buckets = HASHTABLE_MIN_SIZE; - ht->entries = 0; + ht->nbuckets = HASHTABLE_MIN_SIZE; + ht->nentries = 0; - buckets_size = ht->num_buckets * sizeof(ht->buckets[0]); + size_t buckets_size = ht->nbuckets * sizeof(ht->buckets[0]); ht->buckets = alloc.malloc(buckets_size); if (ht->buckets == NULL) { alloc.free(ht); @@ -435,25 +384,26 @@ _Py_hashtable_destroy_entry(_Py_hashtable_t *ht, _Py_hashtable_entry_t *entry) void _Py_hashtable_clear(_Py_hashtable_t *ht) { - _Py_hashtable_entry_t *entry, *next; - size_t i; - - for (i=0; i < ht->num_buckets; i++) { - for (entry = TABLE_HEAD(ht, i); entry != NULL; entry = next) { - next = ENTRY_NEXT(entry); + for (size_t i=0; i < ht->nbuckets; i++) { + _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i); + while (entry != NULL) { + _Py_hashtable_entry_t *next = ENTRY_NEXT(entry); _Py_hashtable_destroy_entry(ht, entry); + entry = next; } _Py_slist_init(&ht->buckets[i]); } - ht->entries = 0; - hashtable_rehash(ht); + ht->nentries = 0; + // Ignore failure: clear function is not expected to fail + // because of a memory allocation failure. + (void)hashtable_rehash(ht); } void _Py_hashtable_destroy(_Py_hashtable_t *ht) { - for (size_t i = 0; i < ht->num_buckets; i++) { + for (size_t i = 0; i < ht->nbuckets; i++) { _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i); while (entry) { _Py_hashtable_entry_t *entry_next = ENTRY_NEXT(entry); diff --git a/Python/marshal.c b/Python/marshal.c index b096ff8932..a0f6b98126 100644 --- a/Python/marshal.c +++ b/Python/marshal.c @@ -312,7 +312,7 @@ w_ref(PyObject *v, char *flag, WFILE *p) w_long(w, p); return 1; } else { - size_t s = p->hashtable->entries; + size_t s = p->hashtable->nentries; /* we don't support long indices */ if (s >= 0x7fffffff) { PyErr_SetString(PyExc_ValueError, "too many objects"); |