1 /* 2 BAREOS® - Backup Archiving REcovery Open Sourced 3 4 Copyright (C) 2004-2011 Free Software Foundation Europe e.V. 5 Copyright (C) 2014-2016 Bareos GmbH & Co. KG 6 7 This program is Free Software; you can redistribute it and/or 8 modify it under the terms of version three of the GNU Affero General Public 9 License as published by the Free Software Foundation and included 10 in the file LICENSE. 11 12 This program is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Affero General Public License for more details. 16 17 You should have received a copy of the GNU Affero General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. 21 */ 22 /* 23 * Written by Kern Sibbald, MMIV 24 */ 25 /** 26 * @file 27 * Hash table class -- htable 28 */ 29 30 #ifndef BAREOS_LIB_HTABLE_H_ 31 #define BAREOS_LIB_HTABLE_H_ 32 33 /** 34 * Loop var through each member of table 35 */ 36 #ifdef HAVE_TYPEOF 37 #define foreach_htable(var, tbl) \ 38 for ((var) = (typeof(var))((tbl)->first()); (var); \ 39 (var) = (typeof(var))((tbl)->next())) 40 #else 41 #define foreach_htable(var, tbl) \ 42 for ((*((void**)&(var)) = (void*)((tbl)->first())); (var); \ 43 (*((void**)&(var)) = (void*)((tbl)->next()))) 44 #endif 45 46 47 #include "include/hostconfig.h" 48 49 #ifdef HAVE_HPUX_OS 50 #pragma pack(push, 4) 51 #endif 52 53 typedef enum 54 { 55 KEY_TYPE_CHAR = 1, 56 KEY_TYPE_UINT32 = 2, 57 KEY_TYPE_UINT64 = 3, 58 KEY_TYPE_BINARY = 4 59 } key_type_t; 60 61 union hlink_key { 62 char* char_key; 63 uint32_t uint32_key; 64 uint64_t uint64_key; 65 uint8_t* binary_key; 66 }; 67 68 struct hlink { 69 void* next; /* Next hash item */ 70 key_type_t key_type; /* Type of key used to hash */ 71 union hlink_key key; /* Key for this item */ 72 uint32_t key_len; /* Length of key for this item */ 73 uint64_t hash; /* Hash for this key */ 74 }; 75 76 struct h_mem { 77 struct h_mem* next; /* Next buffer */ 78 int32_t rem; /* Remaining bytes in big_buffer */ 79 char* mem; /* Memory pointer */ 80 char first[1]; /* First byte */ 81 }; 82 83 #ifdef HAVE_HPUX_OS 84 #pragma pack(pop) 85 #endif 86 87 class htable { 88 hlink** table = nullptr; /* Hash table */ 89 int loffset = 0; /* Link offset in item */ 90 hlink* walkptr = nullptr; /* Table walk pointer */ 91 uint64_t hash = 0; /* Temp storage */ 92 uint64_t total_size = 0; /* Total bytes malloced */ 93 uint32_t extend_length = 94 0; /* Number of bytes to allocate when extending buffer */ 95 uint32_t walk_index = 0; /* Table walk index */ 96 uint32_t num_items = 0; /* Current number of items */ 97 uint32_t max_items = 0; /* Maximum items before growing */ 98 uint32_t buckets = 0; /* Size of hash table */ 99 uint32_t index = 0; /* Temp storage */ 100 uint32_t mask = 0; /* "Remainder" mask */ 101 uint32_t rshift = 0; /* Amount to shift down */ 102 uint32_t blocks = 0; /* Blocks malloced */ 103 struct h_mem* mem_block = nullptr; /* Malloc'ed memory block chain */ 104 void MallocBigBuf(int size); /* Get a big buffer */ 105 void HashIndex(char* key); /* Produce hash key,index */ 106 void HashIndex(uint32_t key); /* Produce hash key,index */ 107 void HashIndex(uint64_t key); /* Produce hash key,index */ 108 void HashIndex(uint8_t* key, uint32_t key_len); /* Produce hash key,index */ 109 void grow_table(); /* Grow the table */ 110 111 public: 112 htable() = default; 113 htable(void* item, 114 void* link, 115 int tsize = 31, 116 int nr_pages = 0, 117 int nr_entries = 4); ~htable()118 ~htable() { destroy(); } 119 void init(void* item, 120 void* link, 121 int tsize = 31, 122 int nr_pages = 0, 123 int nr_entries = 4); 124 bool insert(char* key, void* item); 125 bool insert(uint32_t key, void* item); 126 bool insert(uint64_t key, void* item); 127 bool insert(uint8_t* key, uint32_t key_len, void* item); 128 void* lookup(char* key); 129 void* lookup(uint32_t key); 130 void* lookup(uint64_t key); 131 void* lookup(uint8_t* key, uint32_t key_len); 132 void* first(); /* Get first item in table */ 133 void* next(); /* Get next item in table */ 134 void destroy(); 135 void stats(); /* Print stats about the table */ 136 uint32_t size(); /* Return size of table */ 137 char* hash_malloc(int size); /* Malloc bytes for a hash entry */ 138 void HashBigFree(); /* Free all hash allocated big buffers */ 139 }; 140 #endif /* BAREOS_LIB_HTABLE_H_ */ 141