VNFs/DPPD-PROX/hash_set.c

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //     http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 */
  16
  17 #include <rte_hash_crc.h>
  18 #include <string.h>
  19
  20 #include "prox_malloc.h"
  21 #include "prox_assert.h"
  22 #include "hash_set.h"
  23
  24 #define HASH_SET_ALLOC_CHUNCK 1024
  25 #define HASH_SET_ALLOC_CHUNCK_MEM (sizeof(struct hash_set_entry) * 1024)
  26
  27 struct hash_set_entry {
  28         uint32_t              crc;
  29         void                  *data;
  30         size_t                len;
  31         struct hash_set_entry *next;
  32 };
  33
  34 struct hash_set {
  35         uint32_t              n_buckets;
  36         int                   socket_id;
  37         struct hash_set_entry *alloc;
  38         size_t                alloc_count;
  39         struct hash_set_entry *mem[0];
  40 };
  41
  42 static struct hash_set_entry *hash_set_alloc_entry(struct hash_set *hs)
  43 {
  44         struct hash_set_entry *ret;
  45
  46         if (hs->alloc_count == 0) {
  47                 size_t mem_size = HASH_SET_ALLOC_CHUNCK *
  48                         sizeof(struct hash_set_entry);
  49
  50                 hs->alloc = prox_zmalloc(mem_size, hs->socket_id);
  51                 hs->alloc_count = HASH_SET_ALLOC_CHUNCK;
  52         }
  53
  54         ret = hs->alloc;
  55         hs->alloc++;
  56         hs->alloc_count--;
  57         return ret;
  58 }
  59
  60 struct hash_set *hash_set_create(uint32_t n_buckets, int socket_id)
  61 {
  62         struct hash_set *ret;
  63         size_t mem_size = sizeof(*ret) + sizeof(ret->mem[0]) * n_buckets;
  64
  65         ret = prox_zmalloc(mem_size, socket_id);
  66         ret->n_buckets = n_buckets;
  67         ret->socket_id = socket_id;
  68
  69         return ret;
  70 }
  71
  72 void *hash_set_find(struct hash_set *hs, void *data, size_t len)
  73 {
  74         uint32_t crc = rte_hash_crc(data, len, 0);
  75
  76         struct hash_set_entry *entry = hs->mem[crc % hs->n_buckets];
  77
  78         while (entry) {
  79                 if (entry->crc == crc && entry->len == len &&
  80                     memcmp(entry->data, data, len) == 0)
  81                         return entry->data;
  82                 entry = entry->next;
  83         }
  84         return NULL;
  85 }
  86
  87 void hash_set_add(struct hash_set *hs, void *data, size_t len)
  88 {
  89         uint32_t crc = rte_hash_crc(data, len, 0);
  90         struct hash_set_entry *new = hash_set_alloc_entry(hs);
  91
  92         new->data = data;
  93         new->len = len;
  94         new->crc = crc;
  95
  96         if (hs->mem[crc % hs->n_buckets]) {
  97                 struct hash_set_entry *entry = hs->mem[crc % hs->n_buckets];
  98                 while (entry->next)
  99                         entry = entry->next;
 100                 entry->next = new;
 101         }
 102         else {
 103                 hs->mem[crc % hs->n_buckets] = new;
 104         }
 105 }