head	1.2;
access;
symbols
	micropython-1-5-2-base:1.1.1.1 MICROPYTHON:1.1.1;
locks; strict;
comment	@ * @;


1.2
date	2026.10.15.05.28.37;	author agc;	state dead;
branches;
next	1.1;
commitid	aHLdC1EGCUYk7xZG;

1.1
date	2016.01.14.01.38.50;	author agc;	state Exp;
branches
	1.1.1.1;
next	;
commitid	Q8liT0v6zMF95QQy;

1.1.1.1
date	2016.01.14.01.38.50;	author agc;	state Exp;
branches;
next	;
commitid	Q8liT0v6zMF95QQy;


desc
@@


1.2
log
@Remove waaaay old micropython sources which haven't been relevant for 10 years
@
text
@/*
 * This file is part of the Micro Python project, http://micropython.org/
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2013, 2014 Damien P. George
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "py/mpconfig.h"
#include "py/misc.h"
#include "py/runtime0.h"
#include "py/runtime.h"

// Fixed empty map. Useful when need to call kw-receiving functions
// without any keywords from C, etc.
const mp_map_t mp_const_empty_map = {
    .all_keys_are_qstrs = 0,
    .is_fixed = 1,
    .is_ordered = 1,
    .used = 0,
    .alloc = 0,
    .table = NULL,
};

// approximatelly doubling primes; made with Mathematica command: Table[Prime[Floor[(1.7)^n]], {n, 3, 24}]
// prefixed with zero for the empty case.
STATIC uint32_t doubling_primes[] = {0, 7, 19, 43, 89, 179, 347, 647, 1229, 2297, 4243, 7829, 14347, 26017, 47149, 84947, 152443, 273253, 488399, 869927, 1547173, 2745121, 4861607};

STATIC mp_uint_t get_doubling_prime_greater_or_equal_to(mp_uint_t x) {
    for (size_t i = 0; i < MP_ARRAY_SIZE(doubling_primes); i++) {
        if (doubling_primes[i] >= x) {
            return doubling_primes[i];
        }
    }
    // ran out of primes in the table!
    // return something sensible, at least make it odd
    return x | 1;
}

/******************************************************************************/
/* map                                                                        */

void mp_map_init(mp_map_t *map, mp_uint_t n) {
    if (n == 0) {
        map->alloc = 0;
        map->table = NULL;
    } else {
        map->alloc = n;
        map->table = m_new0(mp_map_elem_t, map->alloc);
    }
    map->used = 0;
    map->all_keys_are_qstrs = 1;
    map->is_fixed = 0;
    map->is_ordered = 0;
}

void mp_map_init_fixed_table(mp_map_t *map, mp_uint_t n, const mp_obj_t *table) {
    map->alloc = n;
    map->used = n;
    map->all_keys_are_qstrs = 1;
    map->is_fixed = 1;
    map->is_ordered = 1;
    map->table = (mp_map_elem_t*)table;
}

mp_map_t *mp_map_new(mp_uint_t n) {
    mp_map_t *map = m_new(mp_map_t, 1);
    mp_map_init(map, n);
    return map;
}

// Differentiate from mp_map_clear() - semantics is different
void mp_map_deinit(mp_map_t *map) {
    if (!map->is_fixed) {
        m_del(mp_map_elem_t, map->table, map->alloc);
    }
    map->used = map->alloc = 0;
}

void mp_map_free(mp_map_t *map) {
    mp_map_deinit(map);
    m_del_obj(mp_map_t, map);
}

void mp_map_clear(mp_map_t *map) {
    if (!map->is_fixed) {
        m_del(mp_map_elem_t, map->table, map->alloc);
    }
    map->alloc = 0;
    map->used = 0;
    map->all_keys_are_qstrs = 1;
    map->is_fixed = 0;
    map->table = NULL;
}

STATIC void mp_map_rehash(mp_map_t *map) {
    mp_uint_t old_alloc = map->alloc;
    mp_map_elem_t *old_table = map->table;
    map->alloc = get_doubling_prime_greater_or_equal_to(map->alloc + 1);
    map->used = 0;
    map->all_keys_are_qstrs = 1;
    map->table = m_new0(mp_map_elem_t, map->alloc);
    for (mp_uint_t i = 0; i < old_alloc; i++) {
        if (old_table[i].key != MP_OBJ_NULL && old_table[i].key != MP_OBJ_SENTINEL) {
            mp_map_lookup(map, old_table[i].key, MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)->value = old_table[i].value;
        }
    }
    m_del(mp_map_elem_t, old_table, old_alloc);
}

