2 * Copyright (C) 2017 Cisco Inc.
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License, version 2,
6 * as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 // @author Changxue Deng <chadeng@cisco.com>
31 #include "mabain_consts.h"
33 #include "rollable_file.h"
35 #include "free_list.h"
36 #include "lock_free.h"
41 typedef struct _NodePtrs
46 uint8_t *edge_key_ptr;
50 // Memory management class for the dictionary
51 class DictMem : public DRMBase
54 DictMem(const std::string &mbdir, bool init_header, size_t memsize,
55 int mode, uint32_t block_size, int max_num_blk, uint32_t queue_size);
60 void PrintStats(std::ostream &out_stream) const;
62 void InitNodePtrs(uint8_t *ptr, int nt, NodePtrs &node_ptrs);
63 void InitEdgePtrs(const NodePtrs &node_ptrs, int index,
65 void AddRootEdge(EdgePtrs &edge_ptrs, const uint8_t *key, int len,
67 int InsertNode(EdgePtrs &edge_ptrs, int match_len, size_t data_offset,
69 int AddLink(EdgePtrs &edge_ptrs, int match_len, const uint8_t *key,
70 int key_len, size_t data_off, MBData &data);
71 int UpdateNode(EdgePtrs &edge_ptrs, const uint8_t *key, int key_len,
73 bool FindNext(const unsigned char *key, int keylen, int &match_len,
74 EdgePtrs &edge_ptr, uint8_t *key_tmp) const;
75 int GetRootEdge(size_t rc_off, int nt, EdgePtrs &edge_ptrs) const;
76 int GetRootEdge_Writer(bool rc_mode, int nt, EdgePtrs &edge_ptrs) const;
77 int ClearRootEdge(int nt) const;
78 void ReserveData(const uint8_t* key, int size, size_t &offset,
79 bool map_new_sliding=true);
80 int NextEdge(const uint8_t *key, EdgePtrs &edge_ptrs,
81 uint8_t *tmp_buff, MBData &mbdata) const;
82 int RemoveEdgeByIndex(const EdgePtrs &edge_ptrs, MBData &data);
84 inline void WriteEdge(const EdgePtrs &edge_ptrs) const;
85 void WriteData(const uint8_t *buff, unsigned len, size_t offset) const;
86 inline size_t GetRootOffset() const;
87 void ClearMem() const;
88 const int* GetNodeSizePtr() const;
89 void ResetSlidingWindow() const;
91 void InitLockFreePtr(LockFree *lf);
96 size_t InitRootNode_RC();
97 int ClearRootEdges_RC() const;
99 // empty edge, used for clearing edges
100 static const uint8_t empty_edge[EDGE_SIZE];
103 bool ReserveNode(int nt, size_t &offset, uint8_t* &ptr);
104 void ReleaseNode(size_t offset, int nt);
105 void ReleaseBuffer(size_t offset, int size);
106 void UpdateTailEdge(EdgePtrs &edge_ptrs, int match_len, MBData &data,
107 EdgePtrs &tail_edge, uint8_t &new_key_first,
108 bool &map_new_sliding);
109 void UpdateHeadEdge(EdgePtrs &edge_ptrs, int match_len,
110 MBData &data, int &release_buffer_size,
111 size_t &edge_str_off, bool &map_new_sliding);
112 void RemoveRootEdge(const EdgePtrs &edge_ptrs);
113 int RemoveEdgeSizeN(const EdgePtrs &edge_ptrs, int nt, size_t node_offset,
114 uint8_t *old_node_buffer, size_t &str_off_rel,
115 int &str_size_rel, size_t parent_edge_offset);
116 int RemoveEdgeSizeOne(uint8_t *old_node_buffer, size_t parent_edge_offset,
117 size_t node_offset, int nt, size_t &str_off_rel,
130 std::shared_ptr<MmapFileIO> header_file;
132 size_t root_offset_rc;
135 inline void DictMem::WriteEdge(const EdgePtrs &edge_ptrs) const
137 if(edge_ptrs.offset + EDGE_SIZE > header->m_index_offset)
139 std::cerr << "invalid edge write: " << edge_ptrs.offset << " " << EDGE_SIZE
140 << " " << header->m_index_offset << "\n";
141 throw (int) MBError::OUT_OF_BOUND;
144 if(kv_file->RandomWrite(edge_ptrs.ptr, EDGE_SIZE, edge_ptrs.offset) != EDGE_SIZE)
145 throw (int) MBError::WRITE_ERROR;
148 inline size_t DictMem::GetRootOffset() const
153 // update the edge pointers for fast access
154 // node_ptrs.offset and node_ptrs.ptr[1] must already be populated before calling this function
155 inline void DictMem::InitEdgePtrs(const NodePtrs &node_ptrs, int index, EdgePtrs &edge_ptrs)
157 int edge_off = NODE_EDGE_KEY_FIRST + node_ptrs.ptr[1] + 1 + index*EDGE_SIZE;
158 edge_ptrs.offset = node_ptrs.offset + edge_off;
159 edge_ptrs.ptr = node_ptrs.ptr + edge_off;
160 edge_ptrs.len_ptr = edge_ptrs.ptr + EDGE_LEN_POS;
161 edge_ptrs.flag_ptr = edge_ptrs.ptr + EDGE_FLAG_POS;
162 edge_ptrs.offset_ptr = edge_ptrs.flag_ptr + 1;
165 inline void InitTempEdgePtrs(EdgePtrs &edge_ptrs)
167 edge_ptrs.ptr = edge_ptrs.edge_buff;
168 edge_ptrs.len_ptr = edge_ptrs.ptr + EDGE_LEN_POS;
169 edge_ptrs.flag_ptr = edge_ptrs.ptr + EDGE_FLAG_POS;
170 edge_ptrs.offset_ptr = edge_ptrs.flag_ptr + 1;
173 // node_ptrs.offset must be populated before caling this function
174 inline void DictMem::InitNodePtrs(uint8_t *ptr, int nt, NodePtrs &node_ptrs)
178 node_ptrs.edge_key_ptr = ptr + NODE_EDGE_KEY_FIRST;
179 node_ptrs.edge_ptr = node_ptrs.edge_key_ptr + nt;