use std::{ ptr, mem, str, slice, fmt };
use std::ops::{ Index, IndexMut, Deref };
use std::iter::FromIterator;
use crate::codegen::{ DumpGenerator, Generator, PrettyGenerator };
use crate::value::JsonValue;
const KEY_BUF_LEN: usize = 32;
static NULL: JsonValue = JsonValue::Null;
#[inline]
fn hash_key(key: &[u8]) -> u64 {
let mut hash: u64 = 0xcbf29ce484222325;
for byte in key {
hash ^= *byte as u64;
hash = hash.wrapping_mul(0x100000001b3);
}
hash
}
struct Key {
pub buf: [u8; KEY_BUF_LEN],
pub len: usize,
pub ptr: *mut u8,
pub hash: u64,
}
impl Key {
#[inline]
fn new(hash: u64, len: usize) -> Self {
Key {
buf: [0; KEY_BUF_LEN],
len: len,
ptr: ptr::null_mut(),
hash: hash
}
}
#[inline]
fn as_bytes(&self) -> &[u8] {
unsafe {
slice::from_raw_parts(self.ptr, self.len)
}
}
#[inline]
fn as_str(&self) -> &str {
unsafe {
str::from_utf8_unchecked(self.as_bytes())
}
}
#[inline]
fn attach(&mut self, key: &[u8]) {
if self.len <= KEY_BUF_LEN {
unsafe {
ptr::copy_nonoverlapping(
key.as_ptr(),
self.buf.as_mut_ptr(),
self.len
);
}
self.ptr = self.buf.as_mut_ptr();
} else {
let mut heap = key.to_vec();
self.ptr = heap.as_mut_ptr();
mem::forget(heap);
}
}
#[inline]
fn fix_ptr(&mut self) {
if self.len <= KEY_BUF_LEN {
self.ptr = self.buf.as_mut_ptr();
}
}
}
unsafe impl Sync for Key {}
unsafe impl Send for Key {}
impl Drop for Key {
fn drop(&mut self) {
unsafe {
if self.len > KEY_BUF_LEN {
let heap = Vec::from_raw_parts(
self.ptr,
self.len,
self.len
);
drop(heap);
}
}
}
}
impl Clone for Key {
fn clone(&self) -> Self {
if self.len > KEY_BUF_LEN {
let mut heap = self.as_bytes().to_vec();
let ptr = heap.as_mut_ptr();
mem::forget(heap);
Key {
buf: [0; KEY_BUF_LEN],
len: self.len,
ptr: ptr,
hash: self.hash,
}
} else {
Key {
buf: self.buf,
len: self.len,
ptr: ptr::null_mut(),
hash: self.hash,
}
}
}
}
#[derive(Clone)]
struct Node {
pub key: Key,
pub value: JsonValue,
pub left: usize,
pub right: usize,
}
impl fmt::Debug for Node {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Debug::fmt(&(self.key.as_str(), &self.value, self.left, self.right), f)
}
}
impl PartialEq for Node {
fn eq(&self, other: &Node) -> bool {
self.key.hash == other.key.hash &&
self.key.as_bytes() == other.key.as_bytes() &&
self.value == other.value
}
}
impl Node {
#[inline]
fn new(value: JsonValue, hash: u64, len: usize) -> Node {
Node {
key: Key::new(hash, len),
value: value,
left: 0,
right: 0,
}
}
}
#[derive(Debug)]
pub struct Object {
store: Vec<Node>
}
impl Object {
#[inline(always)]
pub fn new() -> Self {
Object {
store: Vec::new()
}
}
#[inline(always)]
pub fn with_capacity(capacity: usize) -> Self {
Object {
store: Vec::with_capacity(capacity)
}
}
#[inline]
fn node_at_index_mut(&mut self, index: usize) -> *mut Node {
unsafe { self.store.as_mut_ptr().offset(index as isize) }
}
#[inline(always)]
fn add_node(&mut self, key: &[u8], value: JsonValue, hash: u64) -> usize {
let index = self.store.len();
if index < self.store.capacity() {
unsafe {
let node = Node::new(value, hash, key.len());
self.store.set_len(index + 1);
ptr::copy_nonoverlapping(
&node as *const Node,
self.store.as_mut_ptr().offset(index as isize),
1,
);
mem::forget(node);
}
unsafe { self.store.get_unchecked_mut(index).key.attach(key) };
} else {
self.store.push(Node::new(value, hash, key.len()));
unsafe { self.store.get_unchecked_mut(index).key.attach(key) };
for node in self.store.iter_mut().take(index) {
node.key.fix_ptr();
}
}
index
}
#[inline]
pub fn insert(&mut self, key: &str, value: JsonValue) {
self.insert_index(key, value);
}
pub(crate) fn insert_index(&mut self, key: &str, value: JsonValue) -> usize {
let key = key.as_bytes();
let hash = hash_key(key);
if self.store.len() == 0 {
self.store.push(Node::new(value, hash, key.len()));
self.store[0].key.attach(key);
return 0;
}
let mut node = unsafe { &mut *self.node_at_index_mut(0) };
let mut parent = 0;
loop {
if hash == node.key.hash && key == node.key.as_bytes() {
node.value = value;
return parent;
} else if hash < node.key.hash {
if node.left != 0 {
parent = node.left;
node = unsafe { &mut *self.node_at_index_mut(node.left) };
continue;
}
let index = self.add_node(key, value, hash);
self.store[parent].left = index;
return index;
} else {
if node.right != 0 {
parent = node.right;
node = unsafe { &mut *self.node_at_index_mut(node.right) };
continue;
}
let index = self.add_node(key, value, hash);
self.store[parent].right = index;
return index;
}
}
}
#[inline]
pub(crate) fn override_at(&mut self, index: usize, value: JsonValue) {
self.store[index].value = value;
}
#[inline]
#[deprecated(since="0.11.11", note="Was only meant for internal use")]
pub fn override_last(&mut self, value: JsonValue) {
if let Some(node) = self.store.last_mut() {
node.value = value;
}
}
pub fn get(&self, key: &str) -> Option<&JsonValue> {
if self.store.len() == 0 {
return None;
}
let key = key.as_bytes();
let hash = hash_key(key);
let mut node = unsafe { self.store.get_unchecked(0) };
loop {
if hash == node.key.hash && key == node.key.as_bytes() {
return Some(&node.value);
} else if hash < node.key.hash {
if node.left == 0 {
return None;
}
node = unsafe { self.store.get_unchecked(node.left) };
} else {
if node.right == 0 {
return None;
}
node = unsafe { self.store.get_unchecked(node.right) };
}
}
}
pub fn get_mut(&mut self, key: &str) -> Option<&mut JsonValue> {
if self.store.len() == 0 {
return None;
}
let key = key.as_bytes();
let hash = hash_key(key);
let mut index = 0;
{
let mut node = unsafe { self.store.get_unchecked(0) };
loop {
if hash == node.key.hash && key == node.key.as_bytes() {
break;
} else if hash < node.key.hash {
if node.left == 0 {
return None;
}
index = node.left;
node = unsafe { self.store.get_unchecked(node.left) };
} else {
if node.right == 0 {
return None;
}
index = node.right;
node = unsafe { self.store.get_unchecked(node.right) };
}
}
}
let node = unsafe { self.store.get_unchecked_mut(index) };
Some(&mut node.value)
}
pub fn remove(&mut self, key: &str) -> Option<JsonValue> {
if self.store.len() == 0 {
return None;
}
let key = key.as_bytes();
let hash = hash_key(key);
let mut index = 0;
{
let mut node = unsafe { self.store.get_unchecked(0) };
loop {
if hash == node.key.hash && key == node.key.as_bytes() {
break;
} else if hash < node.key.hash {
if node.left == 0 {
return None;
}
index = node.left;
node = unsafe { self.store.get_unchecked(node.left) };
} else {
if node.right == 0 {
return None;
}
index = node.right;
node = unsafe { self.store.get_unchecked(node.right) };
}
}
}
let mut new_object = Object::with_capacity(self.store.len() - 1);
let mut removed = None;
for (i, node) in self.store.iter_mut().enumerate() {
if i == index {
removed = Some(mem::replace(&mut node.value, JsonValue::Null));
} else {
let value = mem::replace(&mut node.value, JsonValue::Null);
new_object.insert(node.key.as_str(), value);
}
}
mem::swap(self, &mut new_object);
removed
}
#[inline(always)]
pub fn len(&self) -> usize {
self.store.len()
}
#[inline(always)]
pub fn is_empty(&self) -> bool {
self.store.is_empty()
}
pub fn clear(&mut self) {
self.store.clear();
}
#[inline(always)]
pub fn iter(&self) -> Iter {
Iter {
inner: self.store.iter()
}
}
#[inline(always)]
pub fn iter_mut(&mut self) -> IterMut {
IterMut {
inner: self.store.iter_mut()
}
}
pub fn dump(&self) -> String {
let mut gen = DumpGenerator::new();
gen.write_object(self).expect("Can't fail");
gen.consume()
}
pub fn pretty(&self, spaces: u16) -> String {
let mut gen = PrettyGenerator::new(spaces);
gen.write_object(self).expect("Can't fail");
gen.consume()
}
}
impl Clone for Object {
fn clone(&self) -> Self {
let mut store = self.store.clone();
for node in store.iter_mut() {
node.key.fix_ptr();
}
Object {
store: store
}
}
}
impl<K: AsRef<str>, V: Into<JsonValue>> FromIterator<(K, V)> for Object {
fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self {
let iter = iter.into_iter();
let mut object = Object::with_capacity(iter.size_hint().0);
for (key, value) in iter {
object.insert(key.as_ref(), value.into());
}
object
}
}
impl PartialEq for Object {
fn eq(&self, other: &Object) -> bool {
if self.len() != other.len() {
return false;
}
for (key, value) in self.iter() {
match other.get(key) {
Some(ref other_val) => if *other_val != value { return false; },
None => return false
}
}
true
}
}
pub struct Iter<'a> {
inner: slice::Iter<'a, Node>
}
impl<'a> Iter<'a> {
pub fn empty() -> Self {
Iter {
inner: [].iter()
}
}
}
impl<'a> Iterator for Iter<'a> {
type Item = (&'a str, &'a JsonValue);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|node| (node.key.as_str(), &node.value))
}
}
impl<'a> DoubleEndedIterator for Iter<'a> {
#[inline(always)]
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back().map(|node| (node.key.as_str(), &node.value))
}
}
impl<'a> ExactSizeIterator for Iter<'a> {
fn len(&self) -> usize {
self.inner.len()
}
}
pub struct IterMut<'a> {
inner: slice::IterMut<'a, Node>
}
impl<'a> IterMut<'a> {
pub fn empty() -> Self {
IterMut {
inner: [].iter_mut()
}
}
}
impl<'a> Iterator for IterMut<'a> {
type Item = (&'a str, &'a mut JsonValue);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|node| (node.key.as_str(), &mut node.value))
}
}
impl<'a> DoubleEndedIterator for IterMut<'a> {
#[inline(always)]
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back().map(|node| (node.key.as_str(), &mut node.value))
}
}
impl<'a> ExactSizeIterator for IterMut<'a> {
fn len(&self) -> usize {
self.inner.len()
}
}
impl<'a> Index<&'a str> for Object {
type Output = JsonValue;
fn index(&self, index: &str) -> &JsonValue {
match self.get(index) {
Some(value) => value,
_ => &NULL
}
}
}
impl Index<String> for Object {
type Output = JsonValue;
fn index(&self, index: String) -> &JsonValue {
self.index(index.deref())
}
}
impl<'a> Index<&'a String> for Object {
type Output = JsonValue;
fn index(&self, index: &String) -> &JsonValue {
self.index(index.deref())
}
}
impl<'a> IndexMut<&'a str> for Object {
fn index_mut(&mut self, index: &str) -> &mut JsonValue {
if self.get(index).is_none() {
self.insert(index, JsonValue::Null);
}
self.get_mut(index).unwrap()
}
}
impl IndexMut<String> for Object {
fn index_mut(&mut self, index: String) -> &mut JsonValue {
self.index_mut(index.deref())
}
}
impl<'a> IndexMut<&'a String> for Object {
fn index_mut(&mut self, index: &String) -> &mut JsonValue {
self.index_mut(index.deref())
}
}