libyasm/hamt.h

   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