/* 
 * mtable.h
 * 
 * This module implements a sparse multi-level array.
 * The indices of the array range from 0 to (2^n)-1, inclusive,
 * and the n bits used for the addressing can be split
 * into arbitrary groups of consecutive bits, 
 * one group representing each level of the table.
 * 
 * This module is used in utf8trans to store
 * the Unicode translation table, where the index
 * can get as high as (2^31)-1, but usually the table
 * stores only a few thousand entries scattered in blocks
 * in the bottom 64k addresses.
 *
 * Each entry in the multi-level array is assumed
 * to be of type void*.  If unassigned, the entry
 * is the null pointer.
 */

#ifndef MTABLE_H
#define MTABLE_H

typedef unsigned int mtable_key;
struct mtable {
    int *exponents;
    void *slots[1];
};
typedef struct mtable *mtable_t;

/* 
 * Makes a new sparse multi-level array.
 * 
 * exponents is a list of positive integers which
 * are the number of bits of addressing for each 
 * level of the table.  The list is terminated
 * by a single zero entry.  
 *
 * For example, for a 2^4 * 2^8 table (total 2^(4+8) entries), 
 *  set exponents = [ 4, 8, 0 ].
 *
 * The most significant bits are listed first.
 *
 * All entries are initially unassigned (that is, they are NULL).
 */
mtable_t mtable_new(int *exponents);

/*
 * Deallocates a multi-level array created by mtable_delete.
 */
void mtable_delete(mtable_t mtable);

/*
 * Extends the given multi-level array by adding
 * more bits of addressing.  The existing
 * entries in the array are given a prefix of zero
 * in the expanded address space.
 */
mtable_t mtable_extend(mtable_t mtab, int *exponents);

/*
 * Changes the entry at the given index to the given data
 * value.
 */
void mtable_set(mtable_t mtable, mtable_key key, void *data);

/*
 * Returns the entry at the given index.
 */
void *mtable_get(mtable_t mtable, mtable_key key);

#endif  /* !defined MTABLE_H */