1 // Copyright 2009 The Archiveopteryx Developers <info@aox.org>
2
3 #include "map.h"
4
5 #include <arpa/inet.h> // ntohl
6
7 // we need BYTE_ORDER and arpa/inet doesn't give us that on linux, so
8 // try to coax that out of linux, but use ifdefs so that if we don't
9 // need endian.h, we don't even try to include it. I hate the
10 // endianness functions.
11 #if !defined( BYTE_ORDER )
12 #if !defined( __USE_BSD )
13 #define __USE_BSD
14 #endif
15 #include <endian.h>
16 #endif
17
18
19 /*! \class Map map.h
20 The Map template maps from uint to a pointer.
21
22 It is intended to be used for cached database rows: The user
23 supplies the row's unique key and the Map supplies a pointer to
24 the cached object.
25
26 The implementation is optimized for scattered clusters of values:
27 If 1234 is in the map, other integers nearby are assumed to be
28 there, too. When this is true, the memory overhead is small and
29 speed high. When not, speed remains high.
30
31 The actual implementation is a number of arrays. The key is
32 chopped into n-bit chunks and each chunk is used to index into a
33 table. The most significant few bits index into the root table.
34
35 n is an implementation constant, not adjustable per Map. At the
36 moment it's 6 (and the root table is mostly empty).
37 */
38
39
40 /*! \fn Map::Map()
41 Creates a new empty Map.
42 */
43
44
45 /*! \fn T * Map::find( uint i )
46
47 Returns a pointer to the object at index \a i, or a null pointer if
48 there is no such object. This function does not allocate any memory.
49 */
50
51 /*! \fn void Map::insert( uint i, T * r )
52
53 Inserts \a r into the Map at index \a i. This may cause memory
54 allocation as the map builds intermediate tree nodes.
55 */
56
57 /*! \fn void Map::remove( uint i )
58
59 Removes the object at index \a i from the Map. This may cause memory
60 allocation, as it's a thin wrapper around insert( \a i, 0 ).
61 */
62
63 /*! \fn bool Map::contains( uint i )
64 Returns true if this map has an object at index \a i, and false if not.
65 */
66
67 /*! \fn uint Map::count() const
68 Returns the number of objects in the Map.
69 */
70
71
72 /*! \fn void Map::clear()
73 Removes everything in the map.
74 */
75
76
77 /*! \fn uint Map::k( uint i )
78 Returns \a i with the most significant byte first (AKA network byte
79 order), useful for PatriciaTree.
80 */
81
82 /*! \fn uint Map::l()
83 Returns the number of bits in a uint.
84 */
85
86
87 // This static helper returns the uint in network byte order, much
88 // like ntohl, except that it supports 64-bit uints.
89
uintInNetworkOrder(uint x)90 uint uintInNetworkOrder( uint x )
91 {
92 if ( BYTE_ORDER == BIG_ENDIAN )
93 return x;
94 else if ( sizeof( uint ) <= 4 )
95 return ntohl( x );
96 else
97 return ( (((x) & 0xff00000000000000ull) >> 56)
98 | (((x) & 0x00ff000000000000ull) >> 40)
99 | (((x) & 0x0000ff0000000000ull) >> 24)
100 | (((x) & 0x000000ff00000000ull) >> 8)
101 | (((x) & 0x00000000ff000000ull) << 8)
102 | (((x) & 0x0000000000ff0000ull) << 24)
103 | (((x) & 0x000000000000ff00ull) << 40)
104 | (((x) & 0x00000000000000ffull) << 56));
105 }
106