1 /* 2 * Copyright 2012 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 * 23 * Authors: 24 * Eric Anholt <eric (at) anholt.net> 25 */ 26 27 #include <stdlib.h> 28 #include <stdio.h> 29 #include <string.h> 30 #include <assert.h> 31 #include "hash_table.h" 32 33 int 34 main(int argc, char **argv) 35 { 36 struct hash_table *ht; 37 const char *str1 = "test1"; 38 const char *str2 = "test2"; 39 const char *str3 = "test3"; 40 struct hash_entry *entry1, *entry2, *search_entry; 41 uint32_t bad_hash = 5; 42 int i; 43 44 (void) argc; 45 (void) argv; 46 47 ht = _mesa_hash_table_create(NULL, NULL, _mesa_key_string_equal); 48 49 /* Insert some items. Inserting 3 items forces a rehash and the new 50 * table size is big enough that we don't get rehashes later. 51 */ 52 _mesa_hash_table_insert_pre_hashed(ht, bad_hash, str1, NULL); 53 _mesa_hash_table_insert_pre_hashed(ht, bad_hash, str2, NULL); 54 _mesa_hash_table_insert_pre_hashed(ht, bad_hash, str3, NULL); 55 56 entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1); 57 assert(entry1->key == str1); 58 59 entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2); 60 assert(entry2->key == str2); 61 62 /* Check that we can still find #1 after inserting #2 */ 63 entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1); 64 assert(entry1->key == str1); 65 66 /* Remove the collided entry and look again. */ 67 _mesa_hash_table_remove(ht, entry1); 68 entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2); 69 assert(entry2->key == str2); 70 71 /* Try inserting #2 again and make sure it gets overwritten */ 72 _mesa_hash_table_insert_pre_hashed(ht, bad_hash, str2, NULL); 73 entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2); 74 hash_table_foreach(ht, search_entry) { 75 assert(search_entry == entry2 || search_entry->key != str2); 76 } 77 78 /* Put str1 back, then spam junk into the table to force a 79 * resize and make sure we can still find them both. 80 */ 81 _mesa_hash_table_insert_pre_hashed(ht, bad_hash, str1, NULL); 82 for (i = 0; i < 100; i++) { 83 char *key = malloc(10); 84 sprintf(key, "spam%d", i); 85 _mesa_hash_table_insert_pre_hashed(ht, _mesa_hash_string(key), key, NULL); 86 } 87 entry1 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str1); 88 assert(entry1->key == str1); 89 entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2); 90 assert(entry2->key == str2); 91 92 _mesa_hash_table_destroy(ht, NULL); 93 94 return 0; 95 } 96