// MP_MAP_LOOKUP behaviour:
//  - returns NULL if not found, else the slot it was found in with key,value non-null
// MP_MAP_LOOKUP_ADD_IF_NOT_FOUND behaviour:
//  - returns slot, with key non-null and value=MP_OBJ_NULL if it was added
// MP_MAP_LOOKUP_REMOVE_IF_FOUND behaviour:
//  - returns NULL if not found, else the slot if was found in with key null and value non-null
mp_map_elem_t *mp_map_lookup(mp_map_t *map, mp_obj_t index, mp_map_lookup_kind_t lookup_kind) {

    if (map->is_fixed && lookup_kind != MP_MAP_LOOKUP) {
        // can't add/remove from a fixed array
        return NULL;
    }

    // Work out if we can compare just pointers
    bool compare_only_ptrs = map->all_keys_are_qstrs;
    if (compare_only_ptrs) {
        if (MP_OBJ_IS_QSTR(index)) {
            // Index is a qstr, so can just do ptr comparison.
        } else if (MP_OBJ_IS_TYPE(index, &mp_type_str)) {
            // Index is a non-interned string.
            // We can either intern the string, or force a full equality comparison.
            // We chose the latter, since interning costs time and potentially RAM,
            // and it won't necessarily benefit subsequent calls because these calls
            // most likely won't pass the newly-interned string.
            compare_only_ptrs = false;
        } else if (lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
            // If we are not adding, then we can return straight away a failed
            // lookup because we know that the index will never be found.
            return NULL;
        }
    }

    // if the map is an ordered array then we must do a brute force linear search
    if (map->is_ordered) {
        for (mp_map_elem_t *elem = &map->table[0], *top = &map->table[map->used]; elem < top; elem++) {
            if (elem->key == index || (!compare_only_ptrs && mp_obj_equal(elem->key, index))) {
                if (MP_UNLIKELY(lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND)) {
                    elem->key = MP_OBJ_SENTINEL;
                    // keep elem->value so that caller can access it if needed
                }
                return elem;
            }
        }
        if (MP_LIKELY(lookup_kind != MP_MAP_LOOKUP_ADD_IF_NOT_FOUND)) {
            return NULL;
        }
        // TODO shrink array down over any previously-freed slots
        if (map->used == map->alloc) {
            // TODO: Alloc policy
            map->alloc += 4;
            map->table = m_renew(mp_map_elem_t, map->table, map->used, map->alloc);
            mp_seq_clear(map->table, map->used, map->alloc, sizeof(*map->table));
        }
        mp_map_elem_t *elem = map->table + map->used++;
        elem->key = index;
        if (!MP_OBJ_IS_QSTR(index)) {
            map->all_keys_are_qstrs = 0;
        }
        return elem;
    }

    // map is a hash table (not an ordered array), so do a hash lookup

    if (map->alloc == 0) {
        if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
            mp_map_rehash(map);
        } else {
            return NULL;
        }
    }

    // get hash of index, with fast path for common case of qstr
    mp_uint_t hash;
    if (MP_OBJ_IS_QSTR(index)) {
        hash = qstr_hash(MP_OBJ_QSTR_VALUE(index));
    } else {
        hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
    }

    mp_uint_t pos = hash % map->alloc;
    mp_uint_t start_pos = pos;
    mp_map_elem_t *avail_slot = NULL;
    for (;;) {
        mp_map_elem_t *slot = &map->table[pos];
        if (slot->key == MP_OBJ_NULL) {
            // found NULL slot, so index is not in table
            if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
                map->used += 1;
                if (avail_slot == NULL) {
                    avail_slot = slot;
                }
                avail_slot->key = index;
                avail_slot->value = MP_OBJ_NULL;
                if (!MP_OBJ_IS_QSTR(index)) {
                    map->all_keys_are_qstrs = 0;
                }
                return avail_slot;
            } else {
                return NULL;
            }
        } else if (slot->key == MP_OBJ_SENTINEL) {
            // found deleted slot, remember for later
            if (avail_slot == NULL) {
                avail_slot = slot;
            }
        } else if (slot->key == index || (!compare_only_ptrs && mp_obj_equal(slot->key, index))) {
            // found index
            // Note: CPython does not replace the index; try x={True:'true'};x[1]='one';x
            if (lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
                // delete element in this slot
                map->used--;
                if (map->table[(pos + 1) % map->alloc].key == MP_OBJ_NULL) {
                    // optimisation if next slot is empty
                    slot->key = MP_OBJ_NULL;
                } else {
                    slot->key = MP_OBJ_SENTINEL;
                }
                // keep slot->value so that caller can access it if needed
            }
            return slot;
        }

        // not yet found, keep searching in this table
        pos = (pos + 1) % map->alloc;

        if (pos == start_pos) {
            // search got back to starting position, so index is not in table
            if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
                if (avail_slot != NULL) {
                    // there was an available slot, so use that
                    map->used++;
                    avail_slot->key = index;
                    avail_slot->value = MP_OBJ_NULL;
                    if (!MP_OBJ_IS_QSTR(index)) {
                        map->all_keys_are_qstrs = 0;
                    }
                    return avail_slot;
                } else {
                    // not enough room in table, rehash it
                    mp_map_rehash(map);
                    // restart the search for the new element
                    start_pos = pos = hash % map->alloc;
                }
            } else {
                return NULL;
            }
        }
    }
}

