$treeview $search $mathjax $extrastylesheet
librsync
2.0.2
$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 <stdio.h> 00024 #include "hashtable.h" 00025 00026 /* Open addressing works best if it can take advantage of memory caches using 00027 locality for probes of adjacent buckets on collisions. So we pack the keys 00028 tightly together in their own key table and avoid referencing the element 00029 table and elements as much as possible. Key value zero is reserved as a 00030 marker for an empty bucket to avoid checking for NULL in the element table. 00031 If we do get a hash value of zero, we -1 to wrap it around to 0xffff. */ 00032 00033 /* Use max 0.8 load factor to avoid bad open addressing performance. */ 00034 #define HASHTABLE_LOADFACTOR_NUM 8 00035 #define HASHTABLE_LOADFACTOR_DEN 10 00036 00037 hashtable_t *_hashtable_new(int size) 00038 { 00039 hashtable_t *t; 00040 int size2; 00041 00042 /* Adjust requested size to account for max load factor. */ 00043 size = 1 + size * HASHTABLE_LOADFACTOR_DEN / HASHTABLE_LOADFACTOR_NUM; 00044 /* Use next power of 2 larger than the requested size. */ 00045 for (size2 = 1; size2 < size; size2 <<= 1) ; 00046 if (!(t = calloc(1, sizeof(hashtable_t)+ size2 * sizeof(unsigned)))) 00047 return NULL; 00048 if (!(t->etable = calloc(size2, sizeof(void *)))) { 00049 free(t); 00050 return NULL; 00051 } 00052 t->size = size2; 00053 t->count = 0; 00054 #ifndef HASHTABLE_NSTATS 00055 t->find_count = t->match_count = t->hashcmp_count = t->entrycmp_count = 0; 00056 #endif 00057 return t; 00058 } 00059 00060 void _hashtable_free(hashtable_t *t) 00061 { 00062 if (t) { 00063 free(t->etable); 00064 free(t); 00065 } 00066 } 00067 00068 void *_hashtable_iter(hashtable_iter_t *i, hashtable_t *t) 00069 { 00070 assert(i != NULL); 00071 assert(t != NULL); 00072 i->htable = t; 00073 i->index = 0; 00074 return _hashtable_next(i); 00075 } 00076 00077 void *_hashtable_next(hashtable_iter_t *i) 00078 { 00079 assert(i->htable != NULL); 00080 assert(i->index <= i->htable->size); 00081 const hashtable_t *t = i->htable; 00082 void *e; 00083 00084 while (i->index < t->size) { 00085 if ((e = t->etable[i->index++])) 00086 return e; 00087 } 00088 return NULL; 00089 }