/*
** Not A Hash Table
**
** Joshua Reich 2006
**
**
** Unlike a hash table, naht has the following properties:
**
** 1. Predefined storage size - no malloc overhead as you grow chains
** 2. No need for linked list traversal (as everything is an array)
** 3. No guarantee that things you insert in the naht will be found later
**
** Because of 1 & 2, there is no way to ensure that we won't over-write
** already inserted data with new data. If you care about the data you
** are storing in the naht, then please use the discard() function to 
** deal with this situation.
**
** We use a LRU policy for discarding old data to make room for new.
** We also search most recently added items when searching.
** This makes for a nice DB table cache. Especially nice for a read-
** cache. I also use it for a write cache, using discard() to write
** stuff out as needed.
*/

#ifndef __NAHT_H__
#define __NAHT_H__

#ifdef THREAD_SAFE
#include "pthread.h"
#endif 

/* 
** Set this appropriately for your application & architecture.
** 1024 should be reasonable for most people.
*/

#define NAHT_CHAIN_LENGTH_BYTES		1024

typedef struct nahtT
{
	void			*bin;
	int				*bins;
	int				*idx;
#ifdef THREAD_SAFE
	pthread_mutex_t	*lock;
#endif
	size_t			item_size;
	int				chain_length;
	unsigned long	mask;
	int				chain_mask;
	unsigned long	buckets;
	int				(*compare)(void *a, void *b);
	void			(*discard)(void *a);
} nahtT;

nahtT 	*naht_init (size_t item_size, float mb, int (*compare)(void *a, void *b), void (*discard)(void *a));
void	naht_free (nahtT *n);
void	*naht_find (nahtT *n, unsigned long hash, void *item);
void	naht_insert (nahtT *n, unsigned long hash, void *item);
void    naht_walk (nahtT *n, void (*walk)(void *a));

#endif