Home | History | Annotate | Download | only in libyasm
      1 /**
      2  * \file libyasm/hamt.h
      3  * \brief Hash Array Mapped Trie (HAMT) functions.
      4  *
      5  * \license
      6  *  Copyright (C) 2001-2007  Peter Johnson
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  *
     17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS''
     18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE
     21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27  * POSSIBILITY OF SUCH DAMAGE.
     28  * \endlicense
     29  */
     30 #ifndef YASM_HAMT_H
     31 #define YASM_HAMT_H
     32 
     33 #ifndef YASM_LIB_DECL
     34 #define YASM_LIB_DECL
     35 #endif
     36 
     37 /** Hash array mapped trie data structure (opaque type). */
     38 typedef struct HAMT HAMT;
     39 /** Hash array mapped trie entry (opaque type). */
     40 typedef struct HAMTEntry HAMTEntry;
     41 
     42 /** Create new, empty, HAMT.  error_func() is called when an internal error is
     43  * encountered--it should NOT return to the calling function.
     44  * \param   nocase          nonzero if HAMT should be case-insensitive
     45  * \param   error_func      function called on internal error
     46  * \return New, empty, hash array mapped trie.
     47  */
     48 YASM_LIB_DECL
     49 HAMT *HAMT_create(int nocase, /*@exits@*/ void (*error_func)
     50     (const char *file, unsigned int line, const char *message));
     51 
     52 /** Delete HAMT and all data associated with it.  Uses deletefunc() to delete
     53  * each data item.
     54  * \param hamt          Hash array mapped trie
     55  * \param deletefunc    Data deletion function
     56  */
     57 YASM_LIB_DECL
     58 void HAMT_destroy(/*@only@*/ HAMT *hamt,
     59                   void (*deletefunc) (/*@only@*/ void *data));
     60 
     61 /** Insert key into HAMT, associating it with data.
     62  * If the key is not present in the HAMT, inserts it, sets *replace to 1, and
     63  *  returns the data passed in.
     64  * If the key is already present and *replace is 0, deletes the data passed
     65  *  in using deletefunc() and returns the data currently associated with the
     66  *  key.
     67  * If the key is already present and *replace is 1, deletes the data currently
     68  *  associated with the key using deletefunc() and replaces it with the data
     69  *  passed in.
     70  * \param hamt          Hash array mapped trie
     71  * \param str           Key
     72  * \param data          Data to associate with key
     73  * \param replace       See above description
     74  * \param deletefunc    Data deletion function if data is replaced
     75  * \return Data now associated with key.
     76  */
     77 YASM_LIB_DECL
     78 /*@dependent@*/ void *HAMT_insert(HAMT *hamt, /*@dependent@*/ const char *str,
     79                                   /*@only@*/ void *data, int *replace,
     80                                   void (*deletefunc) (/*@only@*/ void *data));
     81 
     82 /** Search for the data associated with a key in the HAMT.
     83  * \param hamt          Hash array mapped trie
     84  * \param str           Key
     85  * \return NULL if key/data not present in HAMT, otherwise associated data.
     86  */
     87 YASM_LIB_DECL
     88 /*@dependent@*/ /*@null@*/ void *HAMT_search(HAMT *hamt, const char *str);
     89 
     90 /** Traverse over all keys in HAMT, calling function on each data item.
     91  * \param hamt          Hash array mapped trie
     92  * \param d             Data to pass to each call to func.
     93  * \param func          Function to call
     94  * \return Stops early (and returns func's return value) if func returns a
     95  *         nonzero value; otherwise 0.
     96  */
     97 YASM_LIB_DECL
     98 int HAMT_traverse(HAMT *hamt, /*@null@*/ void *d,
     99                   int (*func) (/*@dependent@*/ /*@null@*/ void *node,
    100                                /*@null@*/ void *d));
    101 
    102 /** Get the first entry in a HAMT.
    103  * \param hamt          Hash array mapped trie
    104  * \return First entry in HAMT, or NULL if HAMT is empty.
    105  */
    106 YASM_LIB_DECL
    107 const HAMTEntry *HAMT_first(const HAMT *hamt);
    108 
    109 /** Get the next entry in a HAMT.
    110  * \param prev          Previous entry in HAMT
    111  * \return Next entry in HAMT, or NULL if no more entries.
    112  */
    113 YASM_LIB_DECL
    114 /*@null@*/ const HAMTEntry *HAMT_next(const HAMTEntry *prev);
    115 
    116 /** Get the corresponding data for a HAMT entry.
    117  * \param entry         HAMT entry (as returned by HAMT_first() and HAMT_next())
    118  * \return Corresponding data item.
    119  */
    120 YASM_LIB_DECL
    121 void *HAMTEntry_get_data(const HAMTEntry *entry);
    122 
    123 #endif
    124