STATIC mp_obj_t btree_init_iter(size_t n_args, const mp_obj_t *args, byte type) {
    mp_obj_btree_t *self = MP_OBJ_TO_PTR(args[0]);
    self->next_flags = type;
    self->start_key = mp_const_none;
    self->end_key = mp_const_none;
    if (n_args > 1) {
        self->start_key = args[1];
        if (n_args > 2) {
            self->end_key = args[2];
            if (n_args > 3) {
                self->next_flags = type | MP_OBJ_SMALL_INT_VALUE(args[3]);
            }
        }
    }
    return args[0];
}

mp_obj_t mp_obj_tuple_unary_op(mp_uint_t op, mp_obj_t self_in) {
    mp_obj_tuple_t *self = MP_OBJ_TO_PTR(self_in);
    switch (op) {
        case MP_UNARY_OP_BOOL: return mp_obj_new_bool(self->len != 0);
        case MP_UNARY_OP_HASH: {
            // start hash with pointer to empty tuple, to make it fairly unique
            mp_int_t hash = (mp_int_t)mp_const_empty_tuple;
            for (size_t i = 0; i < self->len; i++) {
                hash += MP_OBJ_SMALL_INT_VALUE(mp_unary_op(MP_UNARY_OP_HASH, self->items[i]));
            }
            return MP_OBJ_NEW_SMALL_INT(hash);
        }
        case MP_UNARY_OP_LEN: return MP_OBJ_NEW_SMALL_INT(self->len);
        default: return MP_OBJ_NULL; // op not supported
    }
}

STATIC mp_obj_t mod_socket_getaddrinfo(uint n_args, const mp_obj_t *args) {
    // TODO: Implement all args
    assert(n_args == 2);
    assert(MP_OBJ_IS_STR(args[0]));

    const char *host = mp_obj_str_get_str(args[0]);
    const char *serv = NULL;
    // getaddrinfo accepts port in string notation, so however
    // it may seem stupid, we need to convert int to str
    if (MP_OBJ_IS_SMALL_INT(args[1])) {
        int port = (short)MP_OBJ_SMALL_INT_VALUE(args[1]);
        char buf[6];
        sprintf(buf, "%d", port);
        serv = buf;
    } else {
        serv = mp_obj_str_get_str(args[1]);
    }

    struct addrinfo hints;
    struct addrinfo *addr;
    memset(&hints, 0, sizeof(hints));
    int res = getaddrinfo(host, serv, NULL/*&hints*/, &addr);

    if (res != 0) {
        // CPython: socket.gaierror
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_OSError, "[addrinfo error %d]", res));
    }
    assert(addr);

    mp_obj_t list = mp_obj_new_list(0, NULL);
    for (; addr; addr = addr->ai_next) {
        mp_obj_tuple_t *t = mp_obj_new_tuple(5, NULL);
        t->items[0] = MP_OBJ_NEW_SMALL_INT((machine_int_t)addr->ai_family);
        t->items[1] = MP_OBJ_NEW_SMALL_INT((machine_int_t)addr->ai_socktype);
        t->items[2] = MP_OBJ_NEW_SMALL_INT((machine_int_t)addr->ai_protocol);
        // "canonname will be a string representing the canonical name of the host
        // if AI_CANONNAME is part of the flags argument; else canonname will be empty." ??
        if (addr->ai_canonname) {
            t->items[3] = MP_OBJ_NEW_QSTR(qstr_from_str(addr->ai_canonname));
        } else {
            t->items[3] = mp_const_none;
        }
        t->items[4] = mp_obj_new_bytearray(addr->ai_addrlen, addr->ai_addr);
        mp_obj_list_append(list, t);
    }
    return list;
}