/******************************************************************************/
/* set                                                                        */

#if MICROPY_PY_BUILTINS_SET

void mp_set_init(mp_set_t *set, mp_uint_t n) {
    set->alloc = n;
    set->used = 0;
    set->table = m_new0(mp_obj_t, set->alloc);
}

STATIC void mp_set_rehash(mp_set_t *set) {
    mp_uint_t old_alloc = set->alloc;
    mp_obj_t *old_table = set->table;
    set->alloc = get_doubling_prime_greater_or_equal_to(set->alloc + 1);
    set->used = 0;
    set->table = m_new0(mp_obj_t, set->alloc);
    for (mp_uint_t i = 0; i < old_alloc; i++) {
        if (old_table[i] != MP_OBJ_NULL && old_table[i] != MP_OBJ_SENTINEL) {
            mp_set_lookup(set, old_table[i], MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
        }
    }
    m_del(mp_obj_t, old_table, old_alloc);
}

mp_obj_t mp_set_lookup(mp_set_t *set, mp_obj_t index, mp_map_lookup_kind_t lookup_kind) {
    // Note: lookup_kind can be MP_MAP_LOOKUP_ADD_IF_NOT_FOUND_OR_REMOVE_IF_FOUND which
    // is handled by using bitwise operations.

    if (set->alloc == 0) {
        if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
            mp_set_rehash(set);
        } else {
            return MP_OBJ_NULL;
        }
    }
    mp_uint_t hash = MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, index));
    mp_uint_t pos = hash % set->alloc;
    mp_uint_t start_pos = pos;
    mp_obj_t *avail_slot = NULL;
    for (;;) {
        mp_obj_t elem = set->table[pos];
        if (elem == MP_OBJ_NULL) {
            // found NULL slot, so index is not in table
            if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
                if (avail_slot == NULL) {
                    avail_slot = &set->table[pos];
                }
                set->used++;
                *avail_slot = index;
                return index;
            } else {
                return MP_OBJ_NULL;
            }
        } else if (elem == MP_OBJ_SENTINEL) {
            // found deleted slot, remember for later
            if (avail_slot == NULL) {
                avail_slot = &set->table[pos];
            }
        } else if (mp_obj_equal(elem, index)) {
            // found index
            if (lookup_kind & MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
                // delete element
                set->used--;
                if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
                    // optimisation if next slot is empty
                    set->table[pos] = MP_OBJ_NULL;
                } else {
                    set->table[pos] = MP_OBJ_SENTINEL;
                }
            }
            return elem;
        }

        // not yet found, keep searching in this table
        pos = (pos + 1) % set->alloc;

        if (pos == start_pos) {
            // search got back to starting position, so index is not in table
            if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
                if (avail_slot != NULL) {
                    // there was an available slot, so use that
                    set->used++;
                    *avail_slot = index;
                    return index;
                } else {
                    // not enough room in table, rehash it
                    mp_set_rehash(set);
                    // restart the search for the new element
                    start_pos = pos = hash % set->alloc;
                }
            } else {
                return MP_OBJ_NULL;
            }
        }
    }
}

