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.
38void mp_seq_multiply(const void *items, size_t item_sz, size_t len, size_t times, void *dest) {
39 for (size_t i = 0; i < times; i++) {
40 size_t copy_sz = item_sz * len;
41 memcpy(dest, items, copy_sz);
42 dest = (char *)dest + copy_sz;
43 }
44}
45
46#if MICROPY_PY_BUILTINS_SLICE
47
48bool mp_seq_get_fast_slice_indexes(mp_uint_t len, mp_obj_t slice, mp_bound_slice_t *indexes) {
49 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 if (indexes->step < 0) {
53 indexes->stop++;
54 }
55
56 // CPython returns empty sequence in such case, or point for assignment is at start
57 if (indexes->step > 0 && indexes->start > indexes->stop) {
58 indexes->stop = indexes->start;
59 } else if (indexes->step < 0 && indexes->start < indexes->stop) {
60 indexes->stop = indexes->start + 1;
61 }
62
63 return indexes->step == 1;
64}
65
66#endif
67
68mp_obj_t mp_seq_extract_slice(size_t len, const mp_obj_t *seq, mp_bound_slice_t *indexes) {
69 (void)len; // TODO can we remove len from the arg list?
70
71 mp_int_t start = indexes->start, stop = indexes->stop;
72 mp_int_t step = indexes->step;
73
74 mp_obj_t res = mp_obj_new_list(0, NULL);
75
76 if (step < 0) {
77 while (start >= stop) {
78 mp_obj_list_append(res, seq[start]);
79 start += step;
80 }
81 } else {
82 while (start < stop) {
83 mp_obj_list_append(res, seq[start]);
84 start += step;
85 }
86 }
87 return res;
88}
89
90// Special-case comparison function for sequences of bytes
91// Don't pass MP_BINARY_OP_NOT_EQUAL here
92bool mp_seq_cmp_bytes(mp_uint_t op, const byte *data1, size_t len1, const byte *data2, size_t len2) {
93 if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
94 return false;
95 }
96
97 // Let's deal only with > & >=
98 if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
99 SWAP(const byte *, data1, data2);
100 SWAP(size_t, len1, len2);
101 if (op == MP_BINARY_OP_LESS) {
102 op = MP_BINARY_OP_MORE;
103 } else {
104 op = MP_BINARY_OP_MORE_EQUAL;
105 }
106 }
107 size_t min_len = len1 < len2 ? len1 : len2;
108 int res = memcmp(data1, data2, min_len);
109 if (op == MP_BINARY_OP_EQUAL) {
110 // If we are checking for equality, here's the answer
111 return res == 0;
112 }
113 if (res < 0) {
114 return false;
115 }
116 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 if (len1 != len2) {
123 if (len1 < len2) {
124 // ... then longer list length wins (we deal only with >)
125 return false;
126 }
127 } else if (op == MP_BINARY_OP_MORE) {
128 // Otherwise, if we have strict relation, equality means failure
129 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
136bool 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 if (op == MP_BINARY_OP_EQUAL && len1 != len2) {
138 return false;
139 }
140
141 // Let's deal only with > & >=
142 if (op == MP_BINARY_OP_LESS || op == MP_BINARY_OP_LESS_EQUAL) {
143 SWAP(const mp_obj_t *, items1, items2);
144 SWAP(size_t, len1, len2);
145 if (op == MP_BINARY_OP_LESS) {
146 op = MP_BINARY_OP_MORE;
147 } else {
148 op = MP_BINARY_OP_MORE_EQUAL;
149 }
150 }
151
152 size_t len = len1 < len2 ? len1 : len2;
153 for (size_t i = 0; i < len; i++) {
154 // If current elements equal, can't decide anything - go on
155 if (mp_obj_equal(items1[i], items2[i])) {
156 continue;
157 }
158
159 // Othewise, if they are not equal, we can have final decision based on them
160 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 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 if (len1 != len2) {
172 if (len1 < len2) {
173 // ... then longer list length wins (we deal only with >)
174 return false;
175 }
176 } else if (op == MP_BINARY_OP_MORE) {
177 // Otherwise, if we have strict relation, sequence equality means failure
178 return false;
179 }
180
181 return true;
182}
183
184// Special-case of index() which searches for mp_obj_t
185mp_obj_t mp_seq_index_obj(const mp_obj_t *items, size_t len, size_t n_args, const mp_obj_t *args) {
186 const mp_obj_type_t *type = mp_obj_get_type(args[0]);
187 mp_obj_t value = args[1];
188 size_t start = 0;
189 size_t stop = len;
190
191 if (n_args >= 3) {
192 start = mp_get_index(type, len, args[2], true);
193 if (n_args >= 4) {
194 stop = mp_get_index(type, len, args[3], true);
195 }
196 }
197
198 for (size_t i = start; i < stop; i++) {
199 if (mp_obj_equal(items[i], value)) {
200 // Common sense says this cannot overflow small int
201 return MP_OBJ_NEW_SMALL_INT(i);
202 }
203 }
204
205 mp_raise_ValueError(MP_ERROR_TEXT("object not in sequence"));
206}
207
208mp_obj_t mp_seq_count_obj(const mp_obj_t *items, size_t len, mp_obj_t value) {
209 size_t count = 0;
210 for (size_t i = 0; i < len; i++) {
211 if (mp_obj_equal(items[i], value)) {
212 count++;
213 }
214 }
215
216 // Common sense says this cannot overflow small int
217 return MP_OBJ_NEW_SMALL_INT(count);
218}
219