1 #ifndef JUDYLARRAY_H 2 #define JUDYLARRAY_H 3 4 /****************************************************************************//** 5 * \file judyLArray.h C++ wrapper for judyL array implementation 6 * 7 * A judyL array maps JudyKey's to corresponding memory cells, each containing 8 * a JudyValue. Each cell must be set to a non-zero value by the caller. 9 * 10 * Author: Mark Pictor. Public domain. 11 * 12 ********************************************************************************/ 13 14 #include "judy.h" 15 #include "assert.h" 16 17 template< typename JudyKey, typename JudyValue > 18 struct judylKVpair { 19 JudyKey key; 20 JudyValue value; 21 }; 22 23 /** A judyL array maps JudyKey's to corresponding memory cells, each containing 24 * a JudyValue. Each cell must be set to a non-zero value by the caller. 25 * 26 * Both template parameters must be the same size as a void* 27 * \param JudyKey the type of the key, i.e. uint64_t, pointer-to-object, etc 28 * \param JudyValue the type of the value 29 */ 30 template< typename JudyKey, typename JudyValue > 31 class judyLArray { 32 public: 33 typedef judylKVpair< JudyKey, JudyValue > pair; 34 protected: 35 Judy * _judyarray; 36 unsigned int _maxLevels, _depth; 37 JudyValue * _lastSlot; 38 JudyKey _buff[1]; 39 bool _success; 40 pair _kv; 41 public: judyLArray()42 judyLArray(): _maxLevels( sizeof( JudyKey ) ), _depth( 1 ), _lastSlot( 0 ), _success( true ) { 43 assert( sizeof( JudyKey ) == JUDY_key_size && "JudyKey *must* be the same size as a pointer!" ); 44 assert( sizeof( JudyValue ) == JUDY_key_size && "JudyValue *must* be the same size as a pointer!" ); 45 _judyarray = judy_open( _maxLevels, _depth ); 46 _buff[0] = 0; 47 } 48 judyLArray(const judyLArray<JudyKey,JudyValue> & other)49 explicit judyLArray( const judyLArray< JudyKey, JudyValue > & other ): _maxLevels( other._maxLevels ), 50 _depth( other._depth ), _success( other._success ) { 51 _judyarray = judy_clone( other._judyarray ); 52 _buff[0] = other._buff[0]; 53 find( *_buff ); //set _lastSlot 54 } 55 ~judyLArray()56 ~judyLArray() { 57 judy_close( _judyarray ); 58 } 59 60 void clear( bool deleteContents = false ) { 61 JudyKey key = 0; 62 while( 0 != ( _lastSlot = ( JudyValue * ) judy_strt( _judyarray, ( const unsigned char * ) &key, 0 ) ) ) { 63 if( deleteContents ) { 64 delete *_lastSlot; 65 } 66 judy_del( _judyarray ); 67 } 68 } 69 getLastValue()70 JudyValue getLastValue() { 71 assert( _lastSlot ); 72 return &_lastSlot; 73 } 74 setLastValue(JudyValue value)75 void setLastValue( JudyValue value ) { 76 assert( _lastSlot ); 77 &_lastSlot = value; 78 } 79 success()80 bool success() { 81 return _success; 82 } 83 //TODO 84 // allocate data memory within judy array for external use. 85 // void *judy_data (Judy *judy, unsigned int amt); 86 87 /// insert or overwrite value for key insert(JudyKey key,JudyValue value)88 bool insert( JudyKey key, JudyValue value ) { 89 assert( value != 0 ); 90 _lastSlot = ( JudyValue * ) judy_cell( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ); 91 if( _lastSlot ) { 92 *_lastSlot = value; 93 _success = true; 94 } else { 95 _success = false; 96 } 97 return _success; 98 } 99 100 /// retrieve the cell pointer greater than or equal to given key 101 /// NOTE what about an atOrBefore function? atOrAfter(JudyKey key)102 const pair atOrAfter( JudyKey key ) { 103 _lastSlot = ( JudyValue * ) judy_strt( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ); 104 return mostRecentPair(); 105 } 106 107 /// retrieve the cell pointer, or return NULL for a given key. find(JudyKey key)108 JudyValue find( JudyKey key ) { 109 _lastSlot = ( JudyValue * ) judy_slot( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ); 110 if( _lastSlot ) { 111 _success = true; 112 return *_lastSlot; 113 } else { 114 _success = false; 115 return 0; 116 } 117 } 118 119 /// retrieve the key-value pair for the most recent judy query. mostRecentPair()120 inline const pair & mostRecentPair() { 121 judy_key( _judyarray, ( unsigned char * ) _buff, _depth * JUDY_key_size ); 122 if( _lastSlot ) { 123 _kv.value = *_lastSlot; 124 _success = true; 125 } else { 126 _kv.value = nullptr; 127 _success = false; 128 } 129 _kv.key = _buff[0]; 130 return _kv; 131 } 132 133 /// retrieve the first key-value pair in the array begin()134 const pair & begin() { 135 JudyKey key = 0; 136 _lastSlot = ( JudyValue * ) judy_strt( _judyarray, ( const unsigned char * ) &key, 0 ); 137 return mostRecentPair(); 138 } 139 140 /// retrieve the last key-value pair in the array end()141 const pair & end() { 142 _lastSlot = ( JudyValue * ) judy_end( _judyarray ); 143 return mostRecentPair(); 144 } 145 146 /// retrieve the key-value pair for the next key in the array. next()147 const pair & next() { 148 _lastSlot = ( JudyValue * ) judy_nxt( _judyarray ); 149 return mostRecentPair(); 150 } 151 152 /// retrieve the key-value pair for the prev key in the array. previous()153 const pair & previous() { 154 _lastSlot = ( JudyValue * ) judy_prv( _judyarray ); 155 return mostRecentPair(); 156 } 157 158 /** delete a key-value pair. If the array is not empty, 159 * getLastValue() will return the entry before the one that was deleted 160 * \sa isEmpty() 161 */ removeEntry(JudyKey * key)162 bool removeEntry( JudyKey * key ) { 163 if( judy_slot( _judyarray, key, _depth * JUDY_key_size ) ) { 164 _lastSlot = ( JudyValue * ) judy_del( _judyarray ); 165 return true; 166 } else { 167 return false; 168 } 169 } 170 171 /// true if the array is empty isEmpty()172 bool isEmpty() { 173 JudyKey key = 0; 174 return ( ( judy_strt( _judyarray, ( const unsigned char * ) &key, _depth * JUDY_key_size ) ) ? false : true ); 175 } 176 }; 177 #endif //JUDYLARRAY_H 178