14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*---------------------------------------------------------------------------* 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * phashtable.c * 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Copyright 2007, 2008 Nuance Communciations, Inc. * 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the 'License'); * 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * you may not use this file except in compliance with the License. * 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * You may obtain a copy of the License at * 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 * 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Unless required by applicable law or agreed to in writing, software * 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * distributed under the License is distributed on an 'AS IS' BASIS, * 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * See the License for the specific language governing permissions and * 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * limitations under the License. * 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *---------------------------------------------------------------------------*/ 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <string.h> 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "phashtable.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "plog.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "pmemory.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "pstdio.h" 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//extern int strcmp(const char * s1, const char * s2); 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define ALLOC_SIZE 16 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct PHashTableEntry_t 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *key; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *value; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTable *table; 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int idx; 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *next; 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *prev; 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode; 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef struct PHashTableEntryBlock_t 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry entries[ALLOC_SIZE]; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct PHashTableEntryBlock_t *next; 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectPHashTableEntryBlock; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct PHashTable_t 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableArgs args; 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const LCHAR *memoryTag; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int size; 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project float maxLoadFactor; 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry **entries; 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int threshold; 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *freeList; 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntryBlock *entryBlock; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "pcrc.h" 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic unsigned int hashString(const void *key) 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ~pcrcComputeString(key); 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableCreate(PHashTableArgs *args, 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const LCHAR *memTag, 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTable **table) 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTable *tmp; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int i; 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (args != NULL && args->maxLoadFactor <= 0.0)) 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((tmp = NEW(PHashTable, memTag)) == NULL) 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_OUT_OF_MEMORY; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (args == NULL) 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.capacity = PHASH_TABLE_DEFAULT_CAPACITY; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.maxLoadFactor = PHASH_TABLE_DEFAULT_MAX_LOAD_FACTOR; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.hashFunction = PHASH_TABLE_DEFAULT_HASH_FUNCTION; 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.compFunction = PHASH_TABLE_DEFAULT_COMP_FUNCTION; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project memcpy(&tmp->args, args, sizeof(PHashTableArgs)); 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (tmp->args.hashFunction == PHASH_TABLE_DEFAULT_HASH_FUNCTION) 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.hashFunction = hashString; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (tmp->args.compFunction == PHASH_TABLE_DEFAULT_COMP_FUNCTION) 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->args.compFunction = LSTRCMP; 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->entries = NEW_ARRAY(PHashTableEntry *, tmp->args.capacity, memTag); 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (tmp->entries == NULL) 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE(tmp); 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_OUT_OF_MEMORY; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = tmp->args.capacity; i > 0;) 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->entries[--i] = NULL; 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->memoryTag = memTag; 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->size = 0; 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->threshold = (unsigned int)(tmp->args.capacity * tmp->args.maxLoadFactor); 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->freeList = NULL; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->entryBlock = NULL; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *table = tmp; 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableDestroy(PHashTable *table) 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntryBlock *tmp, *block; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL) 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block = table->entryBlock; 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (block != NULL) 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp = block->next; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE(block); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block = tmp; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE(table->entries); 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE(table); 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableGetSize(PHashTable *table, 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_t *size) 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || size == NULL) 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *size = table->size; 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PHashTableEntry *getEntry(PHashTable *table, 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *key, 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode, 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int idx) 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *entry = table->entries[idx]; 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (key == NULL) 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (entry != NULL) 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->key == NULL) 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return entry; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = entry->next; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (entry != NULL) 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->hashCode == hashCode && table->args.compFunction(key, entry->key) == 0) 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return entry; 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = entry->next; 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return NULL; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic void removeEntry(PHashTableEntry *entry) 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->prev == NULL) 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->table->entries[entry->idx] = entry->next; 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->prev->next = entry->next; 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->next != NULL) 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next->prev = entry->prev; 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->table->size--; 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next = entry->table->freeList; 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->table->freeList = entry; 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* clean up entry for re-use. */ 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->key = entry->value = NULL; 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableGetValue(PHashTable *table, const void *key, void **value) 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *entry; 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode; 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int idx; 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || value == NULL) 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashCode = table->args.hashFunction(key); 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = hashCode % table->args.capacity; 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((entry = getEntry(table, key, hashCode, idx)) != NULL) 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *value = (void *) entry->value; 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *value = NULL; 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_NO_MATCH_ERROR; 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableContainsKey(PHashTable *table, const void *key, ESR_BOOL* exists) 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ESR_ReturnCode rc; 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry* entry; 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || exists == NULL) 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rc = ESR_INVALID_ARGUMENT; 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PLogError(ESR_rc2str(rc)); 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project goto CLEANUP; 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rc = PHashTableGetEntry(table, key, &entry); 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (rc == ESR_SUCCESS) 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *exists = ESR_TRUE; 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (rc == ESR_NO_MATCH_ERROR) 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *exists = ESR_FALSE; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project goto CLEANUP; 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectCLEANUP: 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return rc; 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableGetEntry(PHashTable *table, const void *key, PHashTableEntry **entry) 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode; 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int idx; 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry* result; 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || entry == NULL) 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashCode = table->args.hashFunction(key); 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = hashCode % table->args.capacity; 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project result = getEntry(table, key, hashCode, idx); 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (result == NULL) 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_NO_MATCH_ERROR; 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *entry = result; 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic ESR_ReturnCode PHashTableRehash(PHashTable *table) 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int i, idx; 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int oldCapacity = table->args.capacity; 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int newCapacity = ((oldCapacity << 1) | 0x01); 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *entry, *tmp, *next; 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry **newEntries = 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (PHashTableEntry **) 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project REALLOC(table->entries, 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sizeof(PHashTableEntry *) * newCapacity); 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (newEntries == NULL) 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_OUT_OF_MEMORY; 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entries = newEntries; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->args.capacity = newCapacity; 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->threshold = (unsigned int)(newCapacity * table->args.maxLoadFactor); 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = oldCapacity; i < newCapacity; ++i) 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entries[i] = NULL; 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < oldCapacity; i++) 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (entry = table->entries[i]; entry != NULL;) 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = entry->hashCode % newCapacity; 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (idx != i) 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Need to change location. */ 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->idx = idx; 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project next = entry->next; 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->prev != NULL) 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->prev->next = next; 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entries[i] = next; 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (next != NULL) 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project next->prev = entry->prev; 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp = table->entries[idx]; 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next = tmp; 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->prev = NULL; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (tmp != NULL) 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tmp->prev = entry; 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entries[idx] = entry; 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = next; 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Already in the right slot. */ 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = entry->next; 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTablePutValue(PHashTable *table, 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *key, 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *value, 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void **oldValue) 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ESR_ReturnCode rc = ESR_SUCCESS; 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode, idx; 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *entry; 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL) return ESR_INVALID_ARGUMENT; 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashCode = table->args.hashFunction(key); 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = hashCode % table->args.capacity; 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = getEntry(table, key, hashCode, idx); 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry != NULL) 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (oldValue != NULL) *oldValue = (void *) entry->value; 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->value = value; 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* If we get here, we need to add a new entry. But first, verify if we need 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project to rehash. */ 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table->size >= table->threshold) 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((rc = PHashTableRehash(table)) != ESR_SUCCESS) 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return rc; 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = hashCode % table->args.capacity; 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table->freeList == NULL) 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Allocate a new block and put all entries on the free list. */ 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntryBlock *block; 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int i; 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block = NEW(PHashTableEntryBlock, table->memoryTag); 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (block == NULL) 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_OUT_OF_MEMORY; 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block->next = table->entryBlock; 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entryBlock = block; 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < ALLOC_SIZE - 1; ++i) 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block->entries[i].next = &block->entries[i+1]; 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project block->entries[ALLOC_SIZE-1].next = NULL; 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* do not see any bug in following code. But on the VxWorks with optimization option -O3 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project it produces wrong result: block->entries[0].next is correct but block->entries[1].next = NULL 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project it causes lot of memory wastes. 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0, entry = block->entries; i < ALLOC_SIZE - 1; ++i, ++entry) 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next = entry+1; 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next = table->freeList; 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->freeList = block->entries; 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Get an entry from the freeList. */ 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = table->freeList; 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->freeList = entry->next; 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Initialize entry data structure. */ 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->table = table; 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->idx = idx; 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->key = key; 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->value = value; 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->hashCode = hashCode; 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next = table->entries[idx]; 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->prev = NULL; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry->next != NULL) 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->next->prev = entry; 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->entries[idx] = entry; 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project table->size++; 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (oldValue != NULL) *oldValue = NULL; 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableRemoveValue(PHashTable *table, 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *key, 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void **oldValue) 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashCode, idx; 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PHashTableEntry *entry; 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ESR_ReturnCode rc; 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL) 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project rc = ESR_INVALID_ARGUMENT; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project PLogError(ESR_rc2str(rc)); 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project goto CLEANUP; 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashCode = table->args.hashFunction(key); 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = hashCode % table->args.capacity; 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = getEntry(table, key, hashCode, idx); 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry != NULL) 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (oldValue != NULL) 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *oldValue = (void*) entry->value; 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project removeEntry(entry); 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (oldValue != NULL) 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *oldValue = NULL; 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectCLEANUP: 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return rc; 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableEntryGetKeyValue(PHashTableEntry *entry, 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void **key, 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void **value) 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry == NULL) return ESR_INVALID_ARGUMENT; 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (key != NULL) *key = (void *) entry->key; 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (value != NULL) *value = (void *) entry->value; 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/** 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Sets the value associated with this entry. 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param entry The hashtable entry. 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param value The value to associate with the entry. 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param oldvalue If this pointer is non-NULL, it will be set to the previous value associated with this entry. 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project **/ 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableEntrySetValue(PHashTableEntry *entry, 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const void *value, 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void **oldValue) 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry == NULL) return ESR_INVALID_ARGUMENT; 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (oldValue != NULL) *oldValue = (void *) entry->value; 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry->value = value; 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/** 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Removes the entry from its hash table. 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param entry The hashtable entry. 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project **/ 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableEntryRemove(PHashTableEntry *entry) 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry == NULL) 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project removeEntry(entry); 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PHashTableEntry* iteratorAdvance(PHashTable *table, PHashTableEntry *entry) 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int idx; 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry != NULL) 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project idx = entry->idx; 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = entry->next; 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry == NULL) 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (++idx < table->args.capacity) 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table->entries[idx] != NULL) 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = table->entries[idx]; 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (idx = 0; idx < table->args.capacity; ++idx) 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table->entries[idx] != NULL) 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project entry = table->entries[idx]; 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return entry; 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableEntryGetFirst(PHashTable *table, PHashTableEntry **entry) 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (table == NULL || entry == NULL) 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *entry = iteratorAdvance(table, NULL); 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/** 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Iterates on the next key and value. Returns a NULL key when at the end of the hash table. 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param iter The iterator on which the iteration is performed. 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param key Returns the key associated with the entry, cannot be NULL. 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * @param value If non-NULL, returns the value associated with the entry. 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project **/ 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectESR_ReturnCode PHashTableEntryAdvance(PHashTableEntry **entry) 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (entry == NULL || *entry == NULL) 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_INVALID_ARGUMENT; 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *entry = iteratorAdvance((*entry)->table, *entry); 5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return ESR_SUCCESS; 5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 561