sequence.c 7.68 KB
Newer Older
1
2
3
4
5
6
/*
 * This file is part of the Micro Python project, http://micropython.org/
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2013, 2014 Damien P. George
7
 * Copyright (c) 2014 Paul Sokolovsky
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 *
 * 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.
 */

28
#include <assert.h>
xbe's avatar
xbe committed
29
#include <stdbool.h>
30
31
#include <string.h>

32
#include "mpconfig.h"
33
34
#include "nlr.h"
#include "misc.h"
35
#include "qstr.h"
36
37
38
39
40
41
#include "obj.h"
#include "runtime0.h"
#include "runtime.h"

// Helpers for sequence types

42
43
#define SWAP(type, var1, var2) { type t = var2; var2 = var1; var1 = t; }

44
45
// Implements backend of sequence * integer operation. Assumes elements are
// memory-adjacent in sequence.
46
void mp_seq_multiply(const void *items, mp_uint_t item_sz, mp_uint_t len, mp_uint_t times, void *dest) {
47
    for (mp_uint_t i = 0; i < times; i++) {
48
49
50
51
52
        uint copy_sz = item_sz * len;
        memcpy(dest, items, copy_sz);
        dest = (char*)dest + copy_sz;
    }
}
53

54
55
#if MICROPY_PY_BUILTINS_SLICE

56
bool mp_seq_get_fast_slice_indexes(mp_uint_t len, mp_obj_t slice, mp_bound_slice_t *indexes) {
57
    mp_obj_t ostart, ostop, ostep;
58
    mp_int_t start, stop;
59
    mp_obj_slice_get(slice, &ostart, &ostop, &ostep);
60

61
62
63
64
65
66
67
68
69
70
71
    if (ostart == mp_const_none) {
        start = 0;
    } else {
        start = MP_OBJ_SMALL_INT_VALUE(ostart);
    }
    if (ostop == mp_const_none) {
        stop = len;
    } else {
        stop = MP_OBJ_SMALL_INT_VALUE(ostop);
    }

72
73
74
75
76
77
78
79
80
    // Unlike subscription, out-of-bounds slice indexes are never error
    if (start < 0) {
        start = len + start;
        if (start < 0) {
            start = 0;
        }
    } else if (start > len) {
        start = len;
    }
81
    if (stop < 0) {
82
83
84
85
        stop = len + stop;
    } else if (stop > len) {
        stop = len;
    }
86
87
88
89
90
91

    // CPython returns empty sequence in such case, or point for assignment is at start
    if (start > stop) {
        stop = start;
    }

92
93
94
95
96
97
98
99
    indexes->start = start;
    indexes->stop = stop;

    if (ostep != mp_const_none && ostep != MP_OBJ_NEW_SMALL_INT(1)) {
        indexes->step = MP_OBJ_SMALL_INT_VALUE(ostep);
        return false;
    }
    indexes->step = 1;
100
101
    return true;
}
102

103
104
#endif

105
mp_obj_t mp_seq_extract_slice(mp_uint_t len, const mp_obj_t *seq, mp_bound_slice_t *indexes) {
106
107
    mp_int_t start = indexes->start, stop = indexes->stop;
    mp_int_t step = indexes->step;
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

    mp_obj_t res = mp_obj_new_list(0, NULL);

    if (step < 0) {
        stop--;
        while (start <= stop) {
            mp_obj_list_append(res, seq[stop]);
            stop += step;
        }
    } else {
        while (start < stop) {
            mp_obj_list_append(res, seq[start]);
            start += step;
        }
    }
    return res;
}

126
// Special-case comparison function for sequences of bytes
Damien George's avatar
Damien George committed
127
// Don't pass MP_BINARY_OP_NOT_EQUAL here
128
bool mp_seq_cmp_bytes(mp_uint_t op, const byte *data1, mp_uint_t len1, const byte *data2, mp_uint_t len2) {
129
130
131
132
    if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
        return false;
    }

133
    // Let's deal only with > & >=
Damien George's avatar
Damien George committed
134
    if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
135
136
        SWAP(const byte*, data1, data2);
        SWAP(uint, len1, len2);
Damien George's avatar
Damien George committed
137
138
        if (op == MP_BINARY_OP_LESS) {
            op = MP_BINARY_OP_MORE;
139
        } else {
Damien George's avatar
Damien George committed
140
            op = MP_BINARY_OP_MORE_EQUAL;
141
142
143
144
        }
    }
    uint min_len = len1 < len2 ? len1 : len2;
    int res = memcmp(data1, data2, min_len);
