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