hash.h revision 64339d36f8bd4db5025fe2988eda22b491a9219c
164339d36f8bd4db5025fe2988eda22b491a9219cFredrik Roubert// Copyright (C) 2016 and later: Unicode, Inc. and others. 264339d36f8bd4db5025fe2988eda22b491a9219cFredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html 3b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/* 4b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 51b7d32f919554dda9c193b32188251337bc756f1Fredrik Roubert* Copyright (C) 1997-2014, International Business Machines 6b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* Corporation and others. All Rights Reserved. 7b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 8b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* Date Name Description 9b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru* 03/28/00 aliu Creation. 10b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru****************************************************************************** 11b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru*/ 12b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 13b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#ifndef HASH_H 14b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#define HASH_H 15b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 16b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "unicode/unistr.h" 17b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "unicode/uobject.h" 1883a171d1a62abf406f7f44ae671823d5ec20db7dCraig Cornelius#include "cmemory.h" 19b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "uhash.h" 20b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 21b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_NAMESPACE_BEGIN 22b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 23b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/** 24b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Hashtable is a thin C++ wrapper around UHashtable, a general-purpose void* 25b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * hashtable implemented in C. Hashtable is designed to be idiomatic and 26b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * easy-to-use in C++. 27b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * 28b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Hashtable is an INTERNAL CLASS. 29b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 30b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruclass U_COMMON_API Hashtable : public UMemory { 31b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashtable* hash; 32b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UHashtable hashObj; 33b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 34b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru inline void init(UHashFunction *keyHash, UKeyComparator *keyComp, UValueComparator *valueComp, UErrorCode& status); 35b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 36b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 37b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /** 38b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Construct a hashtable 39b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * @param ignoreKeyCase If true, keys are case insensitive. 40b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * @param status Error code 41b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 42b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable(UBool ignoreKeyCase, UErrorCode& status); 43b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 44b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /** 45b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Construct a hashtable 4650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho * @param keyComp Comparator for comparing the keys 4750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho * @param valueComp Comparator for comparing the values 48b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * @param status Error code 49b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 50b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable(UKeyComparator *keyComp, UValueComparator *valueComp, UErrorCode& status); 51b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 52b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /** 53b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Construct a hashtable 54b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * @param status Error code 55b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 56b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable(UErrorCode& status); 57b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 58b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /** 59b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Construct a hashtable, _disregarding any error_. Use this constructor 60b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * with caution. 61b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 62b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable(); 63b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 64b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /** 65b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Non-virtual destructor; make this virtual if Hashtable is subclassed 66b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * in the future. 67b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru */ 68b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ~Hashtable(); 69b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 70b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UObjectDeleter *setValueDeleter(UObjectDeleter *fn); 71b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 72b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t count() const; 73b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 74b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* put(const UnicodeString& key, void* value, UErrorCode& status); 75b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 76b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t puti(const UnicodeString& key, int32_t value, UErrorCode& status); 77b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 78b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* get(const UnicodeString& key) const; 79b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 80b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t geti(const UnicodeString& key) const; 81b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 82b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void* remove(const UnicodeString& key); 83b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 84b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru int32_t removei(const UnicodeString& key); 85b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 86b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void removeAll(void); 87b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 88b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement* find(const UnicodeString& key) const; 89b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 901b7d32f919554dda9c193b32188251337bc756f1Fredrik Roubert /** 911b7d32f919554dda9c193b32188251337bc756f1Fredrik Roubert * @param pos - must be UHASH_FIRST on first call, and untouched afterwards. 921b7d32f919554dda9c193b32188251337bc756f1Fredrik Roubert * @see uhash_nextElement 931b7d32f919554dda9c193b32188251337bc756f1Fredrik Roubert */ 94b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const UHashElement* nextElement(int32_t& pos) const; 95b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 9650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho UKeyComparator* setKeyComparator(UKeyComparator*keyComp); 97b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 9850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho UValueComparator* setValueComparator(UValueComparator* valueComp); 99b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 100b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UBool equals(const Hashtable& that) const; 101b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 102b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable(const Hashtable &other); // forbid copying of this class 103b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Hashtable &operator=(const Hashtable &other); // forbid copying of this class 104b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 105b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 106b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/********************************************************************* 107b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru * Implementation 108b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ********************************************************************/ 109b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 110b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline void Hashtable::init(UHashFunction *keyHash, UKeyComparator *keyComp, 111b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UValueComparator *valueComp, UErrorCode& status) { 112b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_FAILURE(status)) { 113b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return; 114b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 115b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uhash_init(&hashObj, keyHash, keyComp, valueComp, &status); 116b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (U_SUCCESS(status)) { 117b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru hash = &hashObj; 11883a171d1a62abf406f7f44ae671823d5ec20db7dCraig Cornelius uhash_setKeyDeleter(hash, uprv_deleteUObject); 119b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 120b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 121b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 122b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline Hashtable::Hashtable(UKeyComparator *keyComp, UValueComparator *valueComp, 123b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode& status) : hash(0) { 124b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru init( uhash_hashUnicodeString, keyComp, valueComp, status); 125b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 126b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline Hashtable::Hashtable(UBool ignoreKeyCase, UErrorCode& status) 127b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : hash(0) 128b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 129b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru init(ignoreKeyCase ? uhash_hashCaselessUnicodeString 130b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : uhash_hashUnicodeString, 131b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ignoreKeyCase ? uhash_compareCaselessUnicodeString 132b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : uhash_compareUnicodeString, 133b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru NULL, 134b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru status); 135b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 136b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 137b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline Hashtable::Hashtable(UErrorCode& status) 138b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : hash(0) 139b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 140b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru init(uhash_hashUnicodeString, uhash_compareUnicodeString, NULL, status); 141b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 142b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 143b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline Hashtable::Hashtable() 144b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : hash(0) 145b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru{ 146b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UErrorCode status = U_ZERO_ERROR; 147b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru init(uhash_hashUnicodeString, uhash_compareUnicodeString, NULL, status); 148b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 149b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 150b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline Hashtable::~Hashtable() { 151b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (hash != NULL) { 152b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uhash_close(hash); 153b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 154b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 155b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 156b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline UObjectDeleter *Hashtable::setValueDeleter(UObjectDeleter *fn) { 157b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_setValueDeleter(hash, fn); 158b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 159b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 160b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline int32_t Hashtable::count() const { 161b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_count(hash); 162b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 163b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 164b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline void* Hashtable::put(const UnicodeString& key, void* value, UErrorCode& status) { 165b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_put(hash, new UnicodeString(key), value, &status); 166b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 167b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 168b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline int32_t Hashtable::puti(const UnicodeString& key, int32_t value, UErrorCode& status) { 169b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_puti(hash, new UnicodeString(key), value, &status); 170b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 171b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 172b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline void* Hashtable::get(const UnicodeString& key) const { 173b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_get(hash, &key); 174b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 175b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 176b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline int32_t Hashtable::geti(const UnicodeString& key) const { 177b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_geti(hash, &key); 178b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 179b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 180b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline void* Hashtable::remove(const UnicodeString& key) { 181b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_remove(hash, &key); 182b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 183b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 184b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline int32_t Hashtable::removei(const UnicodeString& key) { 185b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_removei(hash, &key); 186b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 187b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 188b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline const UHashElement* Hashtable::find(const UnicodeString& key) const { 189b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_find(hash, &key); 190b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 191b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 192b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline const UHashElement* Hashtable::nextElement(int32_t& pos) const { 193b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_nextElement(hash, &pos); 194b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 195b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 196b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline void Hashtable::removeAll(void) { 197b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru uhash_removeAll(hash); 198b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 199b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 20050294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoinline UKeyComparator* Hashtable::setKeyComparator(UKeyComparator*keyComp){ 201b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_setKeyComparator(hash, keyComp); 202b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 203b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 20450294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoinline UValueComparator* Hashtable::setValueComparator(UValueComparator* valueComp){ 205b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_setValueComparator(hash, valueComp); 206b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 207b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 208b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruinline UBool Hashtable::equals(const Hashtable& that)const{ 209b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return uhash_equals(hash, that.hash); 210b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 211b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruU_NAMESPACE_END 212b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 213b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#endif 214b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 215