1 #ifndef JUDYL2ARRAY_H
2 #define JUDYL2ARRAY_H
3 
4 /****************************************************************************//**
5 * \file judyL2Array.h C++ wrapper for judyL2 array implementation
6 *
7 * A judyL2 array maps JudyKey's to multiple JudyValue's, similar to
8 * std::multimap. Internally, this is a judyL array of std::vector< JudyValue >.
9 *
10 *    Author: Mark Pictor. Public domain.
11 *
12 ********************************************************************************/
13 
14 #include "judy.h"
15 #include "assert.h"
16 #include <iterator>
17 #include <vector>
18 
19 template< typename JudyKey, typename vec >
20 struct judyl2KVpair {
21     JudyKey key;
22     vec value;
23 };
24 
25 /** A judyL2 array maps JudyKey's to multiple JudyValue's, similar to std::multimap.
26  * Internally, this is a judyL array of std::vector< JudyValue >.
27  * The first template parameter must be the same size as a void*
28  *  \param JudyKey the type of the key, i.e. uint64_t, etc
29  *  \param JudyValue the type of the value, i.e. int, pointer-to-object, etc. With judyL2Array, the size of this value can vary.
30  */
31 template< typename JudyKey, typename JudyValue >
32 class judyL2Array {
33     public:
34         typedef std::vector< JudyValue > vector;
35         typedef const vector cvector;
36         typedef judyl2KVpair< JudyKey, vector * > pair;
37         typedef judyl2KVpair< JudyKey, cvector * > cpair;
38     protected:
39         Judy * _judyarray;
40         unsigned int _maxLevels, _depth;
41         vector ** _lastSlot;
42         JudyKey _buff[1];
43         bool _success;
44         cpair kv;
45     public:
judyL2Array()46         judyL2Array(): _maxLevels( sizeof( JudyKey ) ), _depth( 1 ), _lastSlot( 0 ), _success( true ) {
47             assert( sizeof( JudyKey ) == JUDY_key_size && "JudyKey *must* be the same size as a pointer!" );
48             _judyarray = judy_open( _maxLevels, _depth );
49             _buff[0] = 0;
50         }
51 
judyL2Array(const judyL2Array<JudyKey,JudyValue> & other)52         explicit judyL2Array( const judyL2Array< JudyKey, JudyValue > & other ): _maxLevels( other._maxLevels ),
53             _depth( other._depth ), _success( other._success ) {
54             _judyarray = judy_clone( other._judyarray );
55             _buff[0] = other._buff[0];
56             find( *_buff ); //set _lastSlot
57         }
58 
59         /// calls clear, so should be safe to call at any point
~judyL2Array()60         ~judyL2Array() {
61             clear();
62             judy_close( _judyarray );
63         }
64 
65         /// delete all vectors and empty the array
clear()66         void clear() {
67             JudyKey key = 0;
68             while( 0 != ( _lastSlot = ( vector ** ) judy_strt( _judyarray, ( const unsigned char * ) &key, 0 ) ) ) {
69                 //( * _lastSlot )->~vector(); //TODO: placement new
70                 delete( * _lastSlot );
71                 judy_del( _judyarray );
72             }
73         }
74 
getLastValue()75         vector * getLastValue() {
76             assert( _lastSlot );
77             return &_lastSlot;
78         }
79 
setLastValue(vector * value)80         void setLastValue( vector * value ) {
81             assert( _lastSlot );
82             &_lastSlot = value;
83         }
84 
success()85         bool success() {
86             return _success;
87         }
88 
89         /** TODO
90          * test for std::vector::shrink_to_fit (C++11), use it once the array is as full as it will be
91          * void freeUnused() {...}
92          */
93 
94         //TODO
95         // allocate data memory within judy array for external use.
96         // void *judy_data (Judy *judy, unsigned int amt);
97 
98         /// insert value into the vector for key.
insert(JudyKey key,JudyValue value)99         bool insert( JudyKey key, JudyValue value ) {
100             _lastSlot = ( vector ** ) judy_cell( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size );
101             if( _lastSlot ) {
102                 if( !( * _lastSlot ) ) {
103                     * _lastSlot = new vector;
104                     /* TODO store vectors inside judy with placement new
105                     * vector * n = judy_data( _judyarray, sizeof( std::vector < JudyValue > ) );
106                     * new(n) vector;
107                     * *_lastSlot = n;
108                     * NOTE - memory alloc'd via judy_data will not be freed until the array is freed (judy_close)
109                     * also use placement new in the other insert function, below
110                     */
111                 }
112                 ( * _lastSlot )->push_back( value );
113                 _success = true;
114             } else {
115                 _success = false;
116             }
117             return _success;
118         }
119 
120         /** for a given key, append to or overwrite the vector
121          * this never simply re-uses the pointer to the given vector because
122          * that would mean that two keys could have the same value (pointer).
123          */
124         bool insert( JudyKey key, const vector & values, bool overwrite = false ) {
125             _lastSlot = ( vector ** ) judy_cell( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size );
126             if( _lastSlot ) {
127                 if( !( * _lastSlot ) ) {
128                     * _lastSlot = new vector;
129                     /* TODO store vectors inside judy with placement new
130                      * (see other insert(), above)
131                      */
132                 } else if( overwrite ) {
133                     ( * _lastSlot )->clear();
134                 }
135                 std::copy( values.begin(), values.end(), std::back_inserter< vector >( ( ** _lastSlot ) ) );
136                 _success = true;
137             } else {
138                 _success = false;
139             }
140             return _success;
141         }
142 
143         /// retrieve the cell pointer greater than or equal to given key
144         /// NOTE what about an atOrBefore function?
atOrAfter(JudyKey key)145         const cpair atOrAfter( JudyKey key ) {
146             _lastSlot = ( vector ** ) judy_strt( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size );
147             return mostRecentPair();
148         }
149 
150         /// retrieve the cell pointer, or return NULL for a given key.
find(JudyKey key)151         cvector * find( JudyKey key ) {
152             _lastSlot = ( vector ** ) judy_slot( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size );
153             if( ( _lastSlot ) && ( * _lastSlot ) ) {
154                 _success = true;
155                 return * _lastSlot;
156             } else {
157                 _success = false;
158                 return 0;
159             }
160         }
161 
162         /// retrieve the key-value pair for the most recent judy query.
mostRecentPair()163         inline const cpair & mostRecentPair() {
164             judy_key( _judyarray, ( unsigned char * ) _buff, _depth * JUDY_key_size );
165             if( _lastSlot ) {
166                 kv.value = *_lastSlot;
167                 _success = true;
168             } else {
169                 kv.value = nullptr;
170                 _success = false;
171             }
172             kv.key = _buff[0];
173             return kv;
174         }
175 
176         /// retrieve the first key-value pair in the array
begin()177         const cpair & begin() {
178             JudyKey key = 0;
179             _lastSlot = ( vector ** ) judy_strt( _judyarray, ( const unsigned char * ) &key, 0 );
180             return mostRecentPair();
181         }
182 
183         /// retrieve the last key-value pair in the array
end()184         const cpair & end() {
185             _lastSlot = ( vector ** ) judy_end( _judyarray );
186             return mostRecentPair();
187         }
188 
189         /// retrieve the key-value pair for the next string in the array.
next()190         const cpair & next() {
191             _lastSlot = ( vector ** ) judy_nxt( _judyarray );
192             return mostRecentPair();
193         }
194 
195         /// retrieve the key-value pair for the prev string in the array.
previous()196         const cpair & previous() {
197             _lastSlot = ( vector ** ) judy_prv( _judyarray );
198             return mostRecentPair();
199         }
200 
201         /** delete a key-value pair. If the array is not empty,
202          * getLastValue() will return the entry before the one that was deleted
203          * \sa isEmpty()
204          */
removeEntry(JudyKey key)205         bool removeEntry( JudyKey key ) {
206             if( 0 != ( _lastSlot = ( vector ** ) judy_slot( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ) ) ) {
207                 // _lastSlot->~vector(); //for use with placement new
208                 delete _lastSlot;
209                 _lastSlot = ( vector ** ) judy_del( _judyarray );
210                 return true;
211             } else {
212                 return false;
213             }
214         }
215 
216         /// true if the array is empty
isEmpty()217         bool isEmpty() {
218             JudyKey key = 0;
219             return ( ( judy_strt( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ) ) ? false : true );
220         }
221 };
222 #endif //JUDYL2ARRAY_H
223