<commit_before>/*
 * Copyright 2015 - 2017 <EMAIL>
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */
#pragma once

#include <ox/std/std.hpp>

namespace ox {
namespace fs {

template<typename FsT>
class FileStore {

	public:
		typedef uint16_t InodeId_t;
		typedef FsT FsSize_t;
		const static auto VERSION = 2;

		struct StatInfo {
			InodeId_t inodeId;
			FsSize_t  size;
			uint8_t fileType;
		};

	private:
		struct Inode {
			// the next Inode in memory
			FsSize_t prev, next;
			FsSize_t dataLen;
			InodeId_t id;
			uint8_t refs;
			uint8_t fileType;
			FsSize_t left, right;

			FsSize_t size();
			void setId(InodeId_t);
			void setData(void *data, FsSize_t size);
			void *data();
		};

		uint16_t m_version;
		uint16_t m_fsType;
		FsSize_t m_size;
		FsSize_t m_memUsed;
		FsSize_t m_rootInode;

	public:
		/**
		 * Dumps this file store's inodes to the given file store.
		 */
		int dumpTo(FileStore<FsSize_t> *dest);

		/**
		 * Compacts and resizes the file store to the minimum possible size for
		 * the contents.
		 *
		 * NOTE: This does NOT resize the buffer that this file store refers to!
		 */
		void resize(FsSize_t size = 0);

		/**
		 * Writes the given data to a "file" with the given id.
		 * @param id the id of the file
		 * @param data the contents of the file
		 * @param dataLen the number of bytes data points to
		 */
		int write(InodeId_t id, void *data, FsSize_t dataLen, uint8_t fileType = 0);

		/**
		 * Removes the inode of the given ID.
		 * @param id the id of the file
		 */
		int remove(InodeId_t id);

		/**
		 * Reads the "file" at the given id. You are responsible for freeing
		 * the data when done with it.
		 * @param id id of the "file"
		 * @param data pointer to the pointer where the data is stored
		 * @param size pointer to a value that will be assigned the size of data
		 * @return 0 if read is a success
		 */
		int read(InodeId_t id, void *data, FsSize_t *size);

		/**
		 * Reads the stat information of the inode of the given inode id.
		 * If the returned inode id is 0, then the requested inode was not found.
		 * @param id id of the inode to stat
		 * @return the stat information of the inode of the given inode id
		 */
		StatInfo stat(InodeId_t id);

		/**
		 * Returns the space needed for this data at the given inode address.
		 * @param id the target inode id
		 * @param size the size of the data to insert
		 * @return the space currently available in this file store.
		 */
		FsSize_t spaceNeeded(InodeId_t id, FsSize_t size);

		/**
		 * Returns the size of the file store.
		 * @return the size of the file store.
		 */
		FsSize_t size();

		/**
		 * Returns the space currently available in this file store.
		 * @return the space currently available in this file store.
		 */
		FsSize_t available();

		uint16_t fsType();

		uint16_t version();
		
		static uint8_t *format(uint8_t *buffer, FsSize_t size, uint16_t fsType = 0);

	private:
		/**
		 * Gets the inode at the given id.
		 * @param root the root node to start comparing on
		 * @param id id of the "file"
		 * @param pathLen number of characters in pathLen
		 * @return the requested Inode, if available
		 */
		Inode *getInode(Inode *root, InodeId_t id);

		/**
		 * Gets the inode at the given id.
		 * @param root the root node to start comparing on
		 * @param id id of the "file"
		 * @param pathLen number of characters in pathLen
		 * @param targetAddr the address of the target inode
		 * @return the requested Inode, if available
		 */
		Inode *getInodeParent(Inode *root, InodeId_t id, FsSize_t targetAddr);

		/**
		 * Removes the inode of the given ID.
		 * @param id the id of the file
		 */
		int remove(Inode *root, InodeId_t id);

		/**
		 * Removes the given node from the linked list.
		 * @param node node to remove
		 */
		void dealloc(Inode *node);

		/**
		 * Gets the address of the next available inode, assuming there is a next
		 * available inode.
		 */
		FsSize_t nextInodeAddr();

		/**
		 * Gets an address for a new Inode.
		 * @param size the size of the Inode
		 */
		void *alloc(FsSize_t size);