145
146
147
148
    if (op == MP_BINARY_OP_EQUAL) {
        // If we are checking for equality, here're the answer
        return res == 0;
    }
149
150
151
152
153
154
155
156
157
158
159
160
161
162
    if (res < 0) {
        return false;
    }
    if (res > 0) {
        return true;
    }

    // If we had tie in the last element...
    // ... and we have lists of different lengths...
    if (len1 != len2) {
        if (len1 < len2) {
            // ... then longer list length wins (we deal only with >)
            return false;
        }
Damien George's avatar
Damien George committed
163
    } else if (op == MP_BINARY_OP_MORE) {
164
165
166
167
168
        // Otherwise, if we have strict relation, equality means failure
        return false;
    }
    return true;
}
169
170

// Special-case comparison function for sequences of mp_obj_t
Damien George's avatar
Damien George committed
171
// Don't pass MP_BINARY_OP_NOT_EQUAL here
172
bool mp_seq_cmp_objs(mp_uint_t op, const mp_obj_t *items1, mp_uint_t len1, const mp_obj_t *items2, mp_uint_t len2) {
Damien George's avatar
Damien George committed
173
    if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
174
175
176
177
        return false;
    }

    // Let's deal only with > & >=
Damien George's avatar
Damien George committed
178
    if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
179
180
        SWAP(const mp_obj_t *, items1, items2);
        SWAP(uint, len1, len2);
Damien George's avatar
Damien George committed
181
182
        if (op == MP_BINARY_OP_LESS) {
            op = MP_BINARY_OP_MORE;
183
        } else {
Damien George's avatar
Damien George committed
184
            op = MP_BINARY_OP_MORE_EQUAL;
185
186
187
        }
    }

188
189
    mp_uint_t len = len1 < len2 ? len1 : len2;
    for (mp_uint_t i = 0; i < len; i++) {
190
        // If current elements equal, can't decide anything - go on
191
        if (mp_obj_equal(items1[i], items2[i])) {
192
            continue;
193
        }
194
195
196
197

        // Othewise, if they are not equal, we can have final decision based on them
        if (op == MP_BINARY_OP_EQUAL) {
            // In particular, if we are checking for equality, here're the answer
198
199
            return false;
        }
200
201
202

        // Otherwise, application of relation op gives the answer
        return (mp_binary_op(op, items1[i], items2[i]) == mp_const_true);
203
204
205
    }

    // If we had tie in the last element...
206
207
208
209
    // ... and we have lists of different lengths...
    if (len1 != len2) {
        if (len1 < len2) {
            // ... then longer list length wins (we deal only with >)
210
211
            return false;
        }
212
213
214
    } else if (op == MP_BINARY_OP_MORE) {
        // Otherwise, if we have strict relation, sequence equality means failure
        return false;
215
216
217
218
    }

    return true;
}
219
220

// Special-case of index() which searches for mp_obj_t
221
mp_obj_t mp_seq_index_obj(const mp_obj_t *items, mp_uint_t len, mp_uint_t n_args, const mp_obj_t *args) {
222
223
224
225
226
227
    mp_obj_type_t *type = mp_obj_get_type(args[0]);
    mp_obj_t *value = args[1];
    uint start = 0;
    uint stop = len;

    if (n_args >= 3) {
228
        start = mp_get_index(type, len, args[2], true);
229
        if (n_args >= 4) {
230
            stop = mp_get_index(type, len, args[3], true);
231
232
233
        }
    }

234
    for (mp_uint_t i = start; i < stop; i++) {
Paul Sokolovsky's avatar
Paul Sokolovsky committed
235
236
237
238
        if (mp_obj_equal(items[i], value)) {
            // Common sense says this cannot overflow small int
            return MP_OBJ_NEW_SMALL_INT(i);
        }
239
240
    }

241
    nlr_raise(mp_obj_new_exception_msg(&mp_type_ValueError, "object not in sequence"));
242
}
243

244
mp_obj_t mp_seq_count_obj(const mp_obj_t *items, mp_uint_t len, mp_obj_t value) {
245
    mp_uint_t count = 0;
246
247
248
249
250
251
252
253
254
    for (uint i = 0; i < len; i++) {
         if (mp_obj_equal(items[i], value)) {
              count++;
         }
    }

    // Common sense says this cannot overflow small int
    return MP_OBJ_NEW_SMALL_INT(count);
}