1a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata/* 2a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * This file is part of ltrace. 398ff309cdc98857eb30992f108439cb7d7673598Petr Machata * Copyright (C) 2012, 2013 Petr Machata, Red Hat Inc. 4a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * 5a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * This program is free software; you can redistribute it and/or 6a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * modify it under the terms of the GNU General Public License as 7a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * published by the Free Software Foundation; either version 2 of the 8a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * License, or (at your option) any later version. 9a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * 10a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * This program is distributed in the hope that it will be useful, but 11a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * WITHOUT ANY WARRANTY; without even the implied warranty of 12a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * General Public License for more details. 14a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * 15a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * You should have received a copy of the GNU General Public License 16a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * along with this program; if not, write to the Free Software 17a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 18a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata * 02110-1301 USA 19a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata */ 20a11cbede4711e1efe2d6fb0a8a5b2050b2fe941cPetr Machata 217186e2af704f4458e6383e8a92482594db29b597Juan Cespedes#include <string.h> 22d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata#include <stdlib.h> 23d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata#include <stdio.h> 24d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata#include "dict.h" 25cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 26d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastruct status_bits { 27d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata unsigned char taken : 1; 28d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata unsigned char erased : 1; 29d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata}; 30cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 31d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic struct status_bits * 32d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatabitp(struct dict *dict, size_t n) 33d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 34d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return VECT_ELEMENT(&dict->status, struct status_bits, n); 35d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 36cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 37d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatavoid 38d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_init(struct dict *dict, 39d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t key_size, size_t value_size, 40d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t (*hash1)(const void *), 41d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int (*eq)(const void *, const void *), 42d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t (*hash2)(size_t)) 43d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 44d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(hash1 != NULL); 45d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(eq != NULL); 46cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 47d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata vect_init(&dict->keys, key_size); 48d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata vect_init(&dict->values, value_size); 49d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata VECT_INIT(&dict->status, struct status_bits); 50d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict->size = 0; 51d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 52d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict->hash1 = hash1; 53d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict->hash2 = hash2; 54d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict->eq = eq; 55d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 56cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 57d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastruct clone_data { 58d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict *target; 59d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int (*clone_key)(void *tgt, const void *src, void *data); 60d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int (*clone_value)(void *tgt, const void *src, void *data); 61d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_key)(void *tgt, void *data); 62d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_value)(void *tgt, void *data); 63d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *data; 64cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes}; 65cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 6682fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machatastatic enum callback_status 67d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataclone_cb(void *key, void *value, void *data) 68345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 69d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct clone_data *clone_data = data; 70d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 71d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata char nkey[clone_data->target->keys.elt_size]; 72d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (clone_data->clone_key == NULL) 73d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memmove(nkey, key, sizeof(nkey)); 74d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata else if (clone_data->clone_key(&nkey, key, clone_data->data) < 0) 75d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_STOP; 76d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 77d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata char nvalue[clone_data->target->values.elt_size]; 78d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (clone_data->clone_value == NULL) { 79d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memmove(nvalue, value, sizeof(nvalue)); 80d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } else if (clone_data->clone_value(&nvalue, value, 81d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata clone_data->data) < 0) { 82d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata fail: 83d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (clone_data->clone_key != NULL) 84d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata clone_data->dtor_key(&nkey, clone_data->data); 85d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_STOP; 86cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 87d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 88d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict_insert(clone_data->target, nkey, nvalue) < 0) { 89d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (clone_data->clone_value != NULL) 90d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata clone_data->dtor_value(&nvalue, clone_data->data); 91d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata goto fail; 92cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 93d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 94d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_CONT; 95cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 96cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 97d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataint 98d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_clone(struct dict *target, const struct dict *source, 99d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int (*clone_key)(void *tgt, const void *src, void *data), 100d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_key)(void *tgt, void *data), 101d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int (*clone_value)(void *tgt, const void *src, void *data), 102d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_value)(void *tgt, void *data), 103d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *data) 104d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 105d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert((clone_key != NULL) == (dtor_key != NULL)); 106d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert((clone_value != NULL) == (dtor_value != NULL)); 107d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 108d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict_init(target, source->keys.elt_size, source->values.elt_size, 109d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata source->hash1, source->eq, source->hash2); 110d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct clone_data clone_data = { 111d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata target, clone_key, clone_value, dtor_key, dtor_value, data 112d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata }; 113d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict_each((struct dict *)source, NULL, 114d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata clone_cb, &clone_data) != NULL) { 115d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict_destroy(target, dtor_key, dtor_value, data); 116d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return -1; 117cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 118d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 0; 119d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 120d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 121d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatasize_t 122d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_size(const struct dict *dict) 123d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 124d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return dict->size; 125cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 126cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 127f13505251e6402460f6cc7ec84e0d8ca91607b4fJuan Cespedesint 128d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_empty(const struct dict *dict) 129d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 130d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return dict->size == 0; 131d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 132cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 133d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastruct destroy_data { 134d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_key)(void *tgt, void *data); 135d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_value)(void *tgt, void *data); 136d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *data; 137d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata}; 138cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 13982fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machatastatic enum callback_status 140d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadestroy_cb(void *key, void *value, void *data) 141d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 142d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct destroy_data *destroy_data = data; 143d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (destroy_data->dtor_key) 144d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata destroy_data->dtor_key(key, destroy_data->data); 145d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (destroy_data->dtor_value) 146d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata destroy_data->dtor_value(value, destroy_data->data); 147d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_CONT; 148d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 149cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 150d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatavoid 151d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_destroy(struct dict *dict, 152d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_key)(void *tgt, void *data), 153d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_value)(void *tgt, void *data), 154d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *data) 155d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 156b658d4f2204c596f54813cdb80d668bb4656d598Petr Machata /* Some slots are unused (the corresponding keys and values 157b658d4f2204c596f54813cdb80d668bb4656d598Petr Machata * are uninitialized), so we can't call dtors for them. 158b658d4f2204c596f54813cdb80d668bb4656d598Petr Machata * Iterate DICT instead. */ 159d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dtor_key != NULL || dtor_value != NULL) { 160d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct destroy_data destroy_data = { 161d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dtor_key, dtor_value, data 162d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata }; 163d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict_each(dict, NULL, destroy_cb, &destroy_data); 164cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 165cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 166d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata vect_destroy(&dict->keys, NULL, NULL); 167d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata vect_destroy(&dict->values, NULL, NULL); 168d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata vect_destroy(&dict->status, NULL, NULL); 169d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 170cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 171d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic size_t 172d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadefault_secondary_hash(size_t pos) 173d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 174d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return pos % 97 + 1; 175d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 176cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 1772718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machatastatic size_t 1782718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machatasmall_secondary_hash(size_t pos) 1792718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata{ 1802718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata return 1; 1812718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata} 1822718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata 183d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic inline size_t 184d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatan(struct dict *dict) 185d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 186d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return vect_size(&dict->keys); 187cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 188cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 189d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic inline size_t (* 190d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatahash2(struct dict *dict))(size_t) 191d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 192d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict->hash2 != NULL) 193d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return dict->hash2; 1942718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata else if (n(dict) < 100) 1952718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata return small_secondary_hash; 196d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata else 197d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return default_secondary_hash; 19877fbb8ff4ba461c11af3678a0db7cf6a47738ff4Petr Machata} 19977fbb8ff4ba461c11af3678a0db7cf6a47738ff4Petr Machata 200d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic void * 201d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatagetkey(struct dict *dict, size_t pos) 202345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 203d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return ((unsigned char *)dict->keys.data) 204d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata + dict->keys.elt_size * pos; 205d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 206cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 207d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic void * 208d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatagetvalue(struct dict *dict, size_t pos) 209d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 210d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return ((unsigned char *)dict->values.data) 211d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata + dict->values.elt_size * pos; 212d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 213cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 214d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic size_t 215d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatafind_slot(struct dict *dict, const void *key, 216d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int *foundp, int *should_rehash, size_t *pi) 217d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 21882fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machata assert(n(dict) > 0); 219d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t pos = dict->hash1(key) % n(dict); 220d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t pos0 = -1; 221d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t d = hash2(dict)(pos); 222d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i = 0; 223d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata *foundp = 0; 224d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 225d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* We skip over any taken or erased slots. But we remember 226d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * the first erased that we find, and if we don't find the key 227d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * later, we return that position. */ 228d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (; bitp(dict, pos)->taken || bitp(dict, pos)->erased; 229d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata pos = (pos + d) % n(dict)) { 230d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (pos0 == (size_t)-1 && bitp(dict, pos)->erased) 231d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata pos0 = pos; 232d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 2332718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata /* If there is a loop, but we've seen an erased 2342718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata * element, take that one. Otherwise give up. */ 2352718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata if (++i > dict->size) { 2362718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata if (pos0 != (size_t)-1) 2372718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata break; 2382718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata return (size_t)-1; 2392718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata } 240cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 241d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (bitp(dict, pos)->taken 242d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata && dict->eq(getkey(dict, pos), key)) { 243d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata *foundp = 1; 244cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes break; 245cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 246cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 247d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 248d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (!*foundp && pos0 != (size_t)-1) 249d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata pos = pos0; 250d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 251d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* If the hash table degraded into a linked list, request a 252d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * rehash. */ 253d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (should_rehash != NULL) 254d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata *should_rehash = i > 10 && i > n(dict) / 10; 255d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 256d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (pi != NULL) 257d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata *pi = i; 258d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return pos; 259cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 260cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 26182fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machatastatic enum callback_status 262d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatarehash_move(void *key, void *value, void *data) 263d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 264d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict_insert(data, key, value) < 0) 265d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_STOP; 266d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata else 267d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_CONT; 268d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 269d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 27082fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machatastatic int 271d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatarehash(struct dict *dict, size_t nn) 272d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 2732718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata assert(nn != n(dict)); 274d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int ret = -1; 275d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 276d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict tmp; 277d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict_init(&tmp, dict->keys.elt_size, dict->values.elt_size, 278d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict->hash1, dict->eq, dict->hash2); 279d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 280d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* To honor all invariants (so that we can safely call 281d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * dict_destroy), we first make a request to _reserve_ enough 282d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * room in all vectors. This has no observable effect on 283d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * contents of vectors. */ 284d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (vect_reserve(&tmp.keys, nn) < 0 285d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata || vect_reserve(&tmp.values, nn) < 0 286d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata || vect_reserve(&tmp.status, nn) < 0) 287d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata goto done; 288d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 289d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* Now that we know that there is enough size in vectors, we 290d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * simply bump the size. */ 291d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata tmp.keys.size = nn; 292d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata tmp.values.size = nn; 293d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t old_size = tmp.status.size; 294d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata tmp.status.size = nn; 295d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memset(VECT_ELEMENT(&tmp.status, struct status_bits, old_size), 296d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 0, (tmp.status.size - old_size) * tmp.status.elt_size); 297d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 298d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* At this point, TMP is once more an empty dictionary with NN 299d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * slots. Now move stuff from DICT to TMP. */ 300d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict_each(dict, NULL, rehash_move, &tmp) != NULL) 301d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata goto done; 302d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 303d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* And now swap contents of DICT and TMP, and we are done. */ 304d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata { 305d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict tmp2 = *dict; 306d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata *dict = tmp; 307d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata tmp = tmp2; 308d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 309cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 310d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata ret = 0; 311cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 312d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadone: 313d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* We only want to release the containers, not the actual data 314d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * that they hold, so it's fine if we don't pass any dtor. */ 315d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dict_destroy(&tmp, NULL, NULL, NULL); 316d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return ret; 317d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 318d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 319d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 320d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic const size_t primes[] = { 321d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 322d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 8191, 16381, 32749, 65521, 130981, 0 323d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata}; 324d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 325d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic size_t 326d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatalarger_size(size_t current) 327d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 328d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (current == 0) 329d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return primes[0]; 330d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 331d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (current < primes[sizeof(primes)/sizeof(*primes) - 2]) { 332d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i; 333d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; primes[i] != 0; ++i) 334d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (primes[i] > current) 335d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return primes[i]; 336d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata abort(); 337efe85f0668a077b1e851df4b3f87a380cf2269fdJuan Cespedes } 338d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 339d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* We ran out of primes, so invent a new one. The following 340d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * gives primes until about 17M elements (and then some more 341d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * later). */ 342d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 2 * current + 6585; 343d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 344d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 345d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic size_t 346d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatasmaller_size(size_t current) 347d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 348d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (current <= primes[0]) 349d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return primes[0]; 350d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 351d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (current <= primes[sizeof(primes)/sizeof(*primes) - 2]) { 352d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i; 353d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t prev = 0; 354d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; primes[i] != 0; ++i) { 355d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (primes[i] >= current) 356d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return prev; 357d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata prev = primes[i]; 358cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 359d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata abort(); 360cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes } 361d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 362d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return (current - 6585) / 2; 363cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 364cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 365d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataint 366d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_insert(struct dict *dict, void *key, void *value) 367d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 368d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (n(dict) == 0 || dict->size > 0.7 * n(dict)) 369d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata rehash: 370d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (rehash(dict, larger_size(n(dict))) < 0) 371d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return -1; 372d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 373d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int found; 374d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int should_rehash; 375d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t slot_n = find_slot(dict, key, &found, &should_rehash, NULL); 3762718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata if (slot_n == (size_t)-1) 3772718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata return -1; 378d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (found) 379d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 1; 3802718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata assert(!bitp(dict, slot_n)->taken); 381d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 382d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* If rehash was requested, do that, and retry. But just live 383d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * with it for apparently sparse tables. No resizing can fix 384d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * a rubbish hash. */ 385d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (should_rehash && dict->size > 0.3 * n(dict)) 386d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata goto rehash; 387d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 388d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memmove(getkey(dict, slot_n), key, dict->keys.elt_size); 389d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memmove(getvalue(dict, slot_n), value, dict->values.elt_size); 390d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 391d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata bitp(dict, slot_n)->taken = 1; 392d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata bitp(dict, slot_n)->erased = 0; 393d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata ++dict->size; 394cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 395d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 0; 396d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 397d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 398d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatavoid * 399d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_find(struct dict *dict, const void *key) 400345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 401d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict->size == 0) 402d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return NULL; 40382fa4c470a908ab4fc6713d120ae87b278edeacfPetr Machata assert(n(dict) > 0); 404cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 405d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int found; 406d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t slot_n = find_slot(dict, key, &found, NULL, NULL); 407d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (found) 408d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return getvalue(dict, slot_n); 409d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata else 410d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return NULL; 411cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 412cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 413f13505251e6402460f6cc7ec84e0d8ca91607b4fJuan Cespedesint 414d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_erase(struct dict *dict, const void *key, 415d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_key)(void *tgt, void *data), 416d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void (*dtor_value)(void *tgt, void *data), 417d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *data) 418345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 419d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int found; 420d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i; 421d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t slot_n = find_slot(dict, key, &found, NULL, &i); 422d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (!found) 423d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return -1; 424d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 425d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dtor_key != NULL) 426d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dtor_key(getkey(dict, slot_n), data); 427d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dtor_value != NULL) 428d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata dtor_value(getvalue(dict, slot_n), data); 429d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 430d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata bitp(dict, slot_n)->taken = 0; 431d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata bitp(dict, slot_n)->erased = 1; 432d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata --dict->size; 433d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 434d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (dict->size < 0.3 * n(dict)) { 4352718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata size_t smaller = smaller_size(n(dict)); 4362718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata if (smaller != n(dict)) 4372718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata /* Don't mind if it fails when shrinking. */ 4382718e3fdab7a3ac75dad45c6969f1aeb4a159a68Petr Machata rehash(dict, smaller); 439d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 440d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 441d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 0; 442cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 443cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 444d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatavoid * 445d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_each(struct dict *dict, void *start_after, 446d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata enum callback_status (*cb)(void *, void *, void *), void *data) 447345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 448d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i; 449d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (start_after != NULL) 450d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata i = ((start_after - dict->keys.data) / dict->keys.elt_size) + 1; 451d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata else 452d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata i = 0; 453d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 454d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (; i < dict->keys.size; ++i) 455d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (bitp(dict, i)->taken && !bitp(dict, i)->erased) { 456d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata void *key = getkey(dict, i); 457d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (cb(key, getvalue(dict, i), data) != CBS_CONT) 458d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return key; 459d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 460d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 461d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return NULL; 462d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 463d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 464d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatasize_t 465d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_hash_int(const int *key) 466d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 467a2c270e86913ab93c41cdd61055d7c2b71b10fa1Petr Machata return (size_t)(*key * 2654435761U); 468cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 469cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes 470f13505251e6402460f6cc7ec84e0d8ca91607b4fJuan Cespedesint 471d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_eq_int(const int *key1, const int *key2) 472345c9b5195383c7b2d2d9db308e824259323803fPetr Machata{ 473d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return *key1 == *key2; 474cac15c3f170b5ec2cc6304c8c0763a78103e1778Juan Cespedes} 475bc8caf0ca16c8cb87bc8288c7a49ee164d075eadJuan Cespedes 476d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatasize_t 477d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_hash_string(const char **key) 478534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata{ 479d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t h = 5381; 480d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata const char *str = *key; 481d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata while (*str != 0) 482d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata h = h * 33 ^ *str++; 483d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return h; 484d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 485bc8caf0ca16c8cb87bc8288c7a49ee164d075eadJuan Cespedes 486d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataint 487d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_eq_string(const char **key1, const char **key2) 488d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 489d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return strcmp(*key1, *key2) == 0; 490d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 491cd8976dbee947f152c3a322503a1063c6359da76Juan Cespedes 4923e86576623d16c5032af4d50108eb878166fb686Petr Machatavoid 4933e86576623d16c5032af4d50108eb878166fb686Petr Machatadict_dtor_string(const char **key, void *data) 4943e86576623d16c5032af4d50108eb878166fb686Petr Machata{ 4953e86576623d16c5032af4d50108eb878166fb686Petr Machata free((char *)*key); 4963e86576623d16c5032af4d50108eb878166fb686Petr Machata} 4973e86576623d16c5032af4d50108eb878166fb686Petr Machata 4983e86576623d16c5032af4d50108eb878166fb686Petr Machataint 4993e86576623d16c5032af4d50108eb878166fb686Petr Machatadict_clone_string(const char **tgt, const char **src, void *data) 5003e86576623d16c5032af4d50108eb878166fb686Petr Machata{ 5013e86576623d16c5032af4d50108eb878166fb686Petr Machata *tgt = strdup(*src); 5023e86576623d16c5032af4d50108eb878166fb686Petr Machata return *tgt != NULL ? 0 : -1; 5033e86576623d16c5032af4d50108eb878166fb686Petr Machata} 5043e86576623d16c5032af4d50108eb878166fb686Petr Machata 505d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata#ifdef TEST 506d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic enum callback_status 507d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadump(int *key, int *value, void *data) 508d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 509d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata char *seen = data; 510d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(seen[*key] == 0); 511d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata seen[*key] = 1; 512d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(*value == *key * 2 + 1); 513d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_STOP; 514d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 515534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 516d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic size_t 517d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatadict_hash_int_silly(const int *key) 518d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 519d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return *key % 10; 520d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 521534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 522d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic void 523d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataverify(struct dict *di, size_t len, char *seen) 524d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata{ 525d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t ct = 0; 526d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int *it; 527d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (it = NULL; (it = DICT_EACH(di, int, int, it, dump, seen)) != NULL;) 528d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata ct++; 529d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(ct == len); 530d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata memset(seen, 0, len); 531bc8caf0ca16c8cb87bc8288c7a49ee164d075eadJuan Cespedes} 532534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 533d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic enum callback_status 534d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatafill_keys(int *key, int *value, void *data) 535534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata{ 536d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int *array = data; 537d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata array[++array[0]] = *key; 538d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return CBS_CONT; 539d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata} 540534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 541d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic void 542d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatatest1(void) 543534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata{ 544d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict di; 545d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_INIT(&di, int, int, dict_hash_int, dict_eq_int, NULL); 546d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 547d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata char seen[100000] = {}; 548d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t i; 549d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; i < sizeof(seen); ++i) { 550d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int key = i; 551d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int value = 2 * i + 1; 552d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_INSERT(&di, &key, &value); 55398ff309cdc98857eb30992f108439cb7d7673598Petr Machata int *valp = DICT_FIND_REF(&di, &key, int); 554d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(valp != NULL); 555d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(*valp == value); 556d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(dict_size(&di) == i + 1); 557d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 558d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 559d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata verify(&di, sizeof(seen), seen); 560d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 561d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict d2; 562d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_CLONE(&d2, &di, int, int, NULL, NULL, NULL, NULL, NULL); 563d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_DESTROY(&di, int, int, NULL, NULL, NULL); 564d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata verify(&d2, sizeof(seen), seen); 565d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 566d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* Now we try to gradually erase all elements. We can't erase 567d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * inside a DICT_EACH call, so copy first keys to a separate 568d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * memory area first. */ 569d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int keys[d2.size + 1]; 570d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata size_t ct = 0; 571d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata keys[0] = 0; 572d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_EACH(&d2, int, int, NULL, fill_keys, keys); 573d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; i < (size_t)keys[0]; ++i) { 574d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(DICT_ERASE(&d2, &keys[i + 1], int, 575d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata NULL, NULL, NULL) == 0); 576d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata ++ct; 577d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 578d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(ct == sizeof(seen)); 579d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_DESTROY(&d2, int, int, NULL, NULL, NULL); 580534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata} 581534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 582d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatastatic void 583d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machatatest_erase(void) 584534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata{ 585d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int i; 586d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 587d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* To test erase, we need a relatively bad hash function, so 588d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * that there are some overlapping chains in the table. */ 589d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict d2; 590d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_INIT(&d2, int, int, dict_hash_int_silly, dict_eq_int, NULL); 591d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata const int limit = 500; 592d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; i < limit; ++i) { 593d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int key = 2 * i + 1; 594d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int value = 2 * key + 1; 595d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_INSERT(&d2, &key, &value); 596d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 597d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 598d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata /* Now we try to delete each of the keys, and verify that none 599d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata * of the chains was broken. */ 600d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (i = 0; i < limit; ++i) { 601d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata struct dict copy; 602d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_CLONE(©, &d2, int, int, NULL, NULL, NULL, NULL, NULL); 603d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int key = 2 * i + 1; 604d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_ERASE(©, &key, int, NULL, NULL, NULL); 605d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(dict_size(©) == dict_size(&d2) - 1); 606d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 607d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata int j; 608d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata for (j = 0; j < limit; ++j) { 609d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata key = 2 * j + 1; 61098ff309cdc98857eb30992f108439cb7d7673598Petr Machata int *valp = DICT_FIND_REF(©, &key, int); 611d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata if (i != j) { 612d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(valp != NULL); 613d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(*valp == 2 * key + 1); 614d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } else { 615d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata assert(valp == NULL); 616d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 617d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 618d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 619d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_DESTROY(©, int, int, NULL, NULL, NULL); 620d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata } 621d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata DICT_DESTROY(&d2, int, int, NULL, NULL, NULL); 622534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata} 623534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata 624d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machataint main(int argc, char *argv[]) 625534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata{ 626d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata test1(); 627d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata test_erase(); 628d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata return 0; 629534e00fcdb63af352414f5bf180ec392157b1a2bPetr Machata} 630d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata 631d7e4ca82e1cf20bb2605befb1da74dd1688c706ePetr Machata#endif 632