1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
|
/*
* 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 */
|