// Unbuffered, inefficient implementation of readline() for raw I/O files.
STATIC mp_obj_t stream_unbuffered_readline(uint n_args, const mp_obj_t *args) {
    struct _mp_obj_base_t *o = (struct _mp_obj_base_t *)args[0];
    if (o->type->stream_p == NULL || o->type->stream_p->read == NULL) {
        // CPython: io.UnsupportedOperation, OSError subclass
        nlr_raise(mp_obj_new_exception_msg(&mp_type_OSError, "Operation not supported"));
    }

    mp_int_t max_size = -1;
    if (n_args > 1) {
        max_size = MP_OBJ_SMALL_INT_VALUE(args[1]);
    }

    vstr_t *vstr;
    if (max_size != -1) {
        vstr = vstr_new_size(max_size);
    } else {
        vstr = vstr_new();
    }

    int error;
    while (max_size == -1 || max_size-- != 0) {
        char *p = vstr_add_len(vstr, 1);
        if (p == NULL) {
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_MemoryError, "out of memory"));
        }

        mp_int_t out_sz = o->type->stream_p->read(o, p, 1, &error);
        if (out_sz == -1) {
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_OSError, "[Errno %d]", error));
        }
        if (out_sz == 0) {
            // Back out previously added byte
            // TODO: This is a bit hacky, does it supported by vstr API contract?
            // Consider, what's better - read a char and get OutOfMemory (so read
            // char is lost), or allocate first as we do.
            vstr_add_len(vstr, -1);
            break;
        }
        if (*p == '\n') {
            break;
        }
    }
    // TODO need a string creation API that doesn't copy the given data
    mp_obj_t ret = mp_obj_new_str_of_type(STREAM_CONTENT_TYPE(o->type->stream_p), (byte*)vstr->buf, vstr->len);
    vstr_free(vstr);
    return ret;
}

// convert a Micro Python object to a sensible value for inline asm
STATIC machine_uint_t convert_obj_for_inline_asm(mp_obj_t obj) {
    // TODO for byte_array, pass pointer to the array
    if (MP_OBJ_IS_SMALL_INT(obj)) {
        return MP_OBJ_SMALL_INT_VALUE(obj);
    } else if (obj == mp_const_none) {
        return 0;
    } else if (obj == mp_const_false) {
        return 0;
    } else if (obj == mp_const_true) {
        return 1;
    } else if (MP_OBJ_IS_STR(obj)) {
        // pointer to the string (it's probably constant though!)
        uint l;
        return (machine_uint_t)mp_obj_str_get_data(obj, &l);
    } else {
        mp_obj_type_t *type = mp_obj_get_type(obj);
        if (0) {
#if MICROPY_PY_BUILTINS_FLOAT
        } else if (type == &mp_type_float) {
            // convert float to int (could also pass in float registers)
            return (machine_int_t)mp_obj_float_get(obj);
#endif
        } else if (type == &mp_type_tuple) {
            // pointer to start of tuple (could pass length, but then could use len(x) for that)
            uint len;
            mp_obj_t *items;
            mp_obj_tuple_get(obj, &len, &items);
            return (machine_uint_t)items;
        } else if (type == &mp_type_list) {
            // pointer to start of list (could pass length, but then could use len(x) for that)
            uint len;
            mp_obj_t *items;
            mp_obj_list_get(obj, &len, &items);
            return (machine_uint_t)items;
        } else {
            mp_buffer_info_t bufinfo;
            if (mp_get_buffer(obj, &bufinfo, MP_BUFFER_WRITE)) {
                // supports the buffer protocol, return a pointer to the data
                return (machine_uint_t)bufinfo.buf;
            } else {
                // just pass along a pointer to the object
                return (machine_uint_t)obj;
            }
        }
    }
}

STATIC mp_obj_t bytearray_make_new(mp_obj_t type_in, mp_uint_t n_args, mp_uint_t n_kw, const mp_obj_t *args) {
    mp_arg_check_num(n_args, n_kw, 0, 1, false);

    if (n_args == 0) {
        // no args: construct an empty bytearray
        return array_new(BYTEARRAY_TYPECODE, 0);
    } else if (MP_OBJ_IS_SMALL_INT(args[0])) {
        // 1 arg, an integer: construct a blank bytearray of that length
        uint len = MP_OBJ_SMALL_INT_VALUE(args[0]);
        mp_obj_array_t *o = array_new(BYTEARRAY_TYPECODE, len);
        memset(o->items, 0, len);
        return o;
    } else {
        // 1 arg, an iterator: construct the bytearray from that
        return array_construct(BYTEARRAY_TYPECODE, args[0]);
    }
}

