13a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/************************************************************************** 23a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 33a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas. 43a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * All Rights Reserved. 53a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 63a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 73a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * copy of this software and associated documentation files (the 83a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * "Software"), to deal in the Software without restriction, including 93a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * without limitation the rights to use, copy, modify, merge, publish, 103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * distribute, sub license, and/or sell copies of the Software, and to 113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * permit persons to whom the Software is furnished to do so, subject to 123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the following conditions: 133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * The above copyright notice and this permission notice (including the 153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * next paragraph) shall be included in all copies or substantial portions 163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * of the Software. 173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR 223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org **************************************************************************/ 273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * @file 303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Hash table implementation. 313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * This file provides a hash implementation that is capable of dealing 333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * with collisions. It stores colliding entries in linked list. All 343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * functions operating on the hash return an iterator. The iterator 353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * itself points to the collision list. If there wasn't any collision 363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the list will have just one entry, otherwise client code should 373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * iterate over the entries to find the exact entry among ones that 383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * had the same key (e.g. memcmp could be used on the data to check 393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * that) 403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * @author Zack Rusin <zack@tungstengraphics.com> 423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#ifndef CSO_HASH_H 453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define CSO_HASH_H 463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "pipe/p_compiler.h" 483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#ifdef __cplusplus 503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgextern "C" { 513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash; 553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_node; 563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter { 593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash *hash; 603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *node; 613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash *cso_hash_create(void); 653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid cso_hash_delete(struct cso_hash *hash); 663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgint cso_hash_size(struct cso_hash *hash); 693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Adds a data with the given key to the hash. If entry with the given 733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * key is already in the hash, this current entry is instered before it 743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * in the collision list. 753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Function returns iterator pointing to the inserted item in the hash. 763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_insert(struct cso_hash *hash, unsigned key, 783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org void *data); 793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Removes the item pointed to by the current iterator from the hash. 813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Note that the data itself is not erased and if it was a malloc'ed pointer 823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * it will have to be freed after calling this function by the callee. 833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Function returns iterator pointing to the item after the removed one in 843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the hash. 853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter); 873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid *cso_hash_take(struct cso_hash *hash, unsigned key); 893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_first_node(struct cso_hash *hash); 933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Return an iterator pointing to the first entry in the collision list. 963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_find(struct cso_hash *hash, unsigned key); 983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Returns true if a value with the given key exists in the hash 1013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgboolean cso_hash_contains(struct cso_hash *hash, unsigned key); 1033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgint cso_hash_iter_is_null(struct cso_hash_iter iter); 1063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned cso_hash_iter_key(struct cso_hash_iter iter); 1073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid *cso_hash_iter_data(struct cso_hash_iter iter); 1083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter); 1113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter); 1123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Convenience routine to iterate over the collision list while doing a memory 1163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * comparison to see which entry in the list is a direct copy of our template 1173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * and returns that entry. 1183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid *cso_hash_find_data_from_template( struct cso_hash *hash, 1203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned hash_key, 1213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org void *templ, 1223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int size ); 1233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#ifdef __cplusplus 1263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 1283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 130