mp_obj_t mp_set_remove_first(mp_set_t *set) {
    for (mp_uint_t pos = 0; pos < set->alloc; pos++) {
        if (MP_SET_SLOT_IS_FILLED(set, pos)) {
            mp_obj_t elem = set->table[pos];
            // delete element
            set->used--;
            if (set->table[(pos + 1) % set->alloc] == MP_OBJ_NULL) {
                // optimisation if next slot is empty
                set->table[pos] = MP_OBJ_NULL;
            } else {
                set->table[pos] = MP_OBJ_SENTINEL;
            }
            return elem;
        }
    }
    return MP_OBJ_NULL;
}

void mp_set_clear(mp_set_t *set) {
    m_del(mp_obj_t, set->table, set->alloc);
    set->alloc = 0;
    set->used = 0;
    set->table = NULL;
}

#endif // MICROPY_PY_BUILTINS_SET

#if defined(DEBUG_PRINT) && DEBUG_PRINT
void mp_map_dump(mp_map_t *map) {
    for (mp_uint_t i = 0; i < map->alloc; i++) {
        if (map->table[i].key != NULL) {
            mp_obj_print(map->table[i].key, PRINT_REPR);
        } else {
            printf("(nil)");
        }
        printf(": %p\n", map->table[i].value);
    }
    printf("---\n");
}
#endif
@


1.1
log
@Initial revision
@
text
@@


1.1.1.1
log
@Import micropython version 1.5.2 into othersrc.

Micropython is a python3 implementation that has been optimised for
micro-controllers and small embedded systems.  It also has a "unix"
port. It has an MIT license.

This is version 1.5.2 of micropython.

	MicroPython implements the entire Python 3.4 syntax (including
	exceptions, "with", "yield from", etc.).  The following core
	datatypes are provided:  str (including basic Unicode
	support), bytes, bytearray, tuple, list, dict, set, frozenset,
	array.array, collections.namedtuple, classes and instances. 
	Builtin modules include sys, time, and struct.  Note that only
	subset of Python 3.4 functionality implemented for the data
	types and modules.

This is the standard micropython source (version v1.5.2), which has been
adapted to use reachover infrastructure. At the present time, libffi
(from pkgsrc) is used. Alternative locations for libffi can be set
using the PKGSRC_PREFIX definition to make.

In the whole scheme of things, micropython is quite small:

	% size bin/micropython
	   text    data     bss     dec     hex filename
	 393495    1624    2208  397327   6100f bin/micropython
	%

and runs much as expected:

	% bin/micropython
	MicroPython v1.5.2 on 2016-01-13; linux version
	Use Ctrl-D to exit, Ctrl-E for paste mode
	>>> print("hello world")
	hello world
	>>> list(5 * x + y for x in range(10) for y in [4, 2, 1])
	[4, 2, 1, 9, 7, 6, 14, 12, 11, 19, 17, 16, 24, 22, 21, 29, 27, 26, 34, 32, 31, 39, 37, 36, 44, 42, 41, 49, 47, 46]
	>>>
	% python2.7
	Python 2.7.10 (default, Oct 17 2015, 17:55:29)
	[GCC 4.8.5] on netbsd7
	Type "help", "copyright", "credits" or "license" for more information.
	>>> print("hello world")
	hello world
	>>> list(5 * x + y for x in range(10) for y in [4, 2, 1])
	[4, 2, 1, 9, 7, 6, 14, 12, 11, 19, 17, 16, 24, 22, 21, 29, 27, 26, 34, 32, 31, 39, 37, 36, 44, 42, 41, 49, 47, 46]
	>>> ^D
	%

This (reachover) version runs all the tests which the gmake version does.

	% make t
	cd bin && make t
	cd /home/agc/local/micropython/bin/../dist/unix/../tests && env MICROPY_MICROPYTHON=/home/agc/local/micropython/bin/micropython ./run-tests
	pass  basics/0prelim.py
	pass  basics/andor.py
	pass  basics/array1.py
	pass  basics/array_add.py
	pass  basics/array_construct.py
	pass  basics/array_construct2.py
	...
	pass  unix/ffi_callback.py
	pass  unix/ffi_float.py
	pass  unix/ffi_float2.py
	474 tests performed (15812 individual testcases)
	474 tests passed
	5 tests skipped: cmd_showbc cmd_verbose machine1 machine_mem extra_coverage
	%

The sources are available from github:
	https://github.com/micropython/micropython

micropython release at:
	https://github.com/micropython/micropython/releases

Sources for 1.5.2 taken from:
	https://github.com/micropython/micropython/archive/v1.5.2.tar.gz

Alistair Crooks
agc@@netbsd.org
Wed Jan 13 17:15:30 PST 2016
@
text
@@