/*
 * keysdb.h - Two Levels Radix-tree Interface
 * 
 * Authors Ghassan Almalless (2008,2009,2010,2011,2012)
 *         Alain Greiner (2016)
 *
 * Copyright  UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-kernel.
 *
 * ALMOS-kernel is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-kernel is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _KEYS_DB_H_
#define _KEYS_DB_H_

#include <types.h>
#include <kmem.h>

#define KEYS_PER_REC        64

/*******************************************************************************************
 * This define the second level in the two level radix-tree, called a record.
 * A record is an array of KEYS_PER_RECORD pointers.
 * Each entry is a (void *) pointer on a key-addressable item.
 * The memory is dynamically allocated for a record only if this record contains 
 * a least one non NULL entry. 
 ******************************************************************************************/

typedef struct keys_record_s
{
	void * tbl[KEYS_PER_REC];
}
keys_record_t;

/*******************************************************************************************
 * This structure defines the two levels radix-tree descriptor.
 * The key is split in two fields : a record_index (MSB) / a key_index (LSB)
 * The first level in the two levels radix-tree is an array of pointers on records.
 * The number of entries in this array is fixed as [sizeof(page) / sizeof(pointer)].
 * The total number of key values is [sizeof(page) / sizeof(pointer)] * KEYS_PER_RECORD.
 ******************************************************************************************/

typedef struct keysdb_s
{
	keys_record_t ** root;           /*! pointer on array of records pointers             */
	uint32_t         records_nr;     /*! number of entries in records array               */
	uint32_t         records_bits;   /*! number of bits to code the record index          */
    uint32_t         keys_nr;        /*! number of entries (keys) in a record             */
	uint32_t         keys_bits;      /*! number of bits to code the key index             */
	page_t         * page;           /*! page descriptor containing the records array     */
}
keysdb_t;


/*******************************************************************************************
 * This function initialises the two levels radix-tree descriptor, and allocates
 * memory (one physical page) to store the records array.
 * @ db      : pointer on the radix-tree descriptor.
 * @ returns 0 if success / returns ENOMEM if no more memory.      
 ******************************************************************************************/
error_t keysdb_init( keysdb_t * db );

/*******************************************************************************************
 * This function releases all memory allocated to store the array of records pointers,
 * and the records themselve. 
 * @ db      : pointer on the radix-tree descriptor.
 ******************************************************************************************/
void keysdb_destroy( keysdb_t * db );

/*******************************************************************************************
 * This function insert a new item in the two level radix-tree.
 * It dynamically allocates memory for a new record if required.
 * @ db      : pointer on the radix-tree descriptor.
 * @ key     : key value used to address the radix tree
 * @ value   : pointer on item to be registered in radix-tree.
 * @ returns 0 if success / returns EINVAL if illegal key value.
 ******************************************************************************************/
error_t keysdb_insert( keysdb_t * db,
                       uint32_t   key,
                       void     * value );

/*******************************************************************************************
 * This function removes an item identified by its key, and returns a pointer
 * on the removed item.
 * @ db      : pointer on the radix-tree descriptor.
 * @ key     : key value.
 * @ returns item pointer if success / returns NULL if failure.
 ******************************************************************************************/
void * keysdb_remove( keysdb_t * db,
                      uint32_t   key );

/*******************************************************************************************
 * This function returns the pointer on the item identified by its key.
 * @ db      : pointer on the radix-tree descriptor.
 * @ key     : key value.
 * @ returns item pointer if success / returns NULL if failure.
 ******************************************************************************************/
void * keysdb_lookup( keysdb_t * db, 
                      uint32_t   key );

/*******************************************************************************************
 * This function displays the content of a two levels radix_tree.
 * @ db      : pointer on the radix-tree descriptor.
 * @ name    : string identifying the radix-tree.
 ******************************************************************************************/
void keysdb_print( keysdb_t * db,
                   char     * name );


/* TODO the two following functions deprecated [AG] */

/*******************************************************************************************
 ******************************************************************************************/
error_t keysdb_bind( keysdb_t *db, uint32_t key_start, uint32_t keys_nr, void *value);

/*******************************************************************************************
 ******************************************************************************************/
error_t keysdb_unbind( keysdb_t *db, uint32_t key_start, uint32_t keys_nr);

#endif	/* _KEYS_DB_H_ */