1 //! Simple, shared algorithm utilities.
2
3 use crate::lib::convert::AsRef;
4 use crate::lib::{mem, ptr, slice};
5
6 // ALGORITHMS
7
8 /// Calculate the difference between two pointers.
9 #[inline]
distance<T>(first: *const T, last: *const T) -> usize10 pub fn distance<T>(first: *const T, last: *const T)
11 -> usize
12 {
13 debug_assert!(last >= first, "range must be positive.");
14 let f = first as usize;
15 let l = last as usize;
16 l - f
17 }
18
19 /// Check if two slices are equal to each other.
20 #[inline]
equal_to_slice(l: &[u8], r: &[u8]) -> bool21 pub fn equal_to_slice(l: &[u8], r: &[u8])
22 -> bool
23 {
24 l == r
25 }
26
27 /// Check if left iter starts with right iter.
28 #[inline]
29 #[cfg(feature = "format")]
starts_with_iter<'a, Iter1, Iter2>(mut l: Iter1, mut r: Iter2) -> (bool, Iter1) where Iter1: Iterator<Item=&'a u8>, Iter2: Iterator<Item=&'a u8>30 pub fn starts_with_iter<'a, Iter1, Iter2>(mut l: Iter1, mut r: Iter2)
31 -> (bool, Iter1)
32 where Iter1: Iterator<Item=&'a u8>,
33 Iter2: Iterator<Item=&'a u8>
34 {
35 loop {
36 // Only call `next()` on l if r is not None, otherwise,
37 // we may incorrectly consume an l character.
38 let ri = r.next();
39 if ri.is_none() {
40 return (true, l);
41 } else if l.next() != ri {
42 return (false, l);
43 }
44 }
45 }
46
47 /// Check if left iter starts with right iter without case-sensitivity.
48 #[inline]
case_insensitive_starts_with_iter<'a, Iter1, Iter2>(mut l: Iter1, mut r: Iter2) -> (bool, Iter1) where Iter1: Iterator<Item=&'a u8>, Iter2: Iterator<Item=&'a u8>49 pub fn case_insensitive_starts_with_iter<'a, Iter1, Iter2>(mut l: Iter1, mut r: Iter2)
50 -> (bool, Iter1)
51 where Iter1: Iterator<Item=&'a u8>,
52 Iter2: Iterator<Item=&'a u8>
53 {
54 loop {
55 let ri = r.next().map(|x| x.to_ascii_lowercase());
56 if ri.is_none() {
57 return (true, l);
58 } else if l.next().map(|x| x.to_ascii_lowercase()) != ri {
59 return (false, l);
60 }
61 }
62 }
63
64 /// Check if left slice ends with right slice.
65 #[inline]
ends_with_slice(l: &[u8], r: &[u8]) -> bool66 pub fn ends_with_slice(l: &[u8], r: &[u8])
67 -> bool
68 {
69 // This cannot be out-of-bounds, since we check `l.len() >= r.len()`
70 // previous to extracting the subslice, so `l.len() - r.len()` must
71 // also be <= l.len() and >= 0.
72 let rget = move || unsafe {l.get_unchecked(l.len()-r.len()..)};
73 l.len() >= r.len() && equal_to_slice(rget(), r)
74 }
75
76 /// Trim character from the left-side of a slice.
77 #[inline]
ltrim_char_slice<'a>(slc: &'a [u8], c: u8) -> (&'a [u8], usize)78 pub fn ltrim_char_slice<'a>(slc: &'a [u8], c: u8)
79 -> (&'a [u8], usize)
80 {
81 let count = slc.iter().take_while(|&&si| si == c).count();
82 // This count cannot exceed the bounds of the slice, since it is
83 // derived from an iterator using the standard library to generate it.
84 debug_assert!(count <= slc.len());
85 let slc = unsafe {slc.get_unchecked(count..)};
86 (slc, count)
87 }
88
89 /// Trim characters from the left-side of a slice.
90 #[inline]
91 #[cfg(feature = "format")]
ltrim_char2_slice<'a>(slc: &'a [u8], c1: u8, c2: u8) -> (&'a [u8], usize)92 pub fn ltrim_char2_slice<'a>(slc: &'a [u8], c1: u8, c2: u8)
93 -> (&'a [u8], usize)
94 {
95 let count = slc.iter().take_while(|&&si| si == c1 || si == c2).count();
96 // This count cannot exceed the bounds of the slice, since it is
97 // derived from an iterator using the standard library to generate it.
98 debug_assert!(count <= slc.len());
99 let slc = unsafe {slc.get_unchecked(count..)};
100 (slc, count)
101 }
102
103 /// Trim character from the right-side of a slice.
104 #[inline]
rtrim_char_slice<'a>(slc: &'a [u8], c: u8) -> (&'a [u8], usize)105 pub fn rtrim_char_slice<'a>(slc: &'a [u8], c: u8)
106 -> (&'a [u8], usize)
107 {
108 let count = slc.iter().rev().take_while(|&&si| si == c).count();
109 let index = slc.len() - count;
110 // Count must be <= slc.len(), and therefore, slc.len() - count must
111 // also be <= slc.len(), since this is derived from an iterator
112 // in the standard library.
113 debug_assert!(count <= slc.len());
114 debug_assert!(index <= slc.len());
115 let slc = unsafe {slc.get_unchecked(..index)};
116 (slc, count)
117 }
118
119 /// Trim character from the right-side of a slice.
120 #[inline]
121 #[cfg(feature = "format")]
rtrim_char2_slice<'a>(slc: &'a [u8], c1: u8, c2: u8) -> (&'a [u8], usize)122 pub fn rtrim_char2_slice<'a>(slc: &'a [u8], c1: u8, c2: u8)
123 -> (&'a [u8], usize)
124 {
125 let count = slc.iter().rev().take_while(|&&si| si == c1 || si == c2).count();
126 let index = slc.len() - count;
127 // Count must be <= slc.len(), and therefore, slc.len() - count must
128 // also be <= slc.len(), since this is derived from an iterator
129 // in the standard library.
130 debug_assert!(count <= slc.len());
131 debug_assert!(index <= slc.len());
132 let slc = unsafe {slc.get_unchecked(..index)};
133 (slc, count)
134 }
135
136 /// Copy from source-to-dst.
137 #[inline]
copy_to_dst<'a, Bytes: AsRef<[u8]>>(dst: &'a mut [u8], src: Bytes) -> usize138 pub fn copy_to_dst<'a, Bytes: AsRef<[u8]>>(dst: &'a mut [u8], src: Bytes)
139 -> usize
140 {
141 let src = src.as_ref();
142 let dst = &mut index_mut!(dst[..src.len()]);
143
144 unsafe {
145 ptr::copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), dst.len());
146 }
147
148 src.len()
149 }
150
151 /// Length-check variant of ptr::write_bytes for a slice.
152 #[cfg(not(any(feature = "grisu3", feature = "ryu")))]
153 #[inline]
write_bytes(dst: &mut [u8], byte: u8)154 pub fn write_bytes(dst: &mut [u8], byte: u8)
155 {
156 unsafe {
157 ptr::write_bytes(dst.as_mut_ptr(), byte, dst.len());
158 }
159 }
160
161 // TEST
162 // ----
163
164 #[cfg(test)]
165 mod tests {
166 use super::*;
167
168 #[test]
distance_test()169 fn distance_test() {
170 unsafe {
171 let x: [u8; 10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
172 let first: *const u8 = x.as_ptr();
173 let last = first.add(x.len());
174 assert_eq!(distance(first, last), 10);
175 }
176 }
177
178 #[test]
equal_to_test()179 fn equal_to_test() {
180 let x = "Hello";
181 let y = "Hello";
182 let z = "hello";
183
184 assert!(equal_to_slice(x.as_bytes(), y.as_bytes()));
185 assert!(!equal_to_slice(x.as_bytes(), z.as_bytes()));
186 assert!(!equal_to_slice(y.as_bytes(), z.as_bytes()));
187 }
188
189 #[test]
190 #[cfg(feature = "format")]
starts_with_test()191 fn starts_with_test() {
192 let w = b"Hello";
193 let x = b"H";
194 let y = b"h";
195 let z = b"a";
196
197 // forward
198 assert!(starts_with_iter(w.iter(), x.iter()).0);
199 assert!(!starts_with_iter(w.iter(), y.iter()).0);
200 assert!(!starts_with_iter(x.iter(), y.iter()).0);
201 assert!(!starts_with_iter(w.iter(), z.iter()).0);
202 assert!(!starts_with_iter(x.iter(), z.iter()).0);
203 assert!(!starts_with_iter(y.iter(), z.iter()).0);
204
205 // back
206 assert!(!starts_with_iter(x.iter(), w.iter()).0);
207 assert!(!starts_with_iter(y.iter(), w.iter()).0);
208 assert!(!starts_with_iter(z.iter(), w.iter()).0);
209 }
210
211 #[test]
case_insensitive_starts_with_test()212 fn case_insensitive_starts_with_test() {
213 let w = b"Hello";
214 let x = b"H";
215 let y = b"h";
216 let z = b"a";
217
218 // forward
219 assert!(case_insensitive_starts_with_iter(w.iter(), x.iter()).0);
220 assert!(case_insensitive_starts_with_iter(w.iter(), y.iter()).0);
221 assert!(case_insensitive_starts_with_iter(x.iter(), y.iter()).0);
222 assert!(!case_insensitive_starts_with_iter(w.iter(), z.iter()).0);
223 assert!(!case_insensitive_starts_with_iter(x.iter(), z.iter()).0);
224 assert!(!case_insensitive_starts_with_iter(y.iter(), z.iter()).0);
225
226 // back
227 assert!(!case_insensitive_starts_with_iter(x.iter(), w.iter()).0);
228 assert!(!case_insensitive_starts_with_iter(y.iter(), w.iter()).0);
229 assert!(!case_insensitive_starts_with_iter(z.iter(), w.iter()).0);
230 }
231
232 #[test]
ends_with_test()233 fn ends_with_test() {
234 let w = "Hello";
235 let x = "lO";
236 let y = "lo";
237 let z = "o";
238
239 // forward
240 assert!(!ends_with_slice(w.as_bytes(), x.as_bytes()));
241 assert!(ends_with_slice(w.as_bytes(), y.as_bytes()));
242 assert!(ends_with_slice(w.as_bytes(), z.as_bytes()));
243 assert!(!ends_with_slice(x.as_bytes(), y.as_bytes()));
244 assert!(!ends_with_slice(x.as_bytes(), z.as_bytes()));
245 assert!(ends_with_slice(y.as_bytes(), z.as_bytes()));
246
247 // back
248 assert!(!ends_with_slice(z.as_bytes(), y.as_bytes()));
249 assert!(!ends_with_slice(z.as_bytes(), x.as_bytes()));
250 assert!(!ends_with_slice(z.as_bytes(), w.as_bytes()));
251 assert!(!ends_with_slice(y.as_bytes(), x.as_bytes()));
252 assert!(!ends_with_slice(y.as_bytes(), w.as_bytes()));
253 assert!(!ends_with_slice(x.as_bytes(), w.as_bytes()));
254 }
255
256 #[test]
ltrim_char_test()257 fn ltrim_char_test() {
258 let w = "0001";
259 let x = "1010";
260 let y = "1.00";
261 let z = "1e05";
262
263 assert_eq!(ltrim_char_slice(w.as_bytes(), b'0').1, 3);
264 assert_eq!(ltrim_char_slice(x.as_bytes(), b'0').1, 0);
265 assert_eq!(ltrim_char_slice(x.as_bytes(), b'1').1, 1);
266 assert_eq!(ltrim_char_slice(y.as_bytes(), b'0').1, 0);
267 assert_eq!(ltrim_char_slice(y.as_bytes(), b'1').1, 1);
268 assert_eq!(ltrim_char_slice(z.as_bytes(), b'0').1, 0);
269 assert_eq!(ltrim_char_slice(z.as_bytes(), b'1').1, 1);
270 }
271
272 #[test]
273 #[cfg(feature = "format")]
ltrim_char2_test()274 fn ltrim_char2_test() {
275 let w = "0001";
276 let x = "1010";
277 let y = "1.00";
278 let z = "1e05";
279 let a = "0_01";
280
281 assert_eq!(ltrim_char2_slice(w.as_bytes(), b'0', b'_').1, 3);
282 assert_eq!(ltrim_char2_slice(x.as_bytes(), b'0', b'_').1, 0);
283 assert_eq!(ltrim_char2_slice(x.as_bytes(), b'1', b'_').1, 1);
284 assert_eq!(ltrim_char2_slice(y.as_bytes(), b'0', b'_').1, 0);
285 assert_eq!(ltrim_char2_slice(y.as_bytes(), b'1', b'_').1, 1);
286 assert_eq!(ltrim_char2_slice(z.as_bytes(), b'0', b'_').1, 0);
287 assert_eq!(ltrim_char2_slice(z.as_bytes(), b'1', b'_').1, 1);
288 assert_eq!(ltrim_char2_slice(a.as_bytes(), b'0', b'_').1, 3);
289 assert_eq!(ltrim_char2_slice(a.as_bytes(), b'1', b'_').1, 0);
290 }
291
292 #[test]
rtrim_char_test()293 fn rtrim_char_test() {
294 let w = "0001";
295 let x = "1010";
296 let y = "1.00";
297 let z = "1e05";
298
299 assert_eq!(rtrim_char_slice(w.as_bytes(), b'0').1, 0);
300 assert_eq!(rtrim_char_slice(x.as_bytes(), b'0').1, 1);
301 assert_eq!(rtrim_char_slice(x.as_bytes(), b'1').1, 0);
302 assert_eq!(rtrim_char_slice(y.as_bytes(), b'0').1, 2);
303 assert_eq!(rtrim_char_slice(y.as_bytes(), b'1').1, 0);
304 assert_eq!(rtrim_char_slice(z.as_bytes(), b'0').1, 0);
305 assert_eq!(rtrim_char_slice(z.as_bytes(), b'5').1, 1);
306 }
307
308 #[test]
309 #[cfg(feature = "format")]
rtrim_char2_test()310 fn rtrim_char2_test() {
311 let w = "0001";
312 let x = "1010";
313 let y = "1.00";
314 let z = "1e05";
315 let a = "0_01";
316
317 assert_eq!(rtrim_char2_slice(w.as_bytes(), b'0', b'_').1, 0);
318 assert_eq!(rtrim_char2_slice(x.as_bytes(), b'0', b'_').1, 1);
319 assert_eq!(rtrim_char2_slice(x.as_bytes(), b'1', b'_').1, 0);
320 assert_eq!(rtrim_char2_slice(y.as_bytes(), b'0', b'_').1, 2);
321 assert_eq!(rtrim_char2_slice(y.as_bytes(), b'1', b'_').1, 0);
322 assert_eq!(rtrim_char2_slice(z.as_bytes(), b'0', b'_').1, 0);
323 assert_eq!(rtrim_char2_slice(z.as_bytes(), b'1', b'_').1, 0);
324 assert_eq!(rtrim_char2_slice(a.as_bytes(), b'0', b'_').1, 0);
325 assert_eq!(rtrim_char2_slice(a.as_bytes(), b'1', b'_').1, 1);
326 }
327 }
328