include/hashtbl.h

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2018 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 /*
  35  * hashtbl.h
  36  *
  37  * Efficient dictionary hash table class.
  38  */
  39
  40 #ifndef NASM_HASHTBL_H
  41 #define NASM_HASHTBL_H
  42
  43 #include "nasmlib.h"
  44
  45 struct hash_node {
  46     uint64_t hash;
  47     const void *key;
  48     size_t keylen;
  49     void *data;
  50 };
  51
  52 struct hash_table {
  53     struct hash_node *table;
  54     size_t load;
  55     size_t size;
  56     size_t max_load;
  57 };
  58
  59 struct hash_insert {
  60     struct hash_table *head;
  61     struct hash_node *where;
  62     struct hash_node node;
  63 };
  64
  65 struct hash_iterator {
  66     const struct hash_table *head;
  67     const struct hash_node *next;
  68 };
  69
  70 uint64_t crc64(uint64_t crc, const char *string);
  71 uint64_t crc64i(uint64_t crc, const char *string);
  72 uint64_t crc64b(uint64_t crc, const void *data, size_t len);
  73 uint64_t crc64ib(uint64_t crc, const void *data, size_t len);
  74 #define CRC64_INIT UINT64_C(0xffffffffffffffff)
  75
  76 static inline uint64_t crc64_byte(uint64_t crc, uint8_t v)
  77 {
  78     extern const uint64_t crc64_tab[256];
  79     return crc64_tab[(uint8_t)(v ^ crc)] ^ (crc >> 8);
  80 }
  81
  82 void **hash_find(struct hash_table *head, const char *string,
  83                 struct hash_insert *insert);
  84 void **hash_findb(struct hash_table *head, const void *key, size_t keylen,
  85                 struct hash_insert *insert);
  86 void **hash_findi(struct hash_table *head, const char *string,
  87                 struct hash_insert *insert);
  88 void **hash_findib(struct hash_table *head, const void *key, size_t keylen,
  89                    struct hash_insert *insert);
  90 void **hash_add(struct hash_insert *insert, const void *key, void *data);
  91 static inline void hash_iterator_init(const struct hash_table *head,
  92                                       struct hash_iterator *iterator)
  93 {
  94     iterator->head = head;
  95     iterator->next = head->table;
  96 }
  97 const struct hash_node *hash_iterate(struct hash_iterator *iterator);
  98
  99 #define hash_for_each(_head,_it,_np) \
 100     for (hash_iterator_init((_head), &(_it)), (_np) = hash_iterate(&(_it)) ; \
 101          (_np) ; (_np) = hash_iterate(&(_it)))
 102
 103 void hash_free(struct hash_table *head);
 104 void hash_free_all(struct hash_table *head, bool free_keys);
 105
 106 #endif /* NASM_HASHTBL_H */