1/*****************************************************************************
2
3Copyright (c) 2007, 2016, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/**************************************************//**
20@file ha/ha0storage.cc
21Hash storage.
22Provides a data structure that stores chunks of data in
23its own storage, avoiding duplicates.
24
25Created September 22, 2007 Vasil Dimov
26*******************************************************/
27
28#include "ha_prototypes.h"
29#include "ha0storage.h"
30#include "hash0hash.h"
31#include "mem0mem.h"
32#include "ut0rnd.h"
33
34/*******************************************************************//**
35Retrieves a data from a storage. If it is present, a pointer to the
36stored copy of data is returned, otherwise NULL is returned. */
37static
38const void*
39ha_storage_get(
40/*===========*/
41 ha_storage_t* storage, /*!< in: hash storage */
42 const void* data, /*!< in: data to check for */
43 ulint data_len) /*!< in: data length */
44{
45 ha_storage_node_t* node;
46 ulint fold;
47
48 /* avoid repetitive calls to ut_fold_binary() in the HASH_SEARCH
49 macro */
50 fold = ut_fold_binary(static_cast<const byte*>(data), data_len);
51
52#define IS_FOUND \
53 node->data_len == data_len && memcmp(node->data, data, data_len) == 0
54
55 HASH_SEARCH(
56 next, /* node->"next" */
57 storage->hash, /* the hash table */
58 fold, /* key */
59 ha_storage_node_t*, /* type of node->next */
60 node, /* auxiliary variable */
61 , /* assertion */
62 IS_FOUND); /* search criteria */
63
64 if (node == NULL) {
65
66 return(NULL);
67 }
68 /* else */
69
70 return(node->data);
71}
72
73/*******************************************************************//**
74Copies data into the storage and returns a pointer to the copy. If the
75same data chunk is already present, then pointer to it is returned.
76Data chunks are considered to be equal if len1 == len2 and
77memcmp(data1, data2, len1) == 0. If "data" is not present (and thus
78data_len bytes need to be allocated) and the size of storage is going to
79become more than "memlim" then "data" is not added and NULL is returned.
80To disable this behavior "memlim" can be set to 0, which stands for
81"no limit". */
82const void*
83ha_storage_put_memlim(
84/*==================*/
85 ha_storage_t* storage, /*!< in/out: hash storage */
86 const void* data, /*!< in: data to store */
87 ulint data_len, /*!< in: data length */
88 ulint memlim) /*!< in: memory limit to obey */
89{
90 void* raw;
91 ha_storage_node_t* node;
92 const void* data_copy;
93 ulint fold;
94
95 /* check if data chunk is already present */
96 data_copy = ha_storage_get(storage, data, data_len);
97 if (data_copy != NULL) {
98
99 return(data_copy);
100 }
101
102 /* not present */
103
104 /* check if we are allowed to allocate data_len bytes */
105 if (memlim > 0
106 && ha_storage_get_size(storage) + data_len > memlim) {
107
108 return(NULL);
109 }
110
111 /* we put the auxiliary node struct and the data itself in one
112 continuous block */
113 raw = mem_heap_alloc(storage->heap,
114 sizeof(ha_storage_node_t) + data_len);
115
116 node = (ha_storage_node_t*) raw;
117 data_copy = (byte*) raw + sizeof(*node);
118
119 memcpy((byte*) raw + sizeof(*node), data, data_len);
120
121 node->data_len = data_len;
122 node->data = data_copy;
123
124 /* avoid repetitive calls to ut_fold_binary() in the HASH_INSERT
125 macro */
126 fold = ut_fold_binary(static_cast<const byte*>(data), data_len);
127
128 HASH_INSERT(
129 ha_storage_node_t, /* type used in the hash chain */
130 next, /* node->"next" */
131 storage->hash, /* the hash table */
132 fold, /* key */
133 node); /* add this data to the hash */
134
135 /* the output should not be changed because it will spoil the
136 hash table */
137 return(data_copy);
138}
139
140#ifdef UNIV_COMPILE_TEST_FUNCS
141
142void
143test_ha_storage()
144{
145 ha_storage_t* storage;
146 char buf[1024];
147 int i;
148 const void* stored[256];
149 const void* p;
150
151 storage = ha_storage_create(0, 0);
152
153 for (i = 0; i < 256; i++) {
154
155 memset(buf, i, sizeof(buf));
156 stored[i] = ha_storage_put(storage, buf, sizeof(buf));
157 }
158
159 //ha_storage_empty(&storage);
160
161 for (i = 255; i >= 0; i--) {
162
163 memset(buf, i, sizeof(buf));
164 p = ha_storage_put(storage, buf, sizeof(buf));
165
166 if (p != stored[i]) {
167 ib::warn() << "ha_storage_put() returned " << p
168 << " instead of " << stored[i] << ", i=" << i;
169 return;
170 }
171 }
172
173 ib::info() << "all ok";
174
175 ha_storage_free(storage);
176}
177
178#endif /* UNIV_COMPILE_TEST_FUNCS */
179