/* Tiny AVL trees
 * Copyright (C) 2020 Tirotech Ltd
 *
 * Author: Daniel Beer <daniel.beer@tirotech.co.nz>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef UTIL_TAVL_H_
#define UTIL_TAVL_H_

#include <stdint.h>
#include <stddef.h>

typedef uint32_t tavl_key_t;
typedef uint16_t tavl_index_t;

/* Stored pointers are split into an index and a heavy bit
 *
 * Initialize a root node by setting it to TAVL_NONE
 */
#define TAVL_HEAVY	0x8000
#define TAVL_INDEX	0x7fff

#define TAVL_NONE	TAVL_INDEX
#define TAVL_MAX_NODES	TAVL_INDEX

struct tavl_node {
	tavl_key_t	key;
	tavl_index_t	down[2];
};

/* Find a node, if it exists, or return TAVL_NONE */
tavl_index_t tavl_find(const struct tavl_node *arr, tavl_index_t root,
		       tavl_key_t key);

/* Insert a node. Returns index of existing node replaced, if any */
tavl_index_t tavl_insert(struct tavl_node *arr, tavl_index_t *root,
			 tavl_index_t n);

/* Delete an item. Returns index of node removed, if any */
tavl_index_t tavl_delete(struct tavl_node *arr, tavl_index_t *root,
			 tavl_key_t k);

#endif