$treeview $search $mathjax $extrastylesheet
librsync
2.3.1
$projectbrief
|
$projectbrief
|
$searchbox |
00001 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 * 00003 * hashtable.c -- a generic hashtable implementation. 00004 * 00005 * Copyright (C) 2016 by Donovan Baarda <abo@minkirri.apana.org.au> 00006 * 00007 * This program is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU Lesser General Public License as published by 00009 * the Free Software Foundation; either version 2.1 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 */ 00021 #include <assert.h> 00022 #include <stdlib.h> 00023 #include "hashtable.h" 00024 00025 /* Open addressing works best if it can take advantage of memory caches using 00026 locality for probes of adjacent buckets on collisions. So we pack the keys 00027 tightly together in their own key table and avoid referencing the element 00028 table and elements as much as possible. Key value zero is reserved as a 00029 marker for an empty bucket to avoid checking for NULL in the element table. 00030 If we do get a hash value of zero, we -1 to wrap it around to 0xffff. */ 00031 00032 /* Use max 0.7 load factor to avoid bad open addressing performance. */ 00033 #define HASHTABLE_LOADFACTOR_NUM 7 00034 #define HASHTABLE_LOADFACTOR_DEN 10 00035 00036 hashtable_t *_hashtable_new(int size) 00037 { 00038 hashtable_t *t; 00039 int size2, bits2; 00040 00041 /* Adjust requested size to account for max load factor. */ 00042 size = 1 + size * HASHTABLE_LOADFACTOR_DEN / HASHTABLE_LOADFACTOR_NUM; 00043 /* Use next power of 2 larger than the requested size and get mask bits. */ 00044 for (size2 = 2, bits2 = 1; size2 < size; size2 <<= 1, bits2++) ; 00045 if (!(t = calloc(1, sizeof(hashtable_t)+ size2 * sizeof(unsigned)))) 00046 return NULL; 00047 if (!(t->etable = calloc(size2, sizeof(void *)))) { 00048 _hashtable_free(t); 00049 return NULL; 00050 } 00051 t->size = size2; 00052 t->count = 0; 00053 t->tmask = size2 - 1; 00054 #ifndef HASHTABLE_NBLOOM 00055 if (!(t->kbloom = calloc(size2 / 8, sizeof(unsigned char)))) { 00056 _hashtable_free(t); 00057 return NULL; 00058 } 00059 t->bshift = sizeof(unsigned) * 8 - bits2; 00060 assert(t->tmask == (unsigned)-1 >> t->bshift); 00061 #endif 00062 #ifndef HASHTABLE_NSTATS 00063 t->find_count = t->match_count = t->hashcmp_count = t->entrycmp_count = 0; 00064 #endif 00065 return t; 00066 } 00067 00068 void _hashtable_free(hashtable_t *t) 00069 { 00070 if (t) { 00071 free(t->etable); 00072 #ifndef HASHTABLE_NBLOOM 00073 free(t->kbloom); 00074 #endif 00075 free(t); 00076 } 00077 }