/usr/include/givaro/givhashtable.h is in libgivaro-dev 4.0.2-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | // ==========================================================================
// $Source: /var/lib/cvs/Givaro/src/kernel/bstruct/givhashtable.h,v $
// Copyright(c)'1994-2009 by The Givaro group
// This file is part of Givaro.
// Givaro is governed by the CeCILL-B license under French law
// and abiding by the rules of distribution of free software.
// see the COPYRIGHT file for more details.
// Author: T. Gautier
// $Id: givhashtable.h,v 1.3 2011-02-02 16:23:55 briceboyer Exp $
// ==========================================================================
/*! @file givhashtable.h
* @ingroup bstruct
* @brief hash table
*/
#ifndef __GIVARO_hashtable_H
#define __GIVARO_hashtable_H
namespace Givaro {
/*! @brief The class Key.
* must have :
* - default cstor
* - operator== : (const Key&, const Key&) -> int
* - godel : void -> int
* .
*/
// Generic Key for class T which can be cast to and int
template<class T>
class Key {
public:
inline Key() {} ;
inline Key(const T& aa) : a(aa) {} ;
inline operator T& () { return a ; }
inline operator const T& () const { return a ; }
inline int godel() const { return (int)a ; }
inline int operator== (const Key<T>& K) const { return a == K.a ; }
private:
T a ;
} ;
//! Hash table
template<class T, class Key>
class HashTable {
public:
// Size of the table :
HashTable ( int n = 0 ) ;
void allocate( int n ) ;
~HashTable ( ) ;
void freeing() ;
// Insert and remove functions
void insert ( const T& item, const Key& k) ;
void insertLast ( const T& item, const Key& k) ;
void insertFront( const T& item, const Key& k) ;
// remove all entry with key k
void remove ( const Key& k) ;
void removeall ( ) ;
// Get and "Get and Remove" functions, return 0 if no found
// select the first item that they found
int get ( T& item, const Key& k ) const ;
int getrmv ( T& item, const Key& k ) ;
// Returns the number of items of the same key :
int num_item( const Key& k ) const ;
public: // ----- internal data structure
// must be private but is access by Iterator class
int num ;
struct _E {
_E( const T& item, const Key& k)
: oneitem(item), key(k) {} ;
public:
T oneitem ;
Key key ;
_E* next ;
_E* pred ;
} ;
_E** tabH ; // Head of list
_E** tabE ; // End of list
public:
// Iterator of all item of a HashTable :
class Iterator {
public:
Iterator ( HashTable<T,Key>& r)
: ref(r)
{
// search the first non-void pointer in ref.tabH :
for (e_curr =0; e_curr < ref.num ; e_curr++)
if ((curr =ref.tabH[e_curr]) !=0) break ;
} ;
operator int() const { return !isend() ; } ;
int isend() const
{
if (e_curr >= ref.num) return 1 ;
if (e_curr == ref.num-1)
if (curr ==0) return 1 ;
return 0 ;
}
void next()
{
_E* tmp = curr->next ;
if (tmp ==0) {
int i ;
for (i=e_curr+1 ; i<ref.num ; i++)
{
tmp = ref.tabH[i] ;
if (tmp !=0) break ;
}
if (i >= ref.num) { curr =0 ; e_curr = i ; }
else { curr = tmp ; e_curr = i ; }
}
else curr = tmp ;
} ;
T curr_item() { return curr->oneitem ; } ;
Key curr_key() { return curr->key ; } ;
private:
HashTable<T,Key>& ref ;
int e_curr ;
_E* curr ;
} ;
// Iterator of all item for a same Key :
class IteratorKey {
public:
IteratorKey ( HashTable<T,Key>& r, const Key& k )
: ref(r), key(k)
{
e_curr = key.godel() % r.num ;
curr = ref.tabH[e_curr] ;
} ;
operator int() const { return !isend() ; } ;
int isend() const { return curr == 0 ; }
void next()
{
curr = curr->next ;
while ( curr != 0 )
{
if (curr->key == key) break ;
curr = curr->next ;
}
} ;
T curr_item() { return curr->oneitem ; } ;
Key curr_key() { return curr->key ; } ;
private:
HashTable<T,Key>& ref ;
Key key ;
int e_curr ;
_E* curr ;
} ;
} ;
} // namespace Givaro
#include "givaro/givhashtable.inl"
#endif // __GIVARO_hashtable_H
|