1441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Copyright (C) 2000, 2001, 2002 Red Hat, Inc. 2441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project Written by Ulrich Drepper <drepper@redhat.com>, 2000. 3441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 4441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project This program is Open Source software; you can redistribute it and/or 5441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project modify it under the terms of the Open Software License version 1.0 as 6441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project published by the Open Source Initiative. 7441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 8441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project You should have received a copy of the Open Software License along 9441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project with this program; if not, you may obtain a copy of the Open Software 10441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project License version 1.0 from http://www.opensource.org/licenses/osl.php or 11441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project by writing the Open Source Initiative c/o Lawrence Rosen, Esq., 12441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 3001 King Ranch Road, Ukiah, CA 95482. */ 13441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 14441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <assert.h> 15441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <stdlib.h> 16441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#include <system.h> 17441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 18441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project/* Before including this file the following macros must be defined: 19441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 20441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME name of the hash table structure. 21441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TYPE data type of the hash table entries 22441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project COMPARE comparison function taking two pointers to TYPE objects 23441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 24441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project The following macros if present select features: 25441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 26441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ITERATE iterating over the table entries is possible 27441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project REVERSE iterate in reverse order of insert 28441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project */ 29441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 30441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 31441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic size_t 32441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectlookup (htab, hval, val) 33441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 34441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int hval; 35441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TYPE val; 36441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 37441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* First hash function: simply take the modul but prevent zero. */ 38441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t idx = 1 + hval % htab->size; 39441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 40441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval != 0) 41441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 42441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int hash; 43441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 44441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval == hval 45441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project && COMPARE (htab->table[idx].data, val) == 0) 46441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return idx; 47441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 48441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Second hash function as suggested in [Knuth]. */ 49441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project hash = 1 + hval % (htab->size - 2); 50441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 51441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project do 52441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 53441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (idx <= hash) 54441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project idx = htab->size + idx - hash; 55441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 56441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project idx -= hash; 57441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 58441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* If entry is found use it. */ 59441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval == hval 60441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project && COMPARE (htab->table[idx].data, val) == 0) 61441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return idx; 62441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 63441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while (htab->table[idx].hashval); 64441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 65441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return idx; 66441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 67441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 68441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 69441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectstatic void 70441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectinsert_entry_2 (NAME *htab, unsigned long int hval, size_t idx, TYPE data) 71441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 72441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 73441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval == 0) 74441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 75441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# ifdef REVERSE 76441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table[idx].next = htab->first; 77441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->first = &htab->table[idx]; 78441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# else 79441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Add the new value to the list. */ 80441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->first == NULL) 81441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->first = htab->table[idx].next = &htab->table[idx]; 82441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 83441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 84441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table[idx].next = htab->first->next; 85441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->first = htab->first->next = &htab->table[idx]; 86441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 87441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# endif 88441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 89441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 90441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 91441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table[idx].hashval = hval; 92441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table[idx].data = data; 93441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 94441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project ++htab->filled; 95441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (100 * htab->filled > 90 * htab->size) 96441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 97441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Table is filled more than 90%. Resize the table. */ 98441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 99441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project __typeof__ (htab->first) first; 100441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# ifndef REVERSE 101441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project __typeof__ (htab->first) runp; 102441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# endif 103441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#else 104441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int old_size = htab->size; 105441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 106441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _TABLE(name) \ 107441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_ent *table = htab->table 108441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define TABLE(name) _TABLE (name) 109441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TABLE(NAME); 110441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 111441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->size = next_prime (htab->size * 2); 112441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->filled = 0; 113441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 114441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project first = htab->first; 115441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->first = NULL; 116441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 117441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table = calloc ((1 + htab->size), sizeof (htab->table[0])); 118441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table == NULL) 119441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 120441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We cannot enlarge the table. Live with what we got. This 121441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project might lead to an infinite loop at some point, though. */ 122441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table = table; 123441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return; 124441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 125441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 126441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Add the old entries to the new table. When iteration is 127441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project supported we maintain the order. */ 128441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 129441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# ifdef REVERSE 130441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while (first != NULL) 131441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 132441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project insert_entry_2 (htab, first->hashval, 133441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project lookup (htab, first->hashval, first->data), 134441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project first->data); 135441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 136441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project first = first->next; 137441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 138441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# else 139441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project assert (first != NULL); 140441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project runp = first = first->next; 141441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project do 142441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project insert_entry_2 (htab, runp->hashval, 143441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project lookup (htab, runp->hashval, runp->data), runp->data); 144441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project while ((runp = runp->next) != first); 145441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# endif 146441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#else 147441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project for (idx = 1; idx <= old_size; ++idx) 148441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (table[idx].hashval != 0) 149441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project insert_entry_2 (htab, table[idx].hashval, 150441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project lookup (htab, table[idx].hashval, table[idx].data), 151441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project table[idx].data); 152441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 153441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 154441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (table); 155441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 156441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 157441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 158441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 159441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectint 160441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define INIT(name) _INIT (name) 161441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _INIT(name) \ 162441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_init 163441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectINIT(NAME) (htab, init_size) 164441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 165441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int init_size; 166441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 167441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We need the size to be a prime. */ 168441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project init_size = next_prime (init_size); 169441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 170441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Initialize the data structure. */ 171441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->size = init_size; 172441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->filled = 0; 173441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 174441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->first = NULL; 175441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 176441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0])); 177441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table == NULL) 178441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return -1; 179441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 180441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 0; 181441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 182441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 183441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 184441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectint 185441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define FREE(name) _FREE (name) 186441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _FREE(name) \ 187441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_free 188441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectFREE(NAME) (htab) 189441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 190441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 191441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project free (htab->table); 192441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 0; 193441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 194441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 195441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 196441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectint 197441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define INSERT(name) _INSERT (name) 198441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _INSERT(name) \ 199441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_insert 200441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectINSERT(NAME) (htab, hval, data) 201441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 202441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int hval; 203441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TYPE data; 204441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 205441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t idx; 206441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 207441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make the hash value nonzero. */ 208441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project hval = hval ?: 1; 209441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 210441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project idx = lookup (htab, hval, data); 211441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 212441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval != 0) 213441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* We don't want to overwrite the old value. */ 214441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return -1; 215441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 216441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* An empty bucket has been found. */ 217441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project insert_entry_2 (htab, hval, idx, data); 218441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 0; 219441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 220441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 221441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 222441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef OVERWRITE 223441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Projectint 224441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define INSERT(name) _INSERT (name) 225441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _INSERT(name) \ 226441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_overwrite 227441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectINSERT(NAME) (htab, hval, data) 228441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 229441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int hval; 230441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TYPE data; 231441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 232441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t idx; 233441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 234441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make the hash value nonzero. */ 235441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project hval = hval ?: 1; 236441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 237441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project idx = lookup (htab, hval, data); 238441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 239441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* The correct bucket has been found. */ 240441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project insert_entry_2 (htab, hval, idx, data); 241441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return 0; 242441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 243441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 244441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 245441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 246441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectTYPE 247441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define FIND(name) _FIND (name) 248441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#define _FIND(name) \ 249441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_find 250441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectFIND(NAME) (htab, hval, val) 251441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 252441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project unsigned long int hval; 253441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project TYPE val; 254441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 255441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project size_t idx; 256441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 257441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Make the hash value nonzero. */ 258441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project hval = hval ?: 1; 259441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 260441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project idx = lookup (htab, hval, val); 261441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 262441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->table[idx].hashval == 0) 263441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 264441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 265441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return htab->table[idx].data; 266441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 267441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 268441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 269441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#ifdef ITERATE 270441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define ITERATEFCT(name) _ITERATEFCT (name) 271441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define _ITERATEFCT(name) \ 272441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project name##_iterate 273441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectTYPE 274441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source ProjectITERATEFCT(NAME) (htab, ptr) 275441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project NAME *htab; 276441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project void **ptr; 277441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project{ 278441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project void *p = *ptr; 279441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 280441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define TYPENAME(name) _TYPENAME (name) 281441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# define _TYPENAME(name) name##_ent 282441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 283441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# ifdef REVERSE 284441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (p == NULL) 285441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project p = htab->first; 286441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 287441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project p = ((TYPENAME(NAME) *) p)->next; 288441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 289441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (p == NULL) 290441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 291441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project *ptr = NULL; 292441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 293441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 294441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# else 295441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (p == NULL) 296441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 297441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (htab->first == NULL) 298441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 299441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project p = htab->first->next; 300441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 301441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project else 302441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project { 303441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project if (p == htab->first) 304441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return NULL; 305441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 306441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project p = ((TYPENAME(NAME) *) p)->next; 307441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project } 308441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project# endif 309441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 310441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project /* Prepare the next element. If possible this will pull the data 311441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project into the cache, for reading. */ 312441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2); 313441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project 314441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project return ((TYPENAME(NAME) *) (*ptr = p))->data; 315441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project} 316441f72d43a9b550baa779fc82f70816da5f74f0eThe Android Open Source Project#endif 317