use crate::level_generator::{GeometricalLevelGenerator, LevelGenerator};
use std::{
borrow::Borrow, cmp, cmp::Ordering, default, fmt, hash, hash::Hash, iter, marker::PhantomData,
mem, ops, ops::Bound,
};
#[derive(Clone, Debug)]
struct SkipNode<K, V> {
key: Option<K>,
value: Option<V>,
level: usize,
next: Option<Box<SkipNode<K, V>>>,
prev: Option<*mut SkipNode<K, V>>,
links: Vec<Option<*mut SkipNode<K, V>>>,
links_len: Vec<usize>,
}
impl<K, V> SkipNode<K, V> {
fn head(total_levels: usize) -> Self {
SkipNode {
key: None,
value: None,
level: total_levels - 1,
next: None,
prev: None,
links: iter::repeat(None).take(total_levels).collect(),
links_len: iter::repeat(0).take(total_levels).collect(),
}
}
fn new(key: K, value: V, level: usize) -> Self {
SkipNode {
key: Some(key),
value: Some(value),
level,
next: None,
prev: None,
links: iter::repeat(None).take(level + 1).collect(),
links_len: iter::repeat(0).take(level + 1).collect(),
}
}
fn into_inner(self) -> Option<(K, V)> {
if self.key.is_some() {
Some((self.key.unwrap(), self.value.unwrap()))
} else {
None
}
}
fn is_head(&self) -> bool {
self.prev.is_none()
}
}
impl<K, V> fmt::Display for SkipNode<K, V>
where
K: fmt::Display,
V: fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if let (&Some(ref k), &Some(ref v)) = (&self.key, &self.value) {
write!(f, "({}, {})", k, v)
} else {
Ok(())
}
}
}
pub struct SkipMap<K, V> {
head: Box<SkipNode<K, V>>,
len: usize,
level_generator: GeometricalLevelGenerator,
}
impl<K, V> SkipMap<K, V>
where
K: cmp::Ord,
{
#[inline]
pub fn new() -> Self {
let lg = GeometricalLevelGenerator::new(16, 1.0 / 2.0);
SkipMap {
head: Box::new(SkipNode::head(lg.total())),
len: 0,
level_generator: lg,
}
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
let levels = cmp::max(1, (capacity as f64).log2().floor() as usize);
let lg = GeometricalLevelGenerator::new(levels, 1.0 / 2.0);
SkipMap {
head: Box::new(SkipNode::head(lg.total())),
len: 0,
level_generator: lg,
}
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
unsafe {
let mut node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut existing_node: Option<*mut SkipNode<K, V>> = None;
let mut prev_nodes: Vec<*mut SkipNode<K, V>> =
Vec::with_capacity(self.level_generator.total());
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
if let Some(existing_node) = existing_node {
while let Some(next) = (*node).links[lvl] {
if next == existing_node {
prev_nodes.push(node);
break;
} else {
node = next;
continue;
}
}
} else {
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.cmp(&key) {
Ordering::Less => {
node = next;
continue;
}
Ordering::Equal => {
existing_node = Some(next);
prev_nodes.push(node);
break;
}
Ordering::Greater => {
prev_nodes.push(node);
break;
}
}
}
}
if (*node).links[lvl].is_none() {
prev_nodes.push(node);
continue;
}
}
}
if let Some(existing_node) = existing_node {
mem::replace(&mut (*existing_node).value, Some(value))
} else {
let mut new_node =
Box::new(SkipNode::new(key, value, self.level_generator.random()));
let new_node_ptr: *mut SkipNode<K, V> = mem::transmute_copy(&new_node);
for (lvl, &prev_node) in prev_nodes.iter().rev().enumerate() {
if lvl <= new_node.level {
new_node.links[lvl] = (*prev_node).links[lvl];
(*prev_node).links[lvl] = Some(new_node_ptr);
if lvl == 0 {
new_node.prev = Some(prev_node);
if let Some(next) = new_node.links[lvl] {
(*next).prev = Some(new_node_ptr);
}
new_node.links_len[lvl] = 1;
} else {
let length = self
.link_length(prev_node, Some(new_node_ptr), lvl)
.unwrap();
new_node.links_len[lvl] = (*prev_node).links_len[lvl] - length + 1;
(*prev_node).links_len[lvl] = length;
}
} else {
(*prev_node).links_len[lvl] += 1;
}
}
let prev_node = (*new_node_ptr).prev.unwrap();
let tmp = mem::replace(&mut (*prev_node).next, Some(new_node));
if let Some(ref mut node) = (*prev_node).next {
node.next = tmp;
}
self.len += 1;
None
}
}
}
}
impl<K, V> SkipMap<K, V> {
#[inline]
pub fn clear(&mut self) {
unsafe {
let node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
while let Some(ref mut next) = (*node).next {
mem::replace(&mut (*node).next, mem::replace(&mut next.next, None));
}
}
let new_head = Box::new(SkipNode::head(self.level_generator.total()));
self.len = 0;
mem::replace(&mut self.head, new_head);
}
#[inline]
pub fn len(&self) -> usize {
self.len
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[inline]
pub fn front(&self) -> Option<(&K, &V)> {
if self.is_empty() {
None
} else {
let node = self.get_index(0);
unsafe {
Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_ref().unwrap(),
))
}
}
}
#[inline]
pub fn front_mut(&self) -> Option<(&K, &mut V)> {
if self.is_empty() {
None
} else {
let node = self.get_index(0) as *mut SkipNode<K, V>;
unsafe {
Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_mut().unwrap(),
))
}
}
}
#[inline]
pub fn back(&self) -> Option<(&K, &V)> {
let len = self.len();
if len > 0 {
let node = self.get_index(len - 1);
unsafe {
Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_ref().unwrap(),
))
}
} else {
None
}
}
#[inline]
pub fn back_mut(&mut self) -> Option<(&K, &mut V)> {
let len = self.len();
if len > 0 {
let node = self.get_index(len - 1) as *mut SkipNode<K, V>;
unsafe {
Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_mut().unwrap(),
))
}
} else {
None
}
}
#[inline]
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Ord,
{
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.borrow().cmp(key) {
Ordering::Less => {
node = next;
continue;
}
Ordering::Equal => {
return (*next).value.as_ref();
}
Ordering::Greater => break,
}
}
}
}
None
}
}
#[inline]
pub fn get_mut<Q: ?Sized>(&self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Ord,
{
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.borrow().cmp(key) {
Ordering::Less => {
node = next;
continue;
}
Ordering::Equal => return (*next).value.as_mut(),
Ordering::Greater => break,
}
}
}
}
None
}
}
#[inline]
pub fn pop_front(&mut self) -> Option<(K, V)> {
if self.is_empty() {
None
} else {
Some(self.remove_index(0))
}
}
#[inline]
pub fn pop_back(&mut self) -> Option<(K, V)> {
let len = self.len();
if len > 0 {
Some(self.remove_index(len - 1))
} else {
None
}
}
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Ord,
{
unsafe {
let mut node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.borrow().cmp(key) {
Ordering::Less => {
node = next;
continue;
}
Ordering::Equal => {
return true;
}
Ordering::Greater => {
break;
}
}
}
}
}
false
}
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Ord,
{
if self.len == 0 {
return None;
}
unsafe {
let mut node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut return_node: Option<*mut SkipNode<K, V>> = None;
let mut prev_nodes: Vec<*mut SkipNode<K, V>> =
Vec::with_capacity(self.level_generator.total());
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
if let Some(return_node) = return_node {
while let Some(next) = (*node).links[lvl] {
if next == return_node {
prev_nodes.push(node);
break;
} else {
node = next;
}
}
} else {
if (*node).links[lvl].is_none() {
prev_nodes.push(node);
continue;
}
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.borrow().cmp(key) {
Ordering::Less => {
node = next;
continue;
}
Ordering::Equal => {
return_node = Some(next);
prev_nodes.push(node);
break;
}
Ordering::Greater => {
prev_nodes.push(node);
break;
}
}
}
}
}
}
if let Some(return_node) = return_node {
for (lvl, &prev_node) in prev_nodes.iter().rev().enumerate() {
if (*prev_node).links[lvl] == Some(return_node) {
(*prev_node).links[lvl] = (*return_node).links[lvl];
(*prev_node).links_len[lvl] += (*return_node).links_len[lvl] - 1;
} else {
(*prev_node).links_len[lvl] -= 1;
}
}
if let Some(next_node) = (*return_node).links[0] {
(*next_node).prev = (*return_node).prev;
}
self.len -= 1;
Some(
mem::replace(
&mut (*(*return_node).prev.unwrap()).next,
mem::replace(&mut (*return_node).next, None),
)
.unwrap()
.into_inner()
.unwrap()
.1,
)
} else {
None
}
}
}
pub fn remove_index(&mut self, index: usize) -> (K, V) {
unsafe {
if index >= self.len() {
panic!("Index out of bounds.");
} else {
let mut node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut return_node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut index_sum = 0;
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while index_sum + (*node).links_len[lvl] < index {
index_sum += (*node).links_len[lvl];
node = (*node).links[lvl].unwrap();
}
if index_sum + (*node).links_len[lvl] == index {
if let Some(next) = (*node).links[lvl] {
return_node = next;
(*node).links[lvl] = (*next).links[lvl];
(*node).links_len[lvl] += (*next).links_len[lvl] - 1;
}
} else {
(*node).links_len[lvl] -= 1;
}
}
if let Some(next) = (*return_node).links[0] {
(*next).prev = (*return_node).prev;
}
self.len -= 1;
mem::replace(
&mut (*(*return_node).prev.unwrap()).next,
mem::replace(&mut (*return_node).next, None),
)
.unwrap()
.into_inner()
.unwrap()
}
}
}
#[allow(clippy::should_implement_trait)]
pub fn into_iter(self) -> IntoIter<K, V> {
IntoIter {
head: unsafe { mem::transmute_copy(&self.head) },
end: self.get_last() as *mut SkipNode<K, V>,
size: self.len(),
skipmap: self,
}
}
pub fn iter(&self) -> Iter<K, V> {
Iter {
start: unsafe { mem::transmute_copy(&self.head) },
end: self.get_last(),
size: self.len(),
_lifetime_k: PhantomData,
_lifetime_v: PhantomData,
}
}
pub fn iter_mut(&self) -> IterMut<K, V> {
IterMut {
start: unsafe { mem::transmute_copy(&self.head) },
end: self.get_last() as *mut SkipNode<K, V>,
size: self.len(),
_lifetime_k: PhantomData,
_lifetime_v: PhantomData,
}
}
pub fn keys(&self) -> Keys<K, V> {
Keys {
start: unsafe { mem::transmute_copy(&self.head) },
end: self.get_last(),
size: self.len(),
_lifetime_k: PhantomData,
}
}
pub fn values(&self) -> Values<K, V> {
Values {
start: unsafe { mem::transmute_copy(&self.head) },
end: self.get_last(),
size: self.len(),
_lifetime_v: PhantomData,
}
}
pub fn range<Q>(&self, min: Bound<&Q>, max: Bound<&Q>) -> Iter<K, V>
where
K: Borrow<Q>,
Q: Ord,
{
unsafe {
let start = match min {
Bound::Included(min) => {
let mut node = self.find_key(min);
if let Some(ref key) = (*node).key {
if key.borrow() == min {
node = (*node).prev.unwrap();
}
}
node
}
Bound::Excluded(min) => self.find_key(min),
Bound::Unbounded => mem::transmute_copy(&self.head),
};
let end = match max {
Bound::Included(max) => self.find_key(max),
Bound::Excluded(max) => {
let mut node = self.find_key(max);
if let Some(ref key) = (*node).key {
if key.borrow() == max {
node = (*node).prev.unwrap();
}
}
node
}
Bound::Unbounded => self.get_last(),
};
match self.link_length(
start as *mut SkipNode<K, V>,
Some(end as *mut SkipNode<K, V>),
cmp::min((*start).level, (*end).level) + 1,
) {
Err(_) => Iter {
start,
end: start,
size: 0,
_lifetime_k: PhantomData,
_lifetime_v: PhantomData,
},
Ok(l) => Iter {
start,
end,
size: l,
_lifetime_k: PhantomData,
_lifetime_v: PhantomData,
},
}
}
}
}
impl<K, V> SkipMap<K, V> {
#[allow(dead_code)]
fn check(&self) {
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
assert!((*node).is_head() == (*node).key.is_none());
assert!((*node).key.is_none() == (*node).value.is_none());
assert!((*node).value.is_none() == (*node).prev.is_none());
let mut length_sum;
for lvl in 0..self.level_generator.total() {
length_sum = 0;
node = mem::transmute_copy(&self.head);
loop {
length_sum += (*node).links_len[lvl];
assert_eq!((*node).level + 1, (*node).links.len());
assert_eq!((*node).level + 1, (*node).links_len.len());
assert_eq!(
(*node).links_len[lvl],
self.link_length(node as *mut SkipNode<K, V>, (*node).links[lvl], lvl)
.unwrap()
);
if lvl == 0 {
assert!((*node).next.is_some() == (*node).links[lvl].is_some());
if let Some(prev) = (*node).prev {
assert_eq!((*prev).links[lvl], Some(node as *mut SkipNode<K, V>));
assert_eq!(node, mem::transmute_copy((*prev).next.as_ref().unwrap()));
}
}
if let Some(next) = (*node).links[lvl] {
assert!((*next).key.is_some());
node = next;
} else {
break;
}
}
assert_eq!(length_sum, self.len());
}
}
}
fn link_length(
&self,
start: *mut SkipNode<K, V>,
end: Option<*mut SkipNode<K, V>>,
lvl: usize,
) -> Result<usize, bool> {
unsafe {
let mut length = 0;
let mut node = start;
if lvl == 0 {
while Some(node) != end {
length += 1;
if (*node).is_head() {
length -= 1;
}
match (*node).links[lvl] {
Some(ptr) => node = ptr,
None => break,
}
}
} else {
while Some(node) != end {
length += (*node).links_len[lvl - 1];
match (*node).links[lvl - 1] {
Some(ptr) => node = ptr,
None => break,
}
}
}
if let Some(end) = end {
if node != end {
return Err(false);
}
}
Ok(length)
}
}
fn get_last(&self) -> *const SkipNode<K, V> {
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while let Some(next) = (*node).links[lvl] {
node = next;
}
}
node
}
}
fn find_key<Q: ?Sized>(&self, key: &Q) -> *const SkipNode<K, V>
where
K: Borrow<Q>,
Q: Ord,
{
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while let Some(next) = (*node).links[lvl] {
if let Some(ref next_key) = (*next).key {
match next_key.borrow().cmp(key) {
Ordering::Less => node = next,
Ordering::Equal => return next,
Ordering::Greater => break,
}
} else {
panic!("Encountered a value-less node.");
}
}
}
node
}
}
fn get_index(&self, index: usize) -> *const SkipNode<K, V> {
unsafe {
if index >= self.len() {
panic!("Index out of bounds.");
} else {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut index_sum = 0;
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
while index_sum + (*node).links_len[lvl] <= index {
index_sum += (*node).links_len[lvl];
node = (*node).links[lvl].unwrap();
}
}
node
}
}
}
}
impl<K, V> SkipMap<K, V>
where
K: fmt::Debug,
V: fmt::Debug,
{
#[allow(dead_code)]
fn debug_structure(&self) {
unsafe {
let mut node: *const SkipNode<K, V> = mem::transmute_copy(&self.head);
let mut rows: Vec<_> = iter::repeat(String::new())
.take(self.level_generator.total())
.collect();
loop {
let value = if let (&Some(ref k), &Some(ref v)) = (&(*node).key, &(*node).value) {
format!("> ({:?}, {:?})", k, v)
} else {
"> ()".to_string()
};
let max_str_len = format!("{} -{}-", value, (*node).links_len[(*node).level]).len();
let mut lvl = self.level_generator.total();
while lvl > 0 {
lvl -= 1;
let mut value_len = if lvl <= (*node).level {
format!("{} -{}-", value, (*node).links_len[lvl])
} else {
format!("{} -", value)
};
for _ in 0..(max_str_len - value_len.len()) {
value_len.push('-');
}
let mut dashes = String::new();
for _ in 0..value_len.len() {
dashes.push('-');
}
if lvl <= (*node).level {
rows[lvl].push_str(value_len.as_ref());
} else {
rows[lvl].push_str(dashes.as_ref());
}
}
if let Some(next) = (*node).links[0] {
node = next;
} else {
break;
}
}
for row in rows.iter().rev() {
println!("{}", row);
}
}
}
}
unsafe impl<K: Send, V: Send> Send for SkipMap<K, V> {}
unsafe impl<K: Sync, V: Sync> Sync for SkipMap<K, V> {}
impl<K, V> ops::Drop for SkipMap<K, V> {
#[inline]
fn drop(&mut self) {
unsafe {
let node: *mut SkipNode<K, V> = mem::transmute_copy(&self.head);
while let Some(ref mut next) = (*node).next {
mem::replace(&mut (*node).next, mem::replace(&mut next.next, None));
}
}
}
}
impl<K: Ord, V> default::Default for SkipMap<K, V> {
fn default() -> SkipMap<K, V> {
SkipMap::new()
}
}
impl<AK, AV, BK, BV> cmp::PartialEq<SkipMap<BK, BV>> for SkipMap<AK, AV>
where
AK: cmp::PartialEq<BK>,
AV: cmp::PartialEq<BV>,
{
#[inline]
fn eq(&self, other: &SkipMap<BK, BV>) -> bool {
self.len() == other.len()
&& self
.iter()
.zip(other.iter())
.all(|(x, y)| x.0 == y.0 && x.1 == y.1)
}
#[allow(clippy::partialeq_ne_impl)]
#[inline]
fn ne(&self, other: &SkipMap<BK, BV>) -> bool {
self.len() != other.len()
|| self
.iter()
.zip(other.iter())
.any(|(x, y)| x.0 != y.0 || x.1 != y.1)
}
}
impl<K, V> cmp::Eq for SkipMap<K, V>
where
K: cmp::Eq,
V: cmp::Eq,
{
}
impl<AK, AV, BK, BV> cmp::PartialOrd<SkipMap<BK, BV>> for SkipMap<AK, AV>
where
AK: cmp::PartialOrd<BK>,
AV: cmp::PartialOrd<BV>,
{
#[inline]
fn partial_cmp(&self, other: &SkipMap<BK, BV>) -> Option<Ordering> {
match self
.iter()
.map(|x| x.0)
.partial_cmp(other.iter().map(|x| x.0))
{
None => None,
Some(Ordering::Less) => Some(Ordering::Less),
Some(Ordering::Greater) => Some(Ordering::Greater),
Some(Ordering::Equal) => self
.iter()
.map(|x| x.1)
.partial_cmp(other.iter().map(|x| x.1)),
}
}
}
impl<K, V> Ord for SkipMap<K, V>
where
K: cmp::Ord,
V: cmp::Ord,
{
#[inline]
fn cmp(&self, other: &SkipMap<K, V>) -> Ordering {
self.iter().cmp(other)
}
}
impl<K, V> Extend<(K, V)> for SkipMap<K, V>
where
K: Ord,
{
#[inline]
fn extend<I: iter::IntoIterator<Item = (K, V)>>(&mut self, iterable: I) {
let iterator = iterable.into_iter();
for element in iterator {
self.insert(element.0, element.1);
}
}
}
impl<'a, K, V> ops::Index<usize> for SkipMap<K, V> {
type Output = V;
fn index(&self, index: usize) -> &V {
unsafe { (*self.get_index(index)).value.as_ref().unwrap() }
}
}
impl<'a, K, V> ops::IndexMut<usize> for SkipMap<K, V> {
fn index_mut(&mut self, index: usize) -> &mut V {
unsafe {
(*(self.get_index(index) as *mut SkipNode<K, V>))
.value
.as_mut()
.unwrap()
}
}
}
impl<K, V> fmt::Debug for SkipMap<K, V>
where
K: fmt::Debug,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "[")?;
for (i, (k, v)) in self.iter().enumerate() {
if i != 0 {
write!(f, ", ")?;
}
write!(f, "({:?}, {:?})", k, v)?;
}
write!(f, "]")
}
}
impl<K, V> fmt::Display for SkipMap<K, V>
where
K: fmt::Display,
V: fmt::Display,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "[")?;
for (i, (k, v)) in self.iter().enumerate() {
if i != 0 {
write!(f, ", ")?;
}
write!(f, "({}, {})", k, v)?;
}
write!(f, "]")
}
}
impl<K, V> iter::IntoIterator for SkipMap<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
fn into_iter(self) -> IntoIter<K, V> {
self.into_iter()
}
}
impl<'a, K, V> iter::IntoIterator for &'a SkipMap<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
}
}
impl<'a, K, V> iter::IntoIterator for &'a mut SkipMap<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
fn into_iter(self) -> IterMut<'a, K, V> {
self.iter_mut()
}
}
impl<K, V> iter::FromIterator<(K, V)> for SkipMap<K, V>
where
K: Ord,
{
#[inline]
fn from_iter<I>(iter: I) -> SkipMap<K, V>
where
I: iter::IntoIterator<Item = (K, V)>,
{
let mut skipmap = SkipMap::new();
skipmap.extend(iter);
skipmap
}
}
impl<K: Hash, V: Hash> Hash for SkipMap<K, V> {
#[inline]
fn hash<H: hash::Hasher>(&self, state: &mut H) {
for elt in self {
elt.hash(state);
}
}
}
pub struct Iter<'a, K: 'a, V: 'a> {
start: *const SkipNode<K, V>,
end: *const SkipNode<K, V>,
size: usize,
_lifetime_k: PhantomData<&'a K>,
_lifetime_v: PhantomData<&'a V>,
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<(&'a K, &'a V)> {
unsafe {
if self.start == self.end {
return None;
}
if let Some(next) = (*self.start).links[0] {
self.start = next;
if self.size > 0 {
self.size -= 1;
}
return Some((
(*self.start).key.as_ref().unwrap(),
(*self.start).value.as_ref().unwrap(),
));
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
unsafe {
if self.end == self.start {
return None;
}
if let Some(prev) = (*self.end).prev {
let node = self.end;
if prev as *const SkipNode<K, V> != self.start {
self.size -= 1;
} else {
self.size = 0;
}
self.end = prev;
if (*node).key.is_some() {
return Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_ref().unwrap(),
));
}
}
None
}
}
}
pub struct IterMut<'a, K: 'a, V: 'a> {
start: *mut SkipNode<K, V>,
end: *mut SkipNode<K, V>,
size: usize,
_lifetime_k: PhantomData<&'a K>,
_lifetime_v: PhantomData<&'a V>,
}
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
unsafe {
if self.start == self.end {
return None;
}
if let Some(next) = (*self.start).links[0] {
self.start = next;
self.size -= 1;
return Some((
(*self.start).key.as_ref().unwrap(),
(*self.start).value.as_mut().unwrap(),
));
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
unsafe {
if self.end == self.start {
return None;
}
if let Some(prev) = (*self.end).prev {
let node = self.end;
if prev as *const SkipNode<K, V> != self.start {
self.size -= 1;
} else {
self.size = 0;
}
self.end = prev;
if (*node).key.is_some() {
return Some((
(*node).key.as_ref().unwrap(),
(*node).value.as_mut().unwrap(),
));
}
}
None
}
}
}
pub struct IntoIter<K, V> {
skipmap: SkipMap<K, V>,
head: *mut SkipNode<K, V>,
end: *mut SkipNode<K, V>,
size: usize,
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<(K, V)> {
unsafe {
if let Some(next) = (*self.head).links[0] {
for lvl in 0..self.skipmap.level_generator.total() {
if lvl <= (*next).level {
(*self.head).links[lvl] = (*next).links[lvl];
(*self.head).links_len[lvl] = (*next).links_len[lvl] - 1;
} else {
(*self.head).links_len[lvl] -= 1;
}
}
if let Some(next) = (*self.head).links[0] {
(*next).prev = Some(self.head);
}
self.skipmap.len -= 1;
self.size -= 1;
mem::replace(
&mut (*self.head).next,
mem::replace(&mut (*next).next, None),
)
.unwrap()
.into_inner()
} else {
None
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
fn next_back(&mut self) -> Option<(K, V)> {
unsafe {
if self.head == self.end {
return None;
}
if let Some(prev) = (*self.end).prev {
if prev as *const SkipNode<K, V> != self.head {
self.size -= 1;
} else {
self.size = 0;
}
self.end = prev;
(*self.end).links[0] = None;
return mem::replace(&mut (*self.end).next, None)
.unwrap()
.into_inner();
}
None
}
}
}
pub struct Keys<'a, K: 'a, V> {
start: *const SkipNode<K, V>,
end: *const SkipNode<K, V>,
size: usize,
_lifetime_k: PhantomData<&'a K>,
}
impl<'a, K, V> Iterator for Keys<'a, K, V> {
type Item = &'a K;
fn next(&mut self) -> Option<&'a K> {
unsafe {
if self.start == self.end {
return None;
}
if let Some(next) = (*self.start).links[0] {
self.start = next;
if self.size > 0 {
self.size -= 1;
} else {
self.size = 0;
}
return (*self.start).key.as_ref();
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
fn next_back(&mut self) -> Option<&'a K> {
unsafe {
if self.end == self.start {
return None;
}
if let Some(prev) = (*self.end).prev {
let node = self.end;
if prev as *const SkipNode<K, V> != self.start {
self.size -= 1;
} else {
self.size = 0;
}
self.end = prev;
return (*node).key.as_ref();
}
None
}
}
}
pub struct Values<'a, K, V: 'a> {
start: *const SkipNode<K, V>,
end: *const SkipNode<K, V>,
size: usize,
_lifetime_v: PhantomData<&'a V>,
}
impl<'a, K, V> Iterator for Values<'a, K, V> {
type Item = &'a V;
fn next(&mut self) -> Option<&'a V> {
unsafe {
if self.start == self.end {
return None;
}
if let Some(next) = (*self.start).links[0] {
self.start = next;
if self.size > 0 {
self.size -= 1;
}
return (*self.start).value.as_ref();
}
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
fn next_back(&mut self) -> Option<&'a V> {
unsafe {
if self.end == self.start {
return None;
}
if let Some(prev) = (*self.end).prev {
let node = self.end;
if prev as *const SkipNode<K, V> != self.start {
self.size -= 1;
} else {
self.size = 0;
}
self.end = prev;
return (*node).value.as_ref();
}
None
}
}
}
#[cfg(test)]
mod tests {
use super::SkipMap;
use std::collections::Bound::{self, Excluded, Included, Unbounded};
#[test]
fn basic_small() {
let mut sm: SkipMap<i64, i64> = SkipMap::new();
sm.check();
assert!(sm.remove(&1).is_none());
sm.check();
assert!(sm.insert(1, 0).is_none());
sm.check();
assert_eq!(sm.insert(1, 5), Some(0));
sm.check();
assert_eq!(sm.remove(&1), Some(5));
sm.check();
assert!(sm.insert(1, 10).is_none());
sm.check();
assert!(sm.insert(2, 20).is_none());
sm.check();
assert_eq!(sm.remove(&1), Some(10));
sm.check();
assert_eq!(sm.remove(&2), Some(20));
sm.check();
assert!(sm.remove(&1).is_none());
sm.check();
}
#[test]
fn basic_large() {
let size = 10_000;
let mut sm = SkipMap::with_capacity(size);
assert!(sm.is_empty());
for i in 0..size {
sm.insert(i, i * 10);
assert_eq!(sm.len(), i + 1);
}
sm.check();
for i in 0..size {
assert_eq!(sm.remove(&i), Some(i * 10));
assert_eq!(sm.len(), size - i - 1);
}
sm.check();
}
#[test]
fn insert_existing() {
let size = 100;
let mut sm = SkipMap::new();
for i in 0..size {
assert!(sm.insert(i, format!("{}", i)).is_none());
}
for i in 0..size {
assert_eq!(sm.insert(i, format!("{}", i)), Some(format!("{}", i)));
}
for i in (0..size).rev() {
assert_eq!(sm.insert(i, format!("{}", i)), Some(format!("{}", i)));
}
}
#[test]
fn clear() {
let mut sm: SkipMap<_, _> = (0..100).map(|x| (x, x)).collect();
assert_eq!(sm.len(), 100);
sm.clear();
sm.check();
assert!(sm.is_empty());
}
#[test]
fn iter() {
let size = 10000;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
fn test<T>(size: usize, mut iter: T)
where
T: Iterator<Item = (usize, usize)>,
{
for i in 0..size {
assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
assert_eq!(iter.next().unwrap(), (i, i));
}
assert_eq!(iter.size_hint(), (0, Some(0)));
assert!(iter.next().is_none());
}
test(size, sm.iter().map(|(&a, &b)| (a, b)));
test(size, sm.iter_mut().map(|(&a, &mut b)| (a, b)));
test(size, sm.into_iter());
}
#[test]
fn iter_rev() {
let size = 1000;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
fn test<T>(size: usize, mut iter: T)
where
T: Iterator<Item = (usize, usize)>,
{
for i in 0..size {
assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
}
assert_eq!(iter.size_hint(), (0, Some(0)));
assert!(iter.next().is_none());
}
test(size, sm.iter().rev().map(|(&a, &b)| (a, b)));
test(size, sm.iter_mut().rev().map(|(&a, &mut b)| (a, b)));
test(size, sm.into_iter().rev());
}
#[test]
fn iter_mixed() {
let size = 1000;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
fn test<T>(size: usize, mut iter: T)
where
T: Iterator<Item = (usize, usize)> + DoubleEndedIterator,
{
for i in 0..size / 4 {
assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
assert_eq!(iter.next().unwrap(), (i, i));
assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
}
for i in size / 4..size * 3 / 4 {
assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
assert_eq!(iter.next().unwrap(), (i, i));
}
assert_eq!(iter.size_hint(), (0, Some(0)));
assert!(iter.next().is_none());
}
test(size, sm.iter().map(|(&a, &b)| (a, b)));
test(size, sm.iter_mut().map(|(&a, &mut b)| (a, b)));
test(size, sm.into_iter());
}
#[test]
fn iter_key_val() {
let size = 1000;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, 2 * x)).collect();
let mut keys = sm.keys();
for i in 0..size / 2 {
assert_eq!(keys.next(), Some(&i));
}
for i in 0..size / 2 {
assert_eq!(keys.next_back(), Some(&(size - i - 1)))
}
assert!(keys.next().is_none());
let mut vals = sm.values();
for i in 0..size / 2 {
assert_eq!(vals.next(), Some(&(2 * i)));
}
for i in 0..size / 2 {
assert_eq!(vals.next_back(), Some(&(2 * (size - i) - 2)))
}
assert!(vals.next().is_none());
}
#[test]
fn range_small() {
let size = 5;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
let mut j = 0;
for ((&k, &v), i) in sm.range(Included(&2), Unbounded).zip(2..size) {
assert_eq!(k, i);
assert_eq!(v, i);
j += 1;
}
assert_eq!(j, size - 2);
}
#[test]
fn range_1000() {
let size = 1000;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
fn test(sm: &SkipMap<usize, usize>, min: Bound<&usize>, max: Bound<&usize>) {
let mut values = sm.range(min, max);
#[allow(clippy::range_plus_one)]
let mut expects = match (min, max) {
(Excluded(&a), Excluded(&b)) => (a + 1)..b,
(Included(&a), Excluded(&b)) => a..b,
(Unbounded, Excluded(&b)) => 0..b,
(Excluded(&a), Included(&b)) => (a + 1)..(b + 1),
(Included(&a), Included(&b)) => a..(b + 1),
(Unbounded, Included(&b)) => 0..(b + 1),
(Excluded(&a), Unbounded) => (a + 1)..1000,
(Included(&a), Unbounded) => a..1000,
(Unbounded, Unbounded) => 0..1000,
};
for ((&k, &v), e) in values.by_ref().zip(expects.by_ref()) {
assert_eq!(k, e);
assert_eq!(v, e);
}
assert!(values.next().is_none());
assert!(expects.next().is_none());
}
test(&sm, Excluded(&200), Excluded(&800));
test(&sm, Included(&200), Excluded(&800));
test(&sm, Unbounded, Excluded(&800));
test(&sm, Excluded(&200), Included(&800));
test(&sm, Included(&200), Included(&800));
test(&sm, Unbounded, Included(&800));
test(&sm, Excluded(&200), Unbounded);
test(&sm, Included(&200), Unbounded);
test(&sm, Unbounded, Unbounded);
}
#[test]
fn range() {
let size = 200;
let sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
for i in 0..size {
for j in 0..size {
let mut values = sm.range(Included(&i), Included(&j)).map(|(&a, &b)| (a, b));
let mut expects = i..=j;
for ((k, v), e) in values.by_ref().zip(expects.by_ref()) {
assert_eq!(k, e);
assert_eq!(v, e);
}
assert!(values.next().is_none());
assert!(expects.next().is_none());
}
}
}
#[test]
fn index_pop() {
let size = 1000;
let mut sm: SkipMap<_, _> = (0..size).map(|x| (x, 2 * x)).collect();
assert_eq!(sm.front(), Some((&0, &0)));
assert_eq!(sm.front_mut(), Some((&0, &mut 0)));
assert_eq!(sm.back(), Some((&(size - 1), &(2 * size - 2))));
assert_eq!(sm.back_mut(), Some((&(size - 1), &mut (2 * size - 2))));
for i in 0..size {
assert_eq!(sm[i], 2 * i);
assert_eq!(sm.get(&i), Some(&(2 * i)));
assert_eq!(sm.get_mut(&i), Some(&mut (2 * i)));
}
let mut sm: SkipMap<_, _> = (0..size).map(|x| (x, 2 * x)).collect();
for i in 0..size {
assert_eq!(sm.pop_front(), Some((i, 2 * i)));
assert_eq!(sm.len(), size - i - 1);
}
assert!(sm.pop_front().is_none());
assert!(sm.front().is_none());
assert!(sm.is_empty());
let mut sm: SkipMap<_, _> = (0..size).map(|x| (x, 2 * x)).collect();
for i in 0..size {
assert_eq!(sm.pop_back(), Some((size - i - 1, 2 * (size - i - 1))));
assert_eq!(sm.len(), size - i - 1);
}
assert!(sm.pop_back().is_none());
assert!(sm.back().is_none());
assert!(sm.is_empty());
}
#[test]
fn remove_index() {
let size = 100;
for i in 0..size {
let mut sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
assert_eq!(sm.remove_index(i), (i, i));
assert_eq!(sm.len(), size - 1);
}
let mut sm: SkipMap<_, _> = (0..size).map(|x| (x, x)).collect();
for i in 0..size {
assert_eq!(sm.remove_index(0), (i, i));
assert_eq!(sm.len(), size - i - 1);
sm.check();
}
assert!(sm.is_empty());
}
#[test]
fn contains() {
let (min, max) = (25, 75);
let sm: SkipMap<_, _> = (min..max).map(|x| (x, x)).collect();
for i in 0..100 {
println!("i = {} (contained: {})", i, sm.contains_key(&i));
if i < min || i >= max {
assert!(!sm.contains_key(&i));
} else {
assert!(sm.contains_key(&i));
}
}
}
#[test]
fn debug_display() {
let sl: SkipMap<_, _> = (0..10).map(|x| (x, x)).collect();
sl.debug_structure();
println!("{:?}", sl);
println!("{}", sl);
}
#[test]
fn equality() {
let a: SkipMap<i64, i64> = (0..100).map(|x| (x, x)).collect();
let b: SkipMap<i64, i64> = (0..100).map(|x| (x, x)).collect();
let c: SkipMap<i64, i64> = (0..10).map(|x| (x, x)).collect();
let d: SkipMap<i64, i64> = (100..200).map(|x| (x, x)).collect();
let e: SkipMap<i64, i64> = (0..100).chain(0..1).map(|x| (x, x)).collect();
assert_eq!(a, a);
assert_eq!(a, b);
assert_ne!(a, c);
assert_ne!(a, d);
assert_eq!(a, e);
assert_eq!(b, b);
assert_ne!(b, c);
assert_ne!(b, d);
assert_eq!(b, e);
assert_eq!(c, c);
assert_ne!(c, d);
assert_ne!(c, e);
assert_eq!(d, d);
assert_ne!(d, e);
assert_eq!(e, e);
}
}