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