// this function implements the '==' operator (and so the inverse of '!=')
// from the python language reference:
// "The objects need not have the same type. If both are numbers, they are converted
// to a common type. Otherwise, the == and != operators always consider objects of
// different types to be unequal."
// note also that False==0 and True==1 are true expressions
bool mp_obj_equal(mp_obj_t o1, mp_obj_t o2) {
    if (o1 == o2) {
        return true;
    } else if (o1 == mp_const_none || o2 == mp_const_none) {
        return false;
    } else if (MP_OBJ_IS_SMALL_INT(o1) || MP_OBJ_IS_SMALL_INT(o2)) {
        if (MP_OBJ_IS_SMALL_INT(o1) && MP_OBJ_IS_SMALL_INT(o2)) {
            return false;
        } else {
            if (MP_OBJ_IS_SMALL_INT(o2)) {
                mp_obj_t temp = o1; o1 = o2; o2 = temp;
            }
            // o1 is the SMALL_INT, o2 is not
            mp_small_int_t val = MP_OBJ_SMALL_INT_VALUE(o1);
            if (o2 == mp_const_false) {
                return val == 0;
            } else if (o2 == mp_const_true) {
                return val == 1;
            } else if (MP_OBJ_IS_TYPE(o2, &mp_type_int)) {
                // If o2 is long int, dispatch to its virtual methods
                mp_obj_base_t *o = o2;
                if (o->type->binary_op != NULL) {
                    mp_obj_t r = o->type->binary_op(MP_BINARY_OP_EQUAL, o2, o1);
                    return r == mp_const_true ? true : false;
                }
            }
            return false;
        }
    } else if (MP_OBJ_IS_STR(o1) && MP_OBJ_IS_STR(o2)) {
        return mp_obj_str_equal(o1, o2);
    } else {
        mp_obj_base_t *o = o1;
        if (o->type->binary_op != NULL) {
            mp_obj_t r = o->type->binary_op(MP_BINARY_OP_EQUAL, o1, o2);
            if (r != MP_OBJ_NULL) {
                return r == mp_const_true ? true : false;
            }
        }

        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_NotImplementedError,
            "Equality for '%s' and '%s' types not yet implemented", mp_obj_get_type_str(o1), mp_obj_get_type_str(o2)));
        return false;
    }
}

STATIC mp_obj_t array_construct(char typecode, mp_obj_t initializer) {
    // bytearrays can be raw-initialised from anything with the buffer protocol
    // other arrays can only be raw-initialised from bytes and bytearray objects
    mp_buffer_info_t bufinfo;
    if (((MICROPY_PY_BUILTINS_BYTEARRAY
            && typecode == BYTEARRAY_TYPECODE)
        || (MICROPY_PY_ARRAY
            && (MP_OBJ_IS_TYPE(initializer, &mp_type_bytes)
                || (MICROPY_PY_BUILTINS_BYTEARRAY && MP_OBJ_IS_TYPE(initializer, &mp_type_bytearray)))))
        && mp_get_buffer(initializer, &bufinfo, MP_BUFFER_READ)) {
        // construct array from raw bytes
        // we round-down the len to make it a multiple of sz (CPython raises error)
        size_t sz = mp_binary_get_size('@', typecode, NULL);
        mp_uint_t len = bufinfo.len / sz;
        mp_obj_array_t *o = array_new(typecode, len);
        memcpy(o->items, bufinfo.buf, len * sz);
        return o;
    }

    mp_uint_t len;
    // Try to create array of exact len if initializer len is known
    mp_obj_t len_in = mp_obj_len_maybe(initializer);
    if (len_in == MP_OBJ_NULL) {
        len = 0;
    } else {
        len = MP_OBJ_SMALL_INT_VALUE(len_in);
    }

    mp_obj_array_t *array = array_new(typecode, len);

    mp_obj_t iterable = mp_getiter(initializer);
    mp_obj_t item;
    mp_uint_t i = 0;
    while ((item = mp_iternext(iterable)) != MP_OBJ_STOP_ITERATION) {
        if (len == 0) {
            array_append(array, item);
        } else {
            mp_binary_set_val_array(typecode, array->items, i++, item);
        }
    }

    return array;
}

