tools/nc_threads/nc_hash.c

   1 /*
   2  * Copyright 2008, Google Inc.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  *     * Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *     * Redistributions in binary form must reproduce the above
  12  * copyright notice, this list of conditions and the following disclaimer
  13  * in the documentation and/or other materials provided with the
  14  * distribution.
  15  *     * Neither the name of Google Inc. nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32
  33 /*
  34  * A hash table for pthreads library
  35  */
  36
  37 #include <unistd.h>
  38 #include "nc_hash.h"
  39 #include "pthread.h"
  40
  41 static uint32_t hash_get_bucket_id(struct NaClHashTable *table,
  42                                    uint32_t id)
  43 {
  44   return id % table->number_of_buckets;
  45 }
  46
  47 int __nacl_hash_init(struct NaClHashTable *table)
  48 {
  49   uint32_t i = 0;
  50
  51   table->number_of_buckets = sizeof(table->buckets) / sizeof(table->buckets[0]);
  52   for (i = 0; i < table->number_of_buckets; ++i) {
  53     LIST_INIT(&table->buckets[i]);
  54   }
  55   return 1;
  56 }
  57
  58 void __nacl_hash_destroy(struct NaClHashTable *table)
  59 {
  60   /*
  61    * Nothing to free - everything is static
  62    * TODO: what do we do when there
  63    * are still some entries in the table?
  64    */
  65 }
  66
  67 int __nacl_hash_insert_mu(struct NaClHashTable *table,
  68                           nc_hash_entry_t *entry)
  69 {
  70   uint32_t bucket_id = hash_get_bucket_id(table, entry->id_function(entry));
  71   LIST_INSERT_HEAD(&table->buckets[bucket_id], entry, list_entries);
  72   return 0;
  73 }
  74
  75 nc_hash_entry_t *__nacl_hash_find_id_mu(struct NaClHashTable *table,
  76                                         uint32_t id)
  77 {
  78   uint32_t bucket_id = hash_get_bucket_id(table, id);
  79   nc_hash_entry_t *iter;
  80   LIST_FOREACH(iter, &table->buckets[bucket_id], list_entries) {
  81     if (iter->id_function(iter) == id) {
  82       return iter;
  83     }
  84   }
  85   return NULL;
  86 }
  87
  88 int __nacl_hash_id_exists_mu(struct NaClHashTable *table,
  89                              uint32_t id)
  90 {
  91   if (NULL == __nacl_hash_find_id_mu(table, id)) {
  92     return 0;
  93   }
  94   return 1;
  95 }
  96
  97 nc_hash_entry_t *__nacl_hash_remove_mu(struct NaClHashTable  *table,
  98                                        uint32_t id)
  99 {
 100   uint32_t bucket_id = hash_get_bucket_id(table, id);
 101   nc_hash_entry_t *iter;
 102   LIST_FOREACH(iter, &table->buckets[bucket_id], list_entries) {
 103     if (iter->id_function(iter) == id) {
 104       LIST_REMOVE(iter, list_entries);
 105       return iter;
 106     }
 107   }
 108   return NULL;
 109 }