lib/libc/sysvipc/sysvipc_hash.c

   1 /*-
   2  * Copyright (c) 2013 Larisa Grigore<larisagrigore@gmail.com>
   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
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29 #include <errno.h>
  30
  31 #include "sysvipc_hash.h"
  32
  33 struct hashtable *
  34 _hash_init(int nr_elems)
  35 {
  36         long hashsize;
  37         struct hashtable *hashtable;
  38         int i;
  39
  40         if (nr_elems <= 0)
  41                 return NULL;
  42         for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1)
  43                 continue;
  44
  45         hashtable = malloc(sizeof(struct hashtable));
  46         if (!hashtable) {
  47                 return NULL;
  48         }
  49
  50         hashtable->entries = malloc(hashsize * sizeof(struct entries_list));
  51         if (!hashtable->entries) {
  52                 free(hashtable);
  53                 hashtable = NULL;
  54                 goto out;
  55         }
  56
  57         hashtable->nr_elems = hashsize;
  58
  59         for (i = 0; i < hashsize; i++)
  60                 LIST_INIT(&hashtable->entries[i]);
  61
  62 out:
  63         return hashtable;
  64 }
  65
  66 int
  67 _hash_destroy(struct hashtable *hashtable)
  68 {
  69         struct entries_list *tmp;
  70         u_long hashmask = hashtable->nr_elems -1;
  71
  72         for (tmp = &hashtable->entries[0]; tmp <= &hashtable->entries[hashmask]; tmp++) {
  73                 if (!LIST_EMPTY(tmp))
  74                         return -1;
  75         }
  76         free(hashtable->entries);
  77         free(hashtable);
  78         hashtable = NULL;
  79         return 0;
  80 }
  81
  82 void
  83 _hash_insert(struct hashtable *hashtable, u_long key, void *value)
  84 {
  85
  86         u_long hashmask = hashtable->nr_elems -1;
  87         struct entries_list *list =
  88                 &hashtable->entries[key & hashmask];
  89         struct hashentry *new_entry = malloc(sizeof(struct hashentry));
  90         new_entry->value = value;
  91         new_entry->key = key;
  92         LIST_INSERT_HEAD(list, new_entry, entry_link);
  93 }
  94
  95 void *
  96 _hash_lookup(struct hashtable *hashtable, u_long key)
  97 {
  98
  99         u_long hashmask = hashtable->nr_elems -1;
 100         struct entries_list *list =
 101                 &hashtable->entries[key & hashmask];
 102         struct hashentry *tmp;
 103
 104         LIST_FOREACH(tmp, list, entry_link) {
 105                 if (tmp->key == key) {
 106                         return tmp->value;
 107                 }
 108         }
 109
 110         return NULL;
 111 }
 112
 113 void *
 114 _hash_remove(struct hashtable *hashtable, u_long key)
 115 {
 116
 117         void *value;
 118         u_long hashmask = hashtable->nr_elems -1;
 119         struct entries_list *list =
 120                 &hashtable->entries[key & hashmask];
 121         struct hashentry *tmp;
 122
 123         LIST_FOREACH(tmp, list, entry_link) {
 124                 if (tmp->key == key)
 125                         goto done;
 126         }
 127
 128         return NULL;
 129
 130 done:
 131         LIST_REMOVE(tmp, entry_link);
 132         value = tmp->value;
 133         free(tmp);
 134         return value;
 135 }
 136
 137 int
 138 get_hash_size(int nr_elems)
 139 {
 140         long hashsize = 0;
 141
 142         for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1)
 143                 continue;
 144
 145         return hashsize;
 146 }