Lines Matching refs:SkipList
9 // Reads require a guarantee that the SkipList will not be destroyed
15 // (1) Allocated nodes are never deleted until the SkipList is
20 // immutable after the Node has been linked into the SkipList.
38 class SkipList {
43 // Create a new SkipList object that will use "cmp" for comparing keys,
45 // must remain allocated for the lifetime of the skiplist object.
46 explicit SkipList(Comparator cmp, Arena* arena);
60 explicit Iterator(const SkipList* list);
89 const SkipList* list_;
138 SkipList(const SkipList&);
139 void operator=(const SkipList&);
144 struct SkipList<Key,Comparator>::Node {
180 typename SkipList<Key,Comparator>::Node*
181 SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
188 inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {
194 inline bool SkipList<Key,Comparator>::Iterator::Valid() const {
199 inline const Key& SkipList<Key,Comparator>::Iterator::key() const {
205 inline void SkipList<Key,Comparator>::Iterator::Next() {
211 inline void SkipList<Key,Comparator>::Iterator::Prev() {
222 inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {
227 inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {
232 inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {
240 int SkipList<Key,Comparator>::RandomHeight() {
253 bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
259 typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)
281 typename SkipList<Key,Comparator>::Node*
282 SkipList<Key,Comparator>::FindLessThan(const Key& key) const {
302 typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast()
322 SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)
334 void SkipList<Key,Comparator>::Insert(const Key& key) {
370 bool SkipList<Key,Comparator>::Contains(const Key& key) const {
