Branch data Line data Source code
1 : : /*
2 : : * This file is part of the MicroPython project, http://micropython.org/
3 : : *
4 : : * The MIT License (MIT)
5 : : *
6 : : * Copyright (c) 2013, 2014 Damien P. George
7 : : * Copyright (c) 2014 Paul Sokolovsky
8 : : *
9 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
10 : : * of this software and associated documentation files (the "Software"), to deal
11 : : * in the Software without restriction, including without limitation the rights
12 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 : : * copies of the Software, and to permit persons to whom the Software is
14 : : * furnished to do so, subject to the following conditions:
15 : : *
16 : : * The above copyright notice and this permission notice shall be included in
17 : : * all copies or substantial portions of the Software.
18 : : *
19 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 : : * THE SOFTWARE.
26 : : */
27 : :
28 : : #include <string.h>
29 : :
30 : : #include "py/runtime.h"
31 : :
32 : : // Helpers for sequence types
33 : :
34 : : #define SWAP(type, var1, var2) { type t = var2; var2 = var1; var1 = t; }
35 : :
36 : : // Implements backend of sequence * integer operation. Assumes elements are
37 : : // memory-adjacent in sequence.
38 : 696 : void mp_seq_multiply(const void *items, size_t item_sz, size_t len, size_t times, void *dest) {
39 [ + + ]: 53107 : for (size_t i = 0; i < times; i++) {
40 : 52411 : size_t copy_sz = item_sz * len;
41 : 52411 : memcpy(dest, items, copy_sz);
42 : 52411 : dest = (char *)dest + copy_sz;
43 : : }
44 : 696 : }
45 : :
46 : : #if MICROPY_PY_BUILTINS_SLICE
47 : :
48 : 8167 : bool mp_seq_get_fast_slice_indexes(mp_uint_t len, mp_obj_t slice, mp_bound_slice_t *indexes) {
49 : 8167 : mp_obj_slice_indices(slice, len, indexes);
50 : :
51 : : // If the index is negative then stop points to the last item, not after it
52 [ + + ]: 8163 : if (indexes->step < 0) {
53 : 112 : indexes->stop++;
54 : : }
55 : :
56 : : // CPython returns empty sequence in such case, or point for assignment is at start
57 [ + + + + ]: 8163 : if (indexes->step > 0 && indexes->start > indexes->stop) {
58 : 10 : indexes->stop = indexes->start;
59 [ + + + + ]: 8153 : } else if (indexes->step < 0 && indexes->start < indexes->stop) {
60 : 36 : indexes->stop = indexes->start + 1;
61 : : }
62 : :
63 : 8163 : return indexes->step == 1;
64 : : }
65 : :
66 : : #endif
67 : :
68 : 132 : mp_obj_t mp_seq_extract_slice(size_t len, const mp_obj_t *seq, mp_bound_slice_t *indexes) {
69 : 132 : (void)len; // TODO can we remove len from the arg list?
70 : :
71 : 132 : mp_int_t start = indexes->start, stop = indexes->stop;
72 : 132 : mp_int_t step = indexes->step;
73 : :
74 : 132 : mp_obj_t res = mp_obj_new_list(0, NULL);
75 : :
76 [ + + ]: 132 : if (step < 0) {
77 [ + + ]: 380 : while (start >= stop) {
78 : 276 : mp_obj_list_append(res, seq[start]);
79 : 276 : start += step;
80 : : }
81 : : } else {
82 [ + + ]: 128 : while (start < stop) {
83 : 100 : mp_obj_list_append(res, seq[start]);
84 : 100 : start += step;
85 : : }
86 : : }
87 : 132 : return res;
88 : : }
89 : :
90 : : // Special-case comparison function for sequences of bytes
91 : : // Don't pass MP_BINARY_OP_NOT_EQUAL here
92 : 29374 : bool mp_seq_cmp_bytes(mp_uint_t op, const byte *data1, size_t len1, const byte *data2, size_t len2) {
93 [ + + ]: 29374 : if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
94 : : return false;
95 : : }
96 : :
97 : : // Let's deal only with > & >=
98 [ + + ]: 9022 : if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
99 : 1638 : SWAP(const byte *, data1, data2);
100 : 1638 : SWAP(size_t, len1, len2);
101 [ + + ]: 1638 : if (op == MP_BINARY_OP_LESS) {
102 : : op = MP_BINARY_OP_MORE;
103 : : } else {
104 : 144 : op = MP_BINARY_OP_MORE_EQUAL;
105 : : }
106 : : }
107 : 9022 : size_t min_len = len1 < len2 ? len1 : len2;
108 : 9022 : int res = memcmp(data1, data2, min_len);
109 [ + + ]: 9022 : if (op == MP_BINARY_OP_EQUAL) {
110 : : // If we are checking for equality, here's the answer
111 : 6926 : return res == 0;
112 : : }
113 [ + + ]: 2096 : if (res < 0) {
114 : : return false;
115 : : }
116 [ + + ]: 1596 : if (res > 0) {
117 : : return true;
118 : : }
119 : :
120 : : // If we had tie in the last element...
121 : : // ... and we have lists of different lengths...
122 [ + + ]: 364 : if (len1 != len2) {
123 [ + + ]: 220 : if (len1 < len2) {
124 : : // ... then longer list length wins (we deal only with >)
125 : 102 : return false;
126 : : }
127 [ + + ]: 144 : } else if (op == MP_BINARY_OP_MORE) {
128 : : // Otherwise, if we have strict relation, equality means failure
129 : 80 : return false;
130 : : }
131 : : return true;
132 : : }
133 : :
134 : : // Special-case comparison function for sequences of mp_obj_t
135 : : // Don't pass MP_BINARY_OP_NOT_EQUAL here
136 : 850 : bool mp_seq_cmp_objs(mp_uint_t op, const mp_obj_t *items1, size_t len1, const mp_obj_t *items2, size_t len2) {
137 [ + + ]: 850 : if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
138 : : return false;
139 : : }
140 : :
141 : : // Let's deal only with > & >=
142 [ + + ]: 826 : if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
143 : 338 : SWAP(const mp_obj_t *, items1, items2);
144 : 338 : SWAP(size_t, len1, len2);
145 [ + + ]: 338 : if (op == MP_BINARY_OP_LESS) {
146 : : op = MP_BINARY_OP_MORE;
147 : : } else {
148 : 76 : op = MP_BINARY_OP_MORE_EQUAL;
149 : : }
150 : : }
151 : :
152 : 826 : size_t len = len1 < len2 ? len1 : len2;
153 [ + + ]: 4130 : for (size_t i = 0; i < len; i++) {
154 : : // If current elements equal, can't decide anything - go on
155 [ + + ]: 3590 : if (mp_obj_equal(items1[i], items2[i])) {
156 : 3304 : continue;
157 : : }
158 : :
159 : : // Otherwise, if they are not equal, we can have final decision based on them
160 [ + + ]: 286 : if (op == MP_BINARY_OP_EQUAL) {
161 : : // In particular, if we are checking for equality, here're the answer
162 : : return false;
163 : : }
164 : :
165 : : // Otherwise, application of relation op gives the answer
166 : 250 : return mp_binary_op(op, items1[i], items2[i]) == mp_const_true;
167 : : }
168 : :
169 : : // If we had tie in the last element...
170 : : // ... and we have lists of different lengths...
171 [ + + ]: 540 : if (len1 != len2) {
172 [ + + ]: 192 : if (len1 < len2) {
173 : : // ... then longer list length wins (we deal only with >)
174 : 96 : return false;
175 : : }
176 [ + + ]: 348 : } else if (op == MP_BINARY_OP_MORE) {
177 : : // Otherwise, if we have strict relation, sequence equality means failure
178 : 36 : return false;
179 : : }
180 : :
181 : : return true;
182 : : }
183 : :
184 : : // Special-case of index() which searches for mp_obj_t
185 : 100 : mp_obj_t mp_seq_index_obj(const mp_obj_t *items, size_t len, size_t n_args, const mp_obj_t *args) {
186 : 100 : const mp_obj_type_t *type = mp_obj_get_type(args[0]);
187 : 100 : mp_obj_t value = args[1];
188 : 100 : size_t start = 0;
189 : 100 : size_t stop = len;
190 : :
191 [ + + ]: 100 : if (n_args >= 3) {
192 : 48 : start = mp_get_index(type, len, args[2], true);
193 [ + + ]: 48 : if (n_args >= 4) {
194 : 20 : stop = mp_get_index(type, len, args[3], true);
195 : : }
196 : : }
197 : :
198 [ + + ]: 198 : for (size_t i = start; i < stop; i++) {
199 [ + + ]: 174 : if (mp_obj_equal(items[i], value)) {
200 : : // Common sense says this cannot overflow small int
201 : 76 : return MP_OBJ_NEW_SMALL_INT(i);
202 : : }
203 : : }
204 : :
205 : 24 : mp_raise_ValueError(MP_ERROR_TEXT("object not in sequence"));
206 : : }
207 : :
208 : 44 : mp_obj_t mp_seq_count_obj(const mp_obj_t *items, size_t len, mp_obj_t value) {
209 : 44 : size_t count = 0;
210 [ + + ]: 352 : for (size_t i = 0; i < len; i++) {
211 [ + + ]: 308 : if (mp_obj_equal(items[i], value)) {
212 : 68 : count++;
213 : : }
214 : : }
215 : :
216 : : // Common sense says this cannot overflow small int
217 : 44 : return MP_OBJ_NEW_SMALL_INT(count);
218 : : }
|