source: source/ariba/utility/types/Identifier.h@ 2437

Last change on this file since 2437 was 2437, checked in by Christoph Mayer, 16 years ago

-memory leaks und corruption gefixt

File size: 14.8 KB
Line 
1// [Licence]
2// The Ariba-Underlay Copyright
3//
4// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
5//
6// Institute of Telematics
7// UniversitÀt Karlsruhe (TH)
8// Zirkel 2, 76128 Karlsruhe
9// Germany
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
22// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33// The views and conclusions contained in the software and documentation
34// are those of the authors and should not be interpreted as representing
35// official policies, either expressed or implied, of the Institute of
36// Telematics.
37// [Licence]
38
39#ifndef IDENTIFIER_H_
40#define IDENTIFIER_H_
41
42#include <memory>
43#include <string>
44#include <gmp.h>
45#include <boost/cstdint.hpp>
46#include "ariba/utility/logging/Logging.h"
47#include "ariba/utility/types/Address.h"
48#include "ariba/utility/serialization.h"
49
50/**< maximum length of the key */
51#define MAX_KEYLENGTH 192
52
53namespace ariba {
54namespace utility {
55
56using_serialization;
57
58class IdentifierBit;
59
60/**
61 * An abstract address class for identifier.<br/>
62 *
63 * This class is the base for all identifier classes.
64 */
65class Identifier: public Address {
66 VSERIALIZEABLE;
67 use_logging_h( Identifier );
68public:
69
70 //-------------------------------------------------------------------------
71 // virtual function from Address
72 //-------------------------------------------------------------------------
73
74 virtual void clearAddress();
75 virtual bool setAddress(string address);
76 virtual string getAddress() const;
77
78 //-------------------------------------------------------------------------
79 // constants
80 //-------------------------------------------------------------------------
81
82 static const Identifier UNSPECIFIED_KEY; /**< Identifier without defined key */
83 static const Identifier ZERO; /**< Identifier with key initialized as 0 */
84 static const Identifier ONE; /**< Identifier with key initialized as 1 */
85
86 //-------------------------------------------------------------------------
87 // construction and destruction
88 //-------------------------------------------------------------------------
89
90 /**
91 * Default constructor
92 *
93 * Contructs an unspecified overlay key
94 */
95 Identifier();
96
97 /**
98 * Constructs an overlay key initialized with a common integer
99 *
100 * @param num The integer to initialize this key with
101 */
102 Identifier(uint32_t num);
103
104 /**
105 * Constructs a key out of a buffer
106 * @param buffer Source buffer
107 * @param size Buffer size (in bytes)
108 */
109 Identifier(const unsigned char* buffer, uint size);
110
111 /**
112 * Constructs a key out of a string number.
113 */
114 Identifier(const std::string& str, uint base = 16);
115
116 /**
117 * Copy constructor.
118 *
119 * @param rhs The key to copy.
120 */
121 Identifier(const Identifier& rhs);
122
123 /**
124 * Default destructor.
125 *
126 * Does nothing ATM.
127 */
128 virtual ~Identifier();
129
130 //-------------------------------------------------------------------------
131 // string representations & node key attributes
132 //-------------------------------------------------------------------------
133
134 /**
135 * Returns a string representation of this key
136 *
137 * @return String representation of this key
138 */
139 virtual std::string toString(uint base = 16) const;
140
141 /**
142 * Common stdc++ console output method
143 */
144 friend std::ostream& operator<<(std::ostream& os, const Identifier& c);
145
146 /**
147 * Returns true, if the key is unspecified
148 *
149 * @return Returns true, if key is unspecified
150 */
151 bool isUnspecified() const;
152
153 //-------------------------------------------------------------------------
154 // operators
155 //-------------------------------------------------------------------------
156
157 /**
158 * compares this to a given Identifier
159 *
160 * @param compKey the the Identifier to compare this to
161 * @return true if compKey->key is smaller than this->key, else false
162 */
163 bool operator<(const Identifier& compKey) const;
164
165 /**
166 * compares this to a given Identifier
167 *
168 * @param compKey the the Identifier to compare this to
169 * @return true if compKey->key is greater than this->key, else false
170 */
171 bool operator>(const Identifier& compKey) const;
172
173 /**
174 * compares this to a given Identifier
175 *
176 * @param compKey the the Identifier to compare this to
177 * @return true if compKey->key is smaller than or equal to this->key, else false
178 */
179 bool operator<=(const Identifier& compKey) const;
180
181 /**
182 * compares this to a given Identifier
183 *
184 * @param compKey the the Identifier to compare this to
185 * @return true if compKey->key is greater than or equal to this->key, else false
186 */
187 bool operator>=(const Identifier& compKey) const;
188
189 /**
190 * compares this to a given Identifier
191 *
192 * @param compKey the the Identifier to compare this to
193 * @return true if compKey->key is equal to this->key, else false
194 */
195 bool operator==(const Identifier& compKey) const;
196
197 /**
198 * compares this to a given Identifier
199 *
200 * @param compKey the the Identifier to compare this to
201 * @return true if compKey->key is not equal to this->key, else false
202 */
203 bool operator!=(const Identifier& compKey) const;
204
205 /**
206 * Unifies all compare operations in one method
207 *
208 * @param compKey key to compare with
209 * @return int -1 if smaller, 0 if equal, 1 if greater
210 */
211 int compareTo(const Identifier& compKey) const;
212
213 /**
214 * assigns Identifier of rhs to this->key
215 *
216 * @param rhs the Identifier with the defined key
217 * @return this Identifier object
218 */
219 Identifier& operator=(const Identifier& rhs);
220
221 /**
222 * substracts 1 from this->key
223 *
224 * @return this Identifier object
225 */
226 Identifier& operator--();
227
228 /**
229 * adds 1 to this->key
230 *
231 * @return this Identifier object
232 */
233 Identifier& operator++();
234
235 /**
236 * adds rhs->key to this->key
237 *
238 * @param rhs the Identifier with the defined key
239 * @return this Identifier object
240 */
241 Identifier& operator+=(const Identifier& rhs);
242
243 /**
244 * substracts rhs->key from this->key
245 *
246 * @param rhs the Identifier with the defined key
247 * @return this Identifier object
248 */
249 Identifier& operator-=(const Identifier& rhs);
250
251 /**
252 * adds rhs->key to this->key
253 *
254 * @param rhs the Identifier with the defined key
255 * @return this Identifier object
256 */
257 Identifier operator+(const Identifier& rhs) const;
258
259 /**
260 * substracts rhs->key from this->key
261 *
262 * @param rhs the Identifier with the defined key
263 * @return this Identifier object
264 */
265 Identifier operator-(const Identifier& rhs) const;
266
267 /**
268 * substracts 1 from this->key
269 *
270 * @return this Identifier object
271 */
272 Identifier operator--(int);
273
274 /**
275 * adds 1 to this->key
276 *
277 * @return this Identifier object
278 */
279 Identifier operator++(int);
280
281 /**
282 * bitwise shift right
283 *
284 * @param num number of bits to shift
285 * @return this Identifier object
286 */
287 Identifier operator>>(uint num) const;
288
289 /**
290 * bitwise shift left
291 *
292 * @param num number of bits to shift
293 * @return this Identifier object
294 */
295 Identifier operator<<(uint num) const;
296
297 /**
298 * bitwise AND of rhs->key and this->key
299 *
300 * @param rhs the Identifier AND is calculated with
301 * @return this Identifier object
302 */
303 Identifier operator&(const Identifier& rhs) const;
304
305 /**
306 * bitwise OR of rhs->key and this->key
307 *
308 * @param rhs the Identifier OR is calculated with
309 * @return this Identifier object
310 */
311 Identifier operator|(const Identifier& rhs) const;
312
313 /**
314 * bitwise XOR of rhs->key and this->key
315 *
316 * @param rhs the Identifier XOR is calculated with
317 * @return this Identifier object
318 */
319 Identifier operator^(const Identifier& rhs) const;
320
321 /**
322 * bitwise NOT of this->key
323 *
324 * @return this Identifier object
325 */
326 Identifier operator~() const;
327
328 /**
329 * returns the n-th bit of this->key
330 *
331 * @param n the position of the returned bit
332 * @return the bit on position n in this->key
333 */
334 IdentifierBit operator[](uint n);
335
336 /**
337 * sets a bit of this->key
338 *
339 * @param pos the position of the bit to set
340 * @param value new value for bit at position pos
341 * @return *this
342 */
343 Identifier& setBitAt(uint pos, bool value);
344
345 //-------------------------------------------------------------------------
346 // additional math
347 //-------------------------------------------------------------------------
348
349 /**
350 * Returns a sub integer at position p with n-bits. p is counted starting
351 * from the least significant bit of the key as bit 0. Bit p of the key
352 * becomes bit 0 of the returned integer.
353 *
354 * @param p the position of the sub-integer
355 * @param n the number of bits to be returned (max.32)
356 * @return The sub-integer.
357 */
358 uint32_t get(uint p, uint n) const;
359
360 /**
361 * Returns a hash value for the key
362 *
363 * @return size_t The hash value
364 */
365 size_t hash() const;
366
367 /**
368 * Returns the position of the msb in this key, which represents
369 * just the logarithm to base 2.
370 *
371 * @return The logarithm to base 2 of this key.
372 */
373 int log_2() const;
374
375 /**
376 * Fills the suffix starting at pos with random bits to lsb.
377 *
378 * @param pos
379 * @return Identifier
380 */
381 Identifier randomSuffix(uint pos) const;
382
383 /**
384 * Fills the prefix starting at pos with random bits to msb.
385 *
386 * @param pos
387 * @return Identifier
388 */
389 Identifier randomPrefix(uint pos) const;
390
391 /**
392 * Calculates the number of equal bits from the left with another
393 * Key (shared prefix length)
394 *
395 * @param compKey the Key to compare with
396 * @return length of shared prefix
397 */
398 uint sharedPrefixLength(const Identifier& compKey) const;
399
400 /**
401 * Returns true, if this key is element of the interval (keyA, keyB)
402 * on the ring.
403 *
404 * @param keyA The left border of the interval
405 * @param keyB The right border of the interval
406 * @return True, if the key is element of the interval (keyA, keyB)
407 */
408 bool isBetween(const Identifier& keyA, const Identifier& keyB) const;
409
410 /**
411 * Returns true, if this key is element of the interval (keyA, keyB]
412 * on the ring.
413 *
414 * @param keyA The left border of the interval
415 * @param keyB The right border of the interval
416 * @return True, if the key is element of the interval (keyA, keyB]
417 */
418 bool isBetweenR(const Identifier& keyA, const Identifier& keyB) const;
419
420 /**
421 * Returns true, if this key is element of the interval [keyA, keyB)
422 * on the ring.
423 *
424 * @param keyA The left border of the interval
425 * @param keyB The right border of the interval
426 * @return True, if the key is element of the interval [keyA, keyB)
427 */
428 bool isBetweenL(const Identifier& keyA, const Identifier& keyB) const;
429
430 /**
431 * Returns true, if this key is element of the interval [keyA, keyB]
432 * on the ring.
433 *
434 * @param keyA The left border of the interval
435 * @param keyB The right border of the interval
436 * @return True, if the key is element of the interval [keyA, keyB]
437 */
438 bool isBetweenLR(const Identifier& keyA, const Identifier& keyB) const;
439
440 //-------------------------------------------------------------------------
441 // static methods
442 //-------------------------------------------------------------------------
443
444 /**
445 * Set the length of an Identifier
446 *
447 * @param length keylength in bits
448 */
449 static void setKeyLength(uint length);
450
451 /**
452 * Returns the length in number of bits.
453 *
454 * @return The length in number of bits.
455 */
456 static uint getLength();
457
458 /**
459 * Returns a random key.
460 *
461 * @return A random key.
462 */
463 static Identifier random();
464
465 /**
466 * Returns the maximum key, i.e. a key filled with bit 1
467 *
468 * @return The maximum key, i.e. a key filled with bit 1
469 */
470 static Identifier max();
471
472
473 // README: due to some problems with serialization the keylength
474 // was changed to 192 bit! As none of the hashing functions
475 // can provide 192 bit output, and we currently don't use any
476 // hashing for identifiers in the demo at all ... this is all commented out!!
477 /**
478 * Returns a key with the SHA1 cryptographic hash of a
479 * string
480 *
481 * @param value A string value.
482 * @return SHA1 of value
483 */
484 static Identifier sha1(const string& value);
485
486 static Identifier sha1(const uint8_t* value, size_t length );
487
488 /**
489 * Returns a key 2^exponent.
490 *
491 * @param exponent The exponent.
492 * @return Key=2^exponent.
493 */
494 static Identifier pow2(uint exponent);
495
496private:
497 // private constants
498
499 static uint keyLength; /**< actual length of the key */
500 static uint aSize; /**< number of needed machine words to hold the key*/
501 static mp_limb_t GMP_MSB_MASK; /**< bits to fill up if key does not
502 exactly fit in one or more machine words */
503
504 // private fields
505 bool isUnspec; /**< is this->key unspecified? */
506
507 void seed();
508
509 static const size_t array_size = MAX_KEYLENGTH / (8 * sizeof(mp_limb_t))
510 + (MAX_KEYLENGTH % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
511
512 /** the overlay key this object represents */
513 mp_limb_t key[array_size + 1];
514
515 // private "helper" methods
516 /**
517 * trims key after key operations
518 */
519 void trim();
520
521 /**
522 * set this->key to 0 and isUnspec to false
523 */
524 void clear();
525};
526
527/**
528 * An auxiliary class for single bits in OverlayKey
529 *
530 * Allows statements like "key[n] = true"
531 */
532class IdentifierBit {
533public:
534
535 IdentifierBit(bool value, uint pos, Identifier* key) :
536 bit(value), pos(pos), key(key) {
537 }
538
539 /** Converts to a boolean value */
540 inline operator bool() {
541 return bit;
542 }
543
544 /** Sets the corresponding bit to a boolean value
545 * @param value value to set to
546 */
547 inline IdentifierBit& operator=(bool value) {
548 key->setBitAt(pos, value);
549 return *this;
550 }
551
552 inline IdentifierBit& operator^=(bool value) {
553 key->setBitAt(pos, (*key)[pos] ^ value);
554 return *this;
555 }
556
557private:
558
559 bool bit;
560 uint pos;
561 Identifier* key;
562};
563
564}
565} // namespace ariba, common
566
567/* serializers */
568sznBeginDefault( ariba::utility::Identifier, X ) {
569 // calculate length of key
570 uint16_t len = array_size*sizeof(mp_limb_t);
571 uint8_t unspec = isUnspec;
572
573 // only serialize the lower 16 bits of keyLength
574 X && unspec && len;
575
576 // serialize the identifier
577 for (int i=array_size-1; i>=0; i--) X && key[i];
578
579 // when deserializing reset unspec flag
580 if (X.isDeserializer()) isUnspec = unspec;
581} sznEnd();
582
583#endif /* IDENTIFIER_H_ */
Note: See TracBrowser for help on using the repository browser.