about summary refs log tree commit diff
path: root/src/libstd/trie.rs
AgeCommit message (Collapse)AuthorLines
2014-02-20move extra::test to libtestLiigo Zhuang-1/+2
2014-02-11Move replace and swap to std::mem. Get rid of std::utilEdward Wang-4/+3
Also move Void to std::any, move drop to std::mem and reexport in prelude.
2014-02-09std: Add init and uninit to mem. Replace direct intrinsic usageBrian Anderson-1/+1
2014-02-07Cleaned up imports per coding standards.chromatic-4/+4
No functional changes; just style.
2014-02-07Removed prelude::* from libstd files.chromatic-1/+5
This replaces the imports from the prelude with the re-exported symbols.
2014-01-25Uppercase numeric constantsChris Wong-12/+12
The following are renamed: * `min_value` => `MIN` * `max_value` => `MAX` * `bits` => `BITS` * `bytes` => `BYTES` Fixes #10010.
2014-01-23Update flip() to be rev().Sean Chalmers-3/+3
Consensus leaned in favour of using rev instead of flip.
2014-01-23Rename Invert to Flip - Issue 10632Sean Chalmers-3/+3
Renamed the invert() function in iter.rs to flip(). Also renamed the Invert<T> type to Flip<T>. Some related code comments changed. Documentation that I could find has been updated, and all the instances I could locate where the function/type were called have been updated as well.
2014-01-21Remove unnecessary parentheses.Huon Wilson-1/+1
2014-01-18Rename iterators for consistencyPalmer Cox-27/+27
Rename existing iterators to get rid of the Iterator suffix and to give them names that better describe the things being iterated over.
2014-01-18std::trie: use unsafe code to give a 3x speed up to the iterator.Huon Wilson-39/+118
This stores the stack of iterators inline (we have a maximum depth with `uint` keys), and then uses direct pointer offsetting to manipulate it, in a blazing fast way: Before: bench_iter_large ... bench: 43187 ns/iter (+/- 3082) bench_iter_small ... bench: 618 ns/iter (+/- 288) After: bench_iter_large ... bench: 13497 ns/iter (+/- 1575) bench_iter_small ... bench: 220 ns/iter (+/- 91)
2014-01-18std::trie: remove each_{key,value}_reverse internal iterators.Huon Wilson-13/+1
This are *trivial* to reimplement in terms of each_reverse if that extra little bit of performance is needed.
2014-01-15std::trie: optimise insert slightly.Huon Wilson-34/+36
This reduces the number of moves/memcpy's we do, which makes insert faster, especially in cases of keys with long equal prefixes (the _low_bits tests): Before: bench_insert_large ... bench: 553966 ns/iter (+/- 64050) bench_insert_large_low_bits ... bench: 1048151 ns/iter (+/- 92484) bench_insert_small ... bench: 168840 ns/iter (+/- 22410) bench_insert_small_low_bits ... bench: 185069 ns/iter (+/- 38332) After: bench_insert_large ... bench: 422132 ns/iter (+/- 35112) bench_insert_large_low_bits ... bench: 339083 ns/iter (+/- 34421) bench_insert_small ... bench: 134539 ns/iter (+/- 15254) bench_insert_small_low_bits ... bench: 88775 ns/iter (+/- 5746)
2014-01-15std::trie: add benchmarks for insert.Huon Wilson-0/+48
2014-01-08std::trie: make lower_bound and upper_bound about 15% faster.Huon Wilson-10/+10
I believe this is mainly due to code-size reduction. Before: test [...]::bench_lower_bound ... bench: 818 ns/iter (+/- 100) test [...]::bench_upper_bound ... bench: 939 ns/iter (+/- 34) After: test [...]::bench_lower_bound ... bench: 698 ns/iter (+/- 60) test [...]::bench_upper_bound ... bench: 817 ns/iter (+/- 20)
2014-01-08std::trie: Add some iteration/search benchmarks.Huon Wilson-0/+60
2014-01-08std::trie: use macros to share code between the iterator implementations.Huon Wilson-129/+126
2014-01-08std::trie: remove some obsolete internal iterators.Huon Wilson-99/+3
2014-01-08std::trie: add an mutable-values iterator.Huon Wilson-0/+168
2013-12-27std: uniform modules titles for docLuca Bruno-1/+1
This commit uniforms the short title of modules provided by libstd, in order to make their roles more explicit when glancing at the index. Signed-off-by: Luca Bruno <lucab@debian.org>
2013-12-11Make 'self lifetime illegal.Erik Price-7/+7
Also remove all instances of 'self within the codebase. This fixes #10889.
2013-11-28Register new snapshotsAlex Crichton-2/+2
2013-11-26libstd: Remove all non-`proc` uses of `do` from libstdPatrick Walton-11/+11
2013-11-26Removed unneccessary `_iter` suffixes from various APIsMarvin Löbel-18/+18
2013-11-25std::trie: Fix find_mut for non-present keysJannis Harder-1/+12
Make TrieMap/TrieSet's find_mut check the key for external nodes. Without this find_mut sometimes returns a reference to another key when querying for a non-present key.
2013-11-19libstd: Change all uses of `&fn(A)->B` over to `|A|->B` in libstdPatrick Walton-12/+12
2013-10-22Drop the '2' suffix from logging macrosAlex Crichton-2/+2
Who doesn't like a massive renaming?
2013-10-09option: rewrite the API to use compositionDaniel Micay-1/+1
2013-09-30std: Remove usage of fmt!Alex Crichton-2/+2
2013-09-15Use std::iter::range_stepblake2-ppc-16/+12
Use the iterator version instead of the old uint::/int::range_step functions.
2013-09-09rename `std::iterator` to `std::iter`Daniel Micay-1/+0
The trait will keep the `Iterator` naming, but a more concise module name makes using the free functions less verbose. The module will define iterables in addition to iterators, as it deals with iteration in general.
2013-08-15std: Move the iterator param on FromIterator and Extendable to the method.Huon Wilson-8/+8
If they are on the trait then it is extremely annoying to use them as generic parameters to a function, e.g. with the iterator param on the trait itself, if one was to pass an Extendable<int> to a function that filled it either from a Range or a Map<VecIterator>, one needs to write something like: fn foo<E: Extendable<int, Range<int>> + Extendable<int, Map<&'self int, int, VecIterator<int>>> (e: &mut E, ...) { ... } since using a generic, i.e. `foo<E: Extendable<int, I>, I: Iterator<int>>` means that `foo` takes 2 type parameters, and the caller has to specify them (which doesn't work anyway, as they'll mismatch with the iterators used in `foo` itself). This patch changes it to: fn foo<E: Extendable<int>>(e: &mut E, ...) { ... }
2013-08-10Merge branch 'trie-bound-iters' of https://github.com/dim-an/rust into rollupErick Tryzelaar-0/+102
2013-08-10std: Rename Iterator.transform -> .mapErick Tryzelaar-2/+2
cc #5898
2013-08-10std: merge Iterator and IteratorUtilErick Tryzelaar-1/+1
2013-08-09Implement `lower_bound_iter`/`upper_bound_iter` for TrieMap/TrieSetDmitry Ermolov-0/+102
2013-08-07Implement DoubleEndedIterator on RangeKevin Ballard-14/+12
Range is now invertable as long as its element type conforms to Integer. Remove int::range_rev() et al in favor of range().invert().
2013-08-07std: Fix for-range loops that can use iteratorsblake2-ppc-2/+2
Fix inappropriate for-range loops to use for-iterator constructs (or other appropriate solution) instead.
2013-08-05Remove debug printing.Dmitry Ermolov-2/+0
2013-08-05Implemented iterator for TrieMapDmitry Ermolov-0/+96
Closes #5506.
2013-08-03auto merge of #8264 : thestinger/rust/snapshot, r=Aatchbors-8/+8
2013-08-03remove obsolete `foreach` keywordDaniel Micay-8/+8
this has been replaced by `for`
2013-08-03auto merge of #8246 : stepancheg/rust/contains-key, r=thestingerbors-6/+0
Map::contains_key can be implemented with Map::find. Remove several implementations of contains_key.
2013-08-03replace all remaining `for` with `foreach` or `do`Daniel Micay-17/+22
2013-08-03Add default implementation of Map::contains_key functionStepan Koltsov-6/+0
Map::contains_key can be implemented with Map::find. Remove several implementations of contains_key.
2013-08-02replace `range` with an external iteratorDaniel Micay-3/+3
2013-08-01std: Replace `for` with `do { .. }` expr where internal iterators are usedblake2-ppc-22/+29
2013-08-01migrate many `for` loops to `foreach`Daniel Micay-6/+7
2013-07-30std: Implement Extendable for hashmap, str and trieblake2-ppc-9/+17
2013-07-25Added default impls for container methodsSteven Fackler-23/+0
A couple of implementations of Container::is_empty weren't exactly self.len() == 0 so I left them alone (e.g. Treemap).
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 09:54:59 +0000