		/**
		 * Compacts all of the inodes into a contiguous space, starting at the first inode.
		 */
		void compact();

		/**
		 * Inserts the given insertValue into the tree of the given root.
		 * If the inode already exists, it replaces the old on deletes it.
		 * @return true if the inode was inserted
		 */
		bool insert(Inode *root, Inode *insertValue);

		/**
		 * Gets the FsSize_t associated with the next Inode to be allocated.
		 * @retrun the FsSize_t associated with the next Inode to be allocated
		 */
		FsSize_t iterator();

		FsSize_t firstInode();

		Inode *lastInode();

		/**
		 * Updates the address of the inode in the tree.
		 */
		void updateInodeAddress(InodeId_t id, FsSize_t oldAddr, FsSize_t newAddr);

		uint8_t *begin() {
			return (uint8_t*) this;
		}

		uint8_t *end() {
			return begin() + this->m_size;
		}

		/**
		 * Converts an actual pointer to a FsSize_t.
		 */
		FsSize_t ptr(void *ptr);

		/**
		 * Converts a FsSize_t to an actual pointer.
		 */
		template<typename T>
		T ptr(FsSize_t ptr) {
			return (T) (begin() + ptr);
		};

};

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::Inode::size() {
	return sizeof(Inode) + dataLen;
}

template<typename FsSize_t>
void FileStore<FsSize_t>::Inode::setId(InodeId_t id) {
	this->id = id;
}

template<typename FsSize_t>
void FileStore<FsSize_t>::Inode::setData(void *data, FsSize_t size) {
	ox_memcpy(this->data(), data, size);
	dataLen = size;
}


template<typename FsSize_t>
void *FileStore<FsSize_t>::Inode::data() {
	return this + 1;
}


// FileStore

template<typename FsSize_t>
int FileStore<FsSize_t>::dumpTo(FileStore<FsSize_t> *dest) {
	if (dest->size() >= size()) {
		auto i = ptr<Inode*>(firstInode());
		do {
			dest->write(i->id, i->data(), i->dataLen, i->fileType);
			i = ptr<Inode*>(i->next);
		} while (ptr(i) != firstInode());
		return 0;
	} else {
		return -1;
	}
}

template<typename FsSize_t>
void FileStore<FsSize_t>::resize(FsSize_t size) {
	if (size < m_size) {
		// shrink file store
		if (m_memUsed > size) {
			size = m_memUsed;
		}
		compact();
		m_size = size;
	} else if (size > m_size) {
		// grow file store
		m_size = size;
	}
}

template<typename FsSize_t>
int FileStore<FsSize_t>::write(InodeId_t id, void *data, FsSize_t dataLen, uint8_t fileType) {
	auto retval = 1;
	const FsSize_t size = sizeof(Inode) + dataLen;
	if (size <= (m_size - m_memUsed)) {
		auto inode = (Inode*) alloc(size);
		if (inode) {
			remove(id);
			inode->id = id;
			inode->fileType = fileType;
			inode->setData(data, dataLen);
			auto root = ptr<Inode*>(m_rootInode);
			if (insert(root, inode) || root == inode) {
				retval = 0;
			}
		}
	}
	return retval;
}

template<typename FsSize_t>
int FileStore<FsSize_t>::remove(InodeId_t id) {
	return remove(ptr<Inode*>(m_rootInode), id);
}

template<typename FsSize_t>
int FileStore<FsSize_t>::remove(Inode *root, InodeId_t id) {
	auto err = 1;

	if (root->id > id) {
		if (root->left) {
			auto node = ptr<Inode*>(root->left);
			if (node->id != id) {
				err = remove(node, id);
			} else {
				root->left = 0;
				if (node->right) {
					insert(root, ptr<Inode*>(node->right));
				}
				if (node->left) {
					insert(root, ptr<Inode*>(node->left));
				}
				dealloc(node);
				node->id = 0;
				node->left = 0;
				node->right = 0;
				err = 0;
			}
		}
	} else if (root->id < id) {
		if (root->right) {
			auto node = ptr<Inode*>(root->right);
			if (node->id != id) {
				err = remove(node, id);
			} else {
				root->right = 0;
				if (node->right) {
					insert(root, ptr<Inode*>(node->right));
				}
				if (node->left) {
					insert(root, ptr<Inode*>(node->left));
				}
				dealloc(node);
				node->id = 0;
				node->left = 0;
				node->right = 0;
				err = 0;
			}
		}
	} else if (ptr<Inode*>(m_rootInode)->id == id) {
		m_rootInode = root->right;
		if (root->left) {
			insert(ptr<Inode*>(m_rootInode), ptr<Inode*>(root->left));
		}
		dealloc(root);
		root->id = 0;
		root->left = 0;
		root->right = 0;
		err = 0;
	}

	return err;
}

template<typename FsSize_t>
void FileStore<FsSize_t>::dealloc(Inode *inode) {
	auto next = ptr<Inode*>(inode->next);
	auto prev = ptr<Inode*>(inode->prev);
	prev->next = ptr(next);
	next->prev = ptr(prev);

	m_memUsed -= inode->size();

	ox_memset(inode, 0, inode->size());
}

template<typename FsSize_t>
void FileStore<FsSize_t>::updateInodeAddress(InodeId_t id, FsSize_t oldAddr, FsSize_t newAddr) {
	auto parent = getInodeParent(ptr<Inode*>(m_rootInode), id, oldAddr);
	if (parent) {
		if (parent->left == oldAddr) {
			parent->left = newAddr;
		} else if (parent->right == oldAddr) {
			parent->right = newAddr;
		}
	}
}

template<typename FsSize_t>
int FileStore<FsSize_t>::read(InodeId_t id, void *data, FsSize_t *size) {
	auto inode = getInode(ptr<Inode*>(m_rootInode), id);
	int retval = 1;
	if (inode) {
		if (size) {
			*size = inode->dataLen;
		}
		ox_memcpy(data, inode->data(), inode->dataLen);
		retval = 0;
	}
	return retval;
}

template<typename FsSize_t>
typename FileStore<FsSize_t>::StatInfo FileStore<FsSize_t>::stat(InodeId_t id) {
	auto inode = getInode(ptr<Inode*>(m_rootInode), id);
	StatInfo stat;
	if (inode) {
		stat.size = inode->dataLen;
		stat.fileType = inode->fileType;
		stat.inodeId = id;
	} else {
		stat.inodeId = 0;
	}
	return stat;
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::spaceNeeded(InodeId_t id, FsSize_t size) {
	FsSize_t needed = sizeof(Inode) + size;;
	auto inode = getInode(ptr<Inode*>(m_rootInode), id);
	if (inode) {
		needed -= inode->size();
	}
	return needed;
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::size() {
	return m_size;
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::available() {
	return m_size - m_memUsed;
}

template<typename FsSize_t>
typename FileStore<FsSize_t>::Inode *FileStore<FsSize_t>::getInode(Inode *root, InodeId_t id) {
	Inode *retval = nullptr;

	if (root->id > id) {
		if (root->left) {
			retval = getInode(ptr<Inode*>(root->left), id);
		}
	} else if (root->id < id) {
		if (root->right) {
			retval = getInode(ptr<Inode*>(root->right), id);
		}
	} else if (root->id == id) {
		retval = root;
	}

	return retval;
}

template<typename FsSize_t>
typename FileStore<FsSize_t>::Inode *FileStore<FsSize_t>::getInodeParent(Inode *root, InodeId_t id, FsSize_t targetAddr) {
	Inode *retval = nullptr;

	if (root->id > id) {
		if (root->left) {
			if (root->left == targetAddr) {
				retval = root;
			} else {
				retval = getInodeParent(ptr<Inode*>(root->left), id, targetAddr);
			}
		}
	} else if (root->id < id) {
		if (root->right) {
			if (root->right == targetAddr) {
				retval = root;
			} else {
				retval = getInodeParent(ptr<Inode*>(root->right), id, targetAddr);
			}
		}
	}

	return retval;
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::nextInodeAddr() {
	FsSize_t next = ptr(lastInode()) + lastInode()->size();
	return next;
}

template<typename FsSize_t>
void *FileStore<FsSize_t>::alloc(FsSize_t size) {
	FsSize_t next = nextInodeAddr();
	if ((next + size) > (uint64_t) end()) {
		compact();
		next = nextInodeAddr();
		if ((next + size) > (uint64_t) end()) {
			return nullptr;
		}
	}

	const auto retval = next;
	const auto inode = ptr<Inode*>(retval);
	ox_memset(inode, 0, size);
	inode->prev = ptr<Inode*>(firstInode())->prev;
	inode->next = retval + size;
	m_memUsed += size;
	ptr<Inode*>(firstInode())->prev = retval;
	return inode;
}

template<typename FsSize_t>
void FileStore<FsSize_t>::compact() {
	auto dest = ptr<Inode*>(firstInode());
	auto current = ptr<Inode*>(firstInode());
	while (current->next > firstInode() && current->next < ptr(end())) {
		ox_memcpy(dest, current, current->size());
		if (dest->next != firstInode()) {
			dest->next = ptr(dest) + dest->size();
		}
		ptr<Inode*>(dest->next)->prev = ptr(dest);
		updateInodeAddress(dest->id, ptr(current), ptr(dest));
		current = ptr<Inode*>(dest->next);
		dest = ptr<Inode*>(ptr(dest) + dest->size());
	}
}

template<typename FsSize_t>
bool FileStore<FsSize_t>::insert(Inode *root, Inode *insertValue) {
	auto retval = false;

	if (root->id > insertValue->id) {
		if (root->left) {
			retval = insert(ptr<Inode*>(root->left), insertValue);
		} else {
			root->left = ptr(insertValue);
			retval = true;
		}
	} else if (root->id < insertValue->id) {
		if (root->right) {
			retval = insert(ptr<Inode*>(root->right), insertValue);
		} else {
			root->right = ptr(insertValue);
			retval = true;
		}
	} else if (m_rootInode == 0) {
		m_rootInode = ptr(insertValue);
		retval = true;
	}

	return retval;
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::iterator() {
	return ptr(lastInode()) + lastInode()->size();
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::ptr(void *ptr) {
#ifdef _MSC_VER
#pragma warning(disable:4244)
#endif
	return ((uint8_t*) ptr) - begin();
#ifdef _MSC_VER
#pragma warning(default:4244)
#endif
}

template<typename FsSize_t>
FsSize_t FileStore<FsSize_t>::firstInode() {
	return sizeof(FileStore<FsSize_t>);
}

template<typename FsSize_t>
typename FileStore<FsSize_t>::Inode *FileStore<FsSize_t>::lastInode() {
	return ptr<Inode*>(ptr<Inode*>(firstInode())->prev);
}

template<typename FsSize_t>
uint16_t FileStore<FsSize_t>::fsType() {
	return m_fsType;
};

template<typename FsSize_t>
uint16_t FileStore<FsSize_t>::version() {
	return m_version;
};

template<typename FsSize_t>
uint8_t *FileStore<FsSize_t>::format(uint8_t *buffer, FsSize_t size, uint16_t fsType) {
	ox_memset(buffer, 0, size);

	auto *fs = (FileStore*) buffer;
	fs->m_fsType = fsType;
	fs->m_version = VERSION;
	fs->m_size = size;
	fs->m_memUsed = sizeof(FileStore<FsSize_t>) + sizeof(Inode);
	fs->m_rootInode = sizeof(FileStore<FsSize_t>);
	((Inode*) (fs + 1))->prev = sizeof(FileStore<FsSize_t>);
	fs->lastInode()->next = sizeof(FileStore<FsSize_t>);

	return (uint8_t*) buffer;
}

typedef FileStore<uint16_t> FileStore16;
typedef FileStore<uint32_t> FileStore32;
typedef FileStore<uint64_t> FileStore64;

}
}<commit_msg>Move file store header into external template<commit_after>/*
 * Copyright 2015 - 2017 <EMAIL>
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */
#pragma once

#include <ox/std/std.hpp>

namespace ox {
namespace fs {

template<typename FsT>
struct FileStoreHeader {
	typedef FsT FsSize_t;
	const static auto VERSION = 2;

	uint16_t version;
	uint16_t fsType;
	FsSize_t size;
	FsSize_t memUsed;
	FsSize_t rootInode;
};

template<typename FsT, typename Header>
class FileStore {

	public:
		typedef uint16_t InodeId_t;
		typedef FsT FsSize_t;
		const static auto VERSION = Header::VERSION;

		struct StatInfo {
			InodeId_t inodeId;
			FsSize_t  size;
			uint8_t fileType;
		};

	private:
		struct Inode {
			// the next Inode in memory
			FsSize_t prev, next;
			FsSize_t dataLen;
			InodeId_t id;
			uint8_t refs;
			uint8_t fileType;
			FsSize_t left, right;

			FsSize_t size();
			void setId(InodeId_t);
			void setData(void *data, FsSize_t size);
			void *data();
		};

		Header m_header;

	public:
		/**
		 * Dumps this file store's inodes to the given file store.
		 */
		int dumpTo(FileStore<FsSize_t, Header> *dest);

		/**
		 * Compacts and resizes the file store to the minimum possible size for
		 * the contents.
		 *
		 * NOTE: This does NOT resize the buffer that this file store refers to!
		 */
		void resize(FsSize_t size = 0);

		/**
		 * Writes the given data to a "file" with the given id.
		 * @param id the id of the file
		 * @param data the contents of the file
		 * @param dataLen the number of bytes data points to
		 */
		int write(InodeId_t id, void *data, FsSize_t dataLen, uint8_t fileType = 0);

		/**
		 * Removes the inode of the given ID.
		 * @param id the id of the file
		 */
		int remove(InodeId_t id);

		/**
		 * Reads the "file" at the given id. You are responsible for freeing
		 * the data when done with it.
		 * @param id id of the "file"
		 * @param data pointer to the pointer where the data is stored
		 * @param size pointer to a value that will be assigned the size of data
		 * @return 0 if read is a success
		 */
		int read(InodeId_t id, void *data, FsSize_t *size);

		/**
		 * Reads the stat information of the inode of the given inode id.
		 * If the returned inode id is 0, then the requested inode was not found.
		 * @param id id of the inode to stat
		 * @return the stat information of the inode of the given inode id
		 */
		StatInfo stat(InodeId_t id);

		/**
		 * Returns the space needed for this data at the given inode address.
		 * @param id the target inode id
		 * @param size the size of the data to insert
		 * @return the space currently available in this file store.
		 */
		FsSize_t spaceNeeded(InodeId_t id, FsSize_t size);

		/**
		 * Returns the size of the file store.
		 * @return the size of the file store.
		 */
		FsSize_t size();

		/**
		 * Returns the space currently available in this file store.
		 * @return the space currently available in this file store.
		 */
		FsSize_t available();

		uint16_t fsType();

		uint16_t version();
		
		static uint8_t *format(uint8_t *buffer, FsSize_t size, uint16_t fsType = 0);

	private:
		/**
		 * Gets the inode at the given id.
		 * @param root the root node to start comparing on
		 * @param id id of the "file"
		 * @param pathLen number of characters in pathLen
		 * @return the requested Inode, if available
		 */
		Inode *getInode(Inode *root, InodeId_t id);

		/**
		 * Gets the inode at the given id.
		 * @param root the root node to start comparing on
		 * @param id id of the "file"
		 * @param pathLen number of characters in pathLen
		 * @param targetAddr the address of the target inode
		 * @return the requested Inode, if available
		 */
		Inode *getInodeParent(Inode *root, InodeId_t id, FsSize_t targetAddr);

		/**
		 * Removes the inode of the given ID.
		 * @param id the id of the file
		 */
		int remove(Inode *root, InodeId_t id);

		/**
		 * Removes the given node from the linked list.
		 * @param node node to remove
		 */
		void dealloc(Inode *node);

		/**
		 * Gets the address of the next available inode, assuming there is a next
		 * available inode.
		 */
		FsSize_t nextInodeAddr();

		/**
		 * Gets an address for a new Inode.
		 * @param size the size of the Inode
		 */
		void *alloc(FsSize_t size);

		/**
		 * Compacts all of the inodes into a contiguous space, starting at the first inode.
		 */
		void compact();

		/**
		 * Inserts the given insertValue into the tree of the given root.
		 * If the inode already exists, it replaces the old on deletes it.
		 * @return true if the inode was inserted
		 */
		bool insert(Inode *root, Inode *insertValue);

		/**
		 * Gets the FsSize_t associated with the next Inode to be allocated.
		 * @retrun the FsSize_t associated with the next Inode to be allocated
		 */
		FsSize_t iterator();

		FsSize_t firstInode();

		Inode *lastInode();

		/**
		 * Updates the address of the inode in the tree.
		 */
		void updateInodeAddress(InodeId_t id, FsSize_t oldAddr, FsSize_t newAddr);

		uint8_t *begin() {
			return (uint8_t*) this;
		}

		uint8_t *end() {
			return begin() + this->m_header.size;
		}

		/**
		 * Converts an actual pointer to a FsSize_t.
		 */
		FsSize_t ptr(void *ptr);

		/**
		 * Converts a FsSize_t to an actual pointer.
		 */
		template<typename T>
		T ptr(FsSize_t ptr) {
			return (T) (begin() + ptr);
		};

};

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::Inode::size() {
	return sizeof(Inode) + dataLen;
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::Inode::setId(InodeId_t id) {
	this->id = id;
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::Inode::setData(void *data, FsSize_t size) {
	ox_memcpy(this->data(), data, size);
	dataLen = size;
}


template<typename FsSize_t, typename Header>
void *FileStore<FsSize_t, Header>::Inode::data() {
	return this + 1;
}


// FileStore

template<typename FsSize_t, typename Header>
int FileStore<FsSize_t, Header>::dumpTo(FileStore<FsSize_t, Header> *dest) {
	if (dest->size() >= size()) {
		auto i = ptr<Inode*>(firstInode());
		do {
			dest->write(i->id, i->data(), i->dataLen, i->fileType);
			i = ptr<Inode*>(i->next);
		} while (ptr(i) != firstInode());
		return 0;
	} else {
		return -1;
	}
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::resize(FsSize_t size) {
	if (size < m_header.size) {
		// shrink file store
		if (m_header.memUsed > size) {
			size = m_header.memUsed;
		}
		compact();
		m_header.size = size;
	} else if (size > m_header.size) {
		// grow file store
		m_header.size = size;
	}
}

template<typename FsSize_t, typename Header>
int FileStore<FsSize_t, Header>::write(InodeId_t id, void *data, FsSize_t dataLen, uint8_t fileType) {
	auto retval = 1;
	const FsSize_t size = sizeof(Inode) + dataLen;
	if (size <= (m_header.size - m_header.memUsed)) {
		auto inode = (Inode*) alloc(size);
		if (inode) {
			remove(id);
			inode->id = id;
			inode->fileType = fileType;
			inode->setData(data, dataLen);
			auto root = ptr<Inode*>(m_header.rootInode);
			if (insert(root, inode) || root == inode) {
				retval = 0;
			}
		}
	}
	return retval;
}

template<typename FsSize_t, typename Header>
int FileStore<FsSize_t, Header>::remove(InodeId_t id) {
	return remove(ptr<Inode*>(m_header.rootInode), id);
}

template<typename FsSize_t, typename Header>
int FileStore<FsSize_t, Header>::remove(Inode *root, InodeId_t id) {
	auto err = 1;

	if (root->id > id) {
		if (root->left) {
			auto node = ptr<Inode*>(root->left);
			if (node->id != id) {
				err = remove(node, id);
			} else {
				root->left = 0;
				if (node->right) {
					insert(root, ptr<Inode*>(node->right));
				}
				if (node->left) {
					insert(root, ptr<Inode*>(node->left));
				}
				dealloc(node);
				node->id = 0;
				node->left = 0;
				node->right = 0;
				err = 0;
			}
		}
	} else if (root->id < id) {
		if (root->right) {
			auto node = ptr<Inode*>(root->right);
			if (node->id != id) {
				err = remove(node, id);
			} else {
				root->right = 0;
				if (node->right) {
					insert(root, ptr<Inode*>(node->right));
				}
				if (node->left) {
					insert(root, ptr<Inode*>(node->left));
				}
				dealloc(node);
				node->id = 0;
				node->left = 0;
				node->right = 0;
				err = 0;
			}
		}
	} else if (ptr<Inode*>(m_header.rootInode)->id == id) {
		m_header.rootInode = root->right;
		if (root->left) {
			insert(ptr<Inode*>(m_header.rootInode), ptr<Inode*>(root->left));
		}
		dealloc(root);
		root->id = 0;
		root->left = 0;
		root->right = 0;
		err = 0;
	}

	return err;
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::dealloc(Inode *inode) {
	auto next = ptr<Inode*>(inode->next);
	auto prev = ptr<Inode*>(inode->prev);
	prev->next = ptr(next);
	next->prev = ptr(prev);

	m_header.memUsed -= inode->size();

	ox_memset(inode, 0, inode->size());
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::updateInodeAddress(InodeId_t id, FsSize_t oldAddr, FsSize_t newAddr) {
	auto parent = getInodeParent(ptr<Inode*>(m_header.rootInode), id, oldAddr);
	if (parent) {
		if (parent->left == oldAddr) {
			parent->left = newAddr;
		} else if (parent->right == oldAddr) {
			parent->right = newAddr;
		}
	}
}

template<typename FsSize_t, typename Header>
int FileStore<FsSize_t, Header>::read(InodeId_t id, void *data, FsSize_t *size) {
	auto inode = getInode(ptr<Inode*>(m_header.rootInode), id);
	int retval = 1;
	if (inode) {
		if (size) {
			*size = inode->dataLen;
		}
		ox_memcpy(data, inode->data(), inode->dataLen);
		retval = 0;
	}
	return retval;
}

template<typename FsSize_t, typename Header>
typename FileStore<FsSize_t, Header>::StatInfo FileStore<FsSize_t, Header>::stat(InodeId_t id) {
	auto inode = getInode(ptr<Inode*>(m_header.rootInode), id);
	StatInfo stat;
	if (inode) {
		stat.size = inode->dataLen;
		stat.fileType = inode->fileType;
		stat.inodeId = id;
	} else {
		stat.inodeId = 0;
	}
	return stat;
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::spaceNeeded(InodeId_t id, FsSize_t size) {
	FsSize_t needed = sizeof(Inode) + size;;
	auto inode = getInode(ptr<Inode*>(m_header.rootInode), id);
	if (inode) {
		needed -= inode->size();
	}
	return needed;
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::size() {
	return m_header.size;
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::available() {
	return m_header.size - m_header.memUsed;
}

template<typename FsSize_t, typename Header>
typename FileStore<FsSize_t, Header>::Inode *FileStore<FsSize_t, Header>::getInode(Inode *root, InodeId_t id) {
	Inode *retval = nullptr;

	if (root->id > id) {
		if (root->left) {
			retval = getInode(ptr<Inode*>(root->left), id);
		}
	} else if (root->id < id) {
		if (root->right) {
			retval = getInode(ptr<Inode*>(root->right), id);
		}
	} else if (root->id == id) {
		retval = root;
	}

	return retval;
}

template<typename FsSize_t, typename Header>
typename FileStore<FsSize_t, Header>::Inode *FileStore<FsSize_t, Header>::getInodeParent(Inode *root, InodeId_t id, FsSize_t targetAddr) {
	Inode *retval = nullptr;

	if (root->id > id) {
		if (root->left) {
			if (root->left == targetAddr) {
				retval = root;
			} else {
				retval = getInodeParent(ptr<Inode*>(root->left), id, targetAddr);
			}
		}
	} else if (root->id < id) {
		if (root->right) {
			if (root->right == targetAddr) {
				retval = root;
			} else {
				retval = getInodeParent(ptr<Inode*>(root->right), id, targetAddr);
			}
		}
	}

	return retval;
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::nextInodeAddr() {
	FsSize_t next = ptr(lastInode()) + lastInode()->size();
	return next;
}

template<typename FsSize_t, typename Header>
void *FileStore<FsSize_t, Header>::alloc(FsSize_t size) {
	FsSize_t next = nextInodeAddr();
	if ((next + size) > (uint64_t) end()) {
		compact();
		next = nextInodeAddr();
		if ((next + size) > (uint64_t) end()) {
			return nullptr;
		}
	}

	const auto retval = next;
	const auto inode = ptr<Inode*>(retval);
	ox_memset(inode, 0, size);
	inode->prev = ptr<Inode*>(firstInode())->prev;
	inode->next = retval + size;
	m_header.memUsed += size;
	ptr<Inode*>(firstInode())->prev = retval;
	return inode;
}

template<typename FsSize_t, typename Header>
void FileStore<FsSize_t, Header>::compact() {
	auto dest = ptr<Inode*>(firstInode());
	auto current = ptr<Inode*>(firstInode());
	while (current->next > firstInode() && current->next < ptr(end())) {
		ox_memcpy(dest, current, current->size());
		if (dest->next != firstInode()) {
			dest->next = ptr(dest) + dest->size();
		}
		ptr<Inode*>(dest->next)->prev = ptr(dest);
		updateInodeAddress(dest->id, ptr(current), ptr(dest));
		current = ptr<Inode*>(dest->next);
		dest = ptr<Inode*>(ptr(dest) + dest->size());
	}
}

template<typename FsSize_t, typename Header>
bool FileStore<FsSize_t, Header>::insert(Inode *root, Inode *insertValue) {
	auto retval = false;

	if (root->id > insertValue->id) {
		if (root->left) {
			retval = insert(ptr<Inode*>(root->left), insertValue);
		} else {
			root->left = ptr(insertValue);
			retval = true;
		}
	} else if (root->id < insertValue->id) {
		if (root->right) {
			retval = insert(ptr<Inode*>(root->right), insertValue);
		} else {
			root->right = ptr(insertValue);
			retval = true;
		}
	} else if (m_header.rootInode == 0) {
		m_header.rootInode = ptr(insertValue);
		retval = true;
	}

	return retval;
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::iterator() {
	return ptr(lastInode()) + lastInode()->size();
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::ptr(void *ptr) {
#ifdef _MSC_VER
#pragma warning(disable:4244)
#endif
	return ((uint8_t*) ptr) - begin();
#ifdef _MSC_VER
#pragma warning(default:4244)
#endif
}

template<typename FsSize_t, typename Header>
FsSize_t FileStore<FsSize_t, Header>::firstInode() {
	return sizeof(FileStore<FsSize_t, Header>);
}

template<typename FsSize_t, typename Header>
typename FileStore<FsSize_t, Header>::Inode *FileStore<FsSize_t, Header>::lastInode() {
	return ptr<Inode*>(ptr<Inode*>(firstInode())->prev);
}

template<typename FsSize_t, typename Header>
uint16_t FileStore<FsSize_t, Header>::fsType() {
	return m_header.fsType;
};

template<typename FsSize_t, typename Header>
uint16_t FileStore<FsSize_t, Header>::version() {
	return m_header.version;
};

template<typename FsSize_t, typename Header>
uint8_t *FileStore<FsSize_t, Header>::format(uint8_t *buffer, FsSize_t size, uint16_t fsType) {
	ox_memset(buffer, 0, size);

	auto *fs = (FileStore*) buffer;
	fs->m_header.fsType = fsType;
	fs->m_header.version = Header::VERSION;
	fs->m_header.size = size;
	fs->m_header.memUsed = sizeof(FileStore<FsSize_t, Header>) + sizeof(Inode);
	fs->m_header.rootInode = sizeof(FileStore<FsSize_t, Header>);
	((Inode*) (fs + 1))->prev = sizeof(FileStore<FsSize_t, Header>);
	fs->lastInode()->next = sizeof(FileStore<FsSize_t, Header>);

	return (uint8_t*) buffer;
}

typedef FileStore<uint16_t, FileStoreHeader<uint16_t>> FileStore16;
typedef FileStore<uint32_t, FileStoreHeader<uint32_t>> FileStore32;
typedef FileStore<uint64_t, FileStoreHeader<uint64_t>> FileStore64;

}
}
{'fraction_non_alphanumeric': 0.14093801555503183, 'fraction_numerical': 0.007070469007777516, 'mean_word_length': 3.7447284345047924, 'pattern_counts': {'":': 0, '<': 243, '<?xml version=': 0, '>': 471, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5289777', 'n_tokens_mistral': 12133, 'n_tokens_neox': 10721, 'n_words': 2935}