STATIC mp_obj_t socket_sendto(size_t n_args, const mp_obj_t *args) {
    mp_obj_socket_t *self = MP_OBJ_TO_PTR(args[0]);
    int flags = 0;

    mp_obj_t dst_addr = args[2];
    if (n_args > 3) {
        flags = MP_OBJ_SMALL_INT_VALUE(args[2]);
        dst_addr = args[3];
    }

    mp_buffer_info_t bufinfo, addr_bi;
    mp_get_buffer_raise(args[1], &bufinfo, MP_BUFFER_READ);
    mp_get_buffer_raise(dst_addr, &addr_bi, MP_BUFFER_READ);
    int out_sz = sendto(self->fd, bufinfo.buf, bufinfo.len, flags,
                        (struct sockaddr *)addr_bi.buf, addr_bi.len);
    RAISE_ERRNO(out_sz, errno);

    return MP_OBJ_NEW_SMALL_INT(out_sz);
}

int rt_is_true(mp_obj_t arg) {
    DEBUG_OP_printf("is true %p\n", arg);
    if (MP_OBJ_IS_SMALL_INT(arg)) {
        if (MP_OBJ_SMALL_INT_VALUE(arg) == 0) {
            return 0;
        } else {
            return 1;
        }
    } else if (arg == mp_const_none) {
        return 0;
    } else if (arg == mp_const_false) {
        return 0;
    } else if (arg == mp_const_true) {
        return 1;
    } else {
        assert(0);
        return 0;
    }
}

STATIC mp_obj_t fdfile_make_new(mp_obj_t type_in, uint n_args, uint n_kw, const mp_obj_t *args) {
    mp_obj_fdfile_t *o = m_new_obj(mp_obj_fdfile_t);
    o->base.type = type_in;

    if (MP_OBJ_IS_SMALL_INT(args[0])) {
        o->fd = MP_OBJ_SMALL_INT_VALUE(args[0]);
        return o;
    }

    const char *fname = mp_obj_str_get_str(args[0]);
    const char *mode_s;
    if (n_args > 1) {
        mode_s = mp_obj_str_get_str(args[1]);
    } else {
        mode_s = "r";
    }

    int mode = 0;
    while (*mode_s) {
        switch (*mode_s++) {
            // Note: these assume O_RDWR = O_RDONLY | O_WRONLY
            case 'r':
                mode |= O_RDONLY;
                break;
            case 'w':
                mode |= O_WRONLY | O_CREAT | O_TRUNC;
                break;
            case 'a':
                mode |= O_APPEND;
                break;
            case '+':
                mode |= O_RDWR;
                break;
        }
    }

    int fd = open(fname, mode, 0644);
    if (fd == -1) {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_OSError, "[Errno %d]", errno));
    }
    return fdfile_new(fd);
}

STATIC mp_obj_t it_iternext(mp_obj_t self_in) {
    mp_obj_getitem_iter_t *self = self_in;
    nlr_buf_t nlr;
    if (nlr_push(&nlr) == 0) {
        // try to get next item
        mp_obj_t value = rt_call_method_n_kw(1, 0, self->args);
        self->args[2] = MP_OBJ_NEW_SMALL_INT(MP_OBJ_SMALL_INT_VALUE(self->args[2]) + 1);
        nlr_pop();
        return value;
    } else {
        // an exception was raised
        if (mp_obj_get_type(nlr.ret_val) == &mp_type_StopIteration) {
            // return mp_const_stop_iteration instead of raising StopIteration
            return mp_const_stop_iteration;
        } else {
            // re-raise exception
            nlr_jump(nlr.ret_val);
        }
    }
}

mp_float_t mp_obj_get_float(mp_obj_t arg) {
    if (arg == mp_const_false) {
        return 0;
    } else if (arg == mp_const_true) {
        return 1;
    } else if (MP_OBJ_IS_SMALL_INT(arg)) {
        return MP_OBJ_SMALL_INT_VALUE(arg);
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_int)) {
        return mp_obj_int_as_float(arg);
    } else if (mp_obj_is_float(arg)) {
        return mp_obj_float_get(arg);
    } else {
        if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
            nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError,
                "can't convert to float"));
        } else {
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
                "can't convert %s to float", mp_obj_get_type_str(arg)));
        }
    }
}

STATIC mp_obj_t socket_setsockopt(uint n_args, const mp_obj_t *args) {
    mp_obj_socket_t *self = args[0];
    int level = MP_OBJ_SMALL_INT_VALUE(args[1]);
    int option = mp_obj_get_int(args[2]);

    const void *optval;
    socklen_t optlen;
    if (MP_OBJ_IS_INT(args[3])) {
        int val = mp_obj_int_get(args[3]);
        optval = &val;
        optlen = sizeof(val);
    } else {
        mp_buffer_info_t bufinfo;
        mp_get_buffer_raise(args[3], &bufinfo, MP_BUFFER_READ);
        optval = bufinfo.buf;
        optlen = bufinfo.len;
    }
    int r = setsockopt(self->fd, level, option, optval, optlen);
    RAISE_ERRNO(r, errno);
    return mp_const_none;
}

mp_int_t mp_obj_get_int(mp_const_obj_t arg) {
    // This function essentially performs implicit type conversion to int
    // Note that Python does NOT provide implicit type conversion from
    // float to int in the core expression language, try some_list[1.0].
    if (arg == mp_const_false) {
        return 0;
    } else if (arg == mp_const_true) {
        return 1;
    } else if (MP_OBJ_IS_SMALL_INT(arg)) {
        return MP_OBJ_SMALL_INT_VALUE(arg);
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_int)) {
        return mp_obj_int_get_checked(arg);
    } else {
        if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
            mp_raise_TypeError("can't convert to int");
        } else {
            nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
                "can't convert %s to int", mp_obj_get_type_str(arg)));
        }
    }
}

mp_int_t mp_obj_hash(mp_obj_t o_in) {
    if (o_in == mp_const_false) {
        return 0; // needs to hash to same as the integer 0, since False==0
    } else if (o_in == mp_const_true) {
        return 1; // needs to hash to same as the integer 1, since True==1
    } else if (MP_OBJ_IS_SMALL_INT(o_in)) {
        return MP_OBJ_SMALL_INT_VALUE(o_in);
    } else if (MP_OBJ_IS_TYPE(o_in, &mp_type_int)) {
        return mp_obj_int_hash(o_in);
    } else if (MP_OBJ_IS_STR(o_in) || MP_OBJ_IS_TYPE(o_in, &mp_type_bytes)) {
        return mp_obj_str_get_hash(o_in);
    } else if (MP_OBJ_IS_TYPE(o_in, &mp_type_NoneType)) {
        return (mp_int_t)o_in;
    } else if (MP_OBJ_IS_FUN(o_in)) {
        return (mp_int_t)o_in;
    } else if (MP_OBJ_IS_TYPE(o_in, &mp_type_tuple)) {
        return mp_obj_tuple_hash(o_in);
    } else if (MP_OBJ_IS_TYPE(o_in, &mp_type_type)) {
        return (mp_int_t)o_in;
    } else if (MP_OBJ_IS_OBJ(o_in)) {
        // if a valid __hash__ method exists, use it
        mp_obj_t hash_method[2];
        mp_load_method_maybe(o_in, MP_QSTR___hash__, hash_method);
        if (hash_method[0] != MP_OBJ_NULL) {
            mp_obj_t hash_val = mp_call_method_n_kw(0, 0, hash_method);
            if (MP_OBJ_IS_INT(hash_val)) {
                return mp_obj_int_get_truncated(hash_val);
            }
        }
    }

    // TODO hash class and instances - in CPython by default user created classes' __hash__ resolves to their id

    if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
        nlr_raise(mp_obj_new_exception_msg(&mp_type_TypeError, "unhashable type"));
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError,
            "unhashable type: '%s'", mp_obj_get_type_str(o_in)));
    }
}

bool mp_obj_get_float_maybe(mp_obj_t arg, mp_float_t *value) {
    mp_float_t val;

    if (arg == mp_const_false) {
        val = 0;
    } else if (arg == mp_const_true) {
        val = 1;
    } else if (MP_OBJ_IS_SMALL_INT(arg)) {
        val = MP_OBJ_SMALL_INT_VALUE(arg);
    #if MICROPY_LONGINT_IMPL != MICROPY_LONGINT_IMPL_NONE
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_int)) {
        val = mp_obj_int_as_float_impl(arg);
    #endif
    } else if (mp_obj_is_float(arg)) {
        val = mp_obj_float_get(arg);
    } else {
        return false;
    }

    *value = val;
    return true;
}

void mp_obj_get_complex(mp_obj_t arg, mp_float_t *real, mp_float_t *imag) {
    if (arg == mp_const_false) {
        *real = 0;
        *imag = 0;
    } else if (arg == mp_const_true) {
        *real = 1;
        *imag = 0;
    } else if (MP_OBJ_IS_SMALL_INT(arg)) {
        *real = MP_OBJ_SMALL_INT_VALUE(arg);
        *imag = 0;
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_int)) {
        *real = mp_obj_int_as_float(arg);
        *imag = 0;
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_float)) {
        *real = mp_obj_float_get(arg);
        *imag = 0;
    } else if (MP_OBJ_IS_TYPE(arg, &mp_type_complex)) {
        mp_obj_complex_get(arg, real, imag);
    } else {
        nlr_raise(mp_obj_new_exception_msg_varg(&mp_type_TypeError, "can't convert %s to complex", mp_obj_get_type_str(arg)));
    }
}

STATIC mp_obj_t btree_seq(size_t n_args, const mp_obj_t *args) {
    mp_obj_btree_t *self = MP_OBJ_TO_PTR(args[0]);
    int flags = MP_OBJ_SMALL_INT_VALUE(args[1]);
    DBT key, val;
    if (n_args > 2) {
        // Different ports may have different type sizes
        mp_uint_t v;
        key.data = (void*)mp_obj_str_get_data(args[2], &v);
        key.size = v;
    }

    int res = __bt_seq(self->db, &key, &val, flags);
    if (res == RET_SPECIAL) {
        return mp_const_none;
    }

    mp_obj_t pair_o = mp_obj_new_tuple(2, NULL);
    mp_obj_tuple_t *pair = MP_OBJ_TO_PTR(pair_o);
    pair->items[0] = mp_obj_new_bytes(key.data, key.size);
    pair->items[1] = mp_obj_new_bytes(val.data, val.size);
    return pair_o;
}

static mp_obj_t str_split(uint n_args, const mp_obj_t *args) {
    int splits = -1;
    mp_obj_t sep = mp_const_none;
    if (n_args > 1) {
        sep = args[1];
        if (n_args > 2) {
            splits = MP_OBJ_SMALL_INT_VALUE(args[2]);
        }
    }
    assert(sep == mp_const_none);
    (void)sep; // unused; to hush compiler warning
    mp_obj_t res = mp_obj_new_list(0, NULL);
    GET_STR_DATA_LEN(args[0], s, len);
    const byte *top = s + len;
    const byte *start;

    // Initial whitespace is not counted as split, so we pre-do it
    while (s < top && is_ws(*s)) s++;
    while (s < top && splits != 0) {
        start = s;
        while (s < top && !is_ws(*s)) s++;
        rt_list_append(res, mp_obj_new_str(start, s - start, false));
        if (s >= top) {
            break;
        }
        while (s < top && is_ws(*s)) s++;
        if (splits > 0) {
            splits--;
        }
    }

    if (s < top) {
        rt_list_append(res, mp_obj_new_str(s, top - s, false));
    }

    return res;
}