diff options
Diffstat (limited to 'src/maps')
| -rw-r--r-- | src/maps/hmap.h | 96 | ||||
| -rw-r--r-- | src/maps/hmap.tmpl | 289 | ||||
| -rw-r--r-- | src/maps/mtools.h | 26 | ||||
| -rw-r--r-- | src/maps/mtools.tmpl | 29 | ||||
| -rw-r--r-- | src/maps/nmap.h | 22 | ||||
| -rw-r--r-- | src/maps/nmap.tmpl | 31 | ||||
| -rw-r--r-- | src/maps/smap.h | 55 | ||||
| -rw-r--r-- | src/maps/smap.tmpl | 215 |
8 files changed, 711 insertions, 52 deletions
diff --git a/src/maps/hmap.h b/src/maps/hmap.h new file mode 100644 index 0000000..38ea2e4 --- /dev/null +++ b/src/maps/hmap.h @@ -0,0 +1,96 @@ +#pragma warning(disable:4786) + +#include "../incl.h" + +#ifndef HMAP_H +#define HMAP_H + +#include <vector> + +using namespace std; + +template <class obj_type, class key_type> +class hmap +{ +protected: + enum entry_type + { + ACTIVE, EMPTY, DELETED + }; + + struct hash_entry + { + obj_type element; + key_type key; + entry_type info; + int hits; + + hash_entry( const obj_type &e = obj_type( ), const key_type &k = key_type( ), entry_type i = EMPTY ) : element( e ), key( k ), info( i ) + { } + } + ; + + int occupied; + + virtual bool is_active( int i_current_pos ) const; + virtual void rehash( ); + virtual bool is_prime ( int n ) const; + virtual int next_prime( int n ) const; + double i_max_occupied_percentage; + + int lookups; + virtual unsigned int hash( const string &key ) const; + vector<hash_entry> array; + + int get_lookups() + { + return lookups; + }; + + int get_capacity() + { + return array.size(); + }; + + double get_lambda() + { + return static_cast<double>(get_size())/static_cast<double>(get_capacity()); + } + + obj_type& operator[]( key_type &k ) + { + return get_elem( k ); + } + + int find_pos ( const key_type &k ); + +public: + hmap( double moc ); + ~hmap( ); + + virtual int get_size(); + virtual void make_empty( ); + virtual void make_empty( void (*func)(key_type) ); + virtual void del_elem ( const key_type &k ); + virtual void rename_key ( const key_type &k1, const key_type &k2 ); + virtual obj_type set_elem ( const obj_type &x, const key_type &k ); + + virtual void run_func( void (*func)(obj_type) ); + virtual void run_func( void (*func)(obj_type, void*), void* v_arg ); + virtual void run_func_on( void (*func)(obj_type), const key_type & k ); + virtual vector<key_type>* get_key_vector( ); + + virtual void add_elem ( const obj_type &x, const key_type &k ); + + virtual bool is_avail( const key_type &k ); + virtual obj_type pop_elem ( const key_type &k ); + virtual obj_type get_elem ( const key_type &k ); + virtual obj_type operator[]( const key_type &k ) { + return get_elem( k ); + } + +}; + +#include "hmap.tmpl" + +#endif diff --git a/src/maps/hmap.tmpl b/src/maps/hmap.tmpl new file mode 100644 index 0000000..cc2ec24 --- /dev/null +++ b/src/maps/hmap.tmpl @@ -0,0 +1,289 @@ +#ifndef HMAP_CPP +#define HMAP_CPP + +#include "hmap.h" + +using namespace std; + +bool is_prime( int n ); +int next_prime( int n ); + +// Construct the hash table. +template <class obj_type, class key_type> +hmap<obj_type, key_type>::hmap( double mop ) + : i_max_occupied_percentage(mop), array( next_prime( 101 ) ) +{ + lookups = 0; + make_empty( ); +} + +template <class obj_type, class key_type> +hmap<obj_type, key_type>::~hmap( ) +{ + make_empty( ); +} + +// Insert item x into the hash table. If the item is +// already present, do nothing +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::add_elem( const obj_type &x, const key_type &k ) +{ + // Insert x as active + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + return; + + array[ i_current_pos ] = hash_entry( x, k, ACTIVE ); + if( ++occupied > array.size( ) * i_max_occupied_percentage ) + rehash( ); +} + +// Expand the hash table. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::rehash( ) +{ + vector<hash_entry> old_array = array; + + // Create new double-sized, empty table + array.resize( next_prime( 2 * old_array.size( ) ) ); + for( int j = 0; j < array.size( ); j++ ) + { + array[ j ].info = EMPTY; + } + + // Copy table over + make_empty( ); + for( int i = 0; i < old_array.size( ); i++ ) + if( old_array[ i ].info == ACTIVE ) + add_elem( old_array[ i ].element, old_array[ i ].key ); +} + +// Hash function, can only handle strings. +// If you want to hash other objects you will have to +// create a hash table for them +template <class obj_type, class key_type> +unsigned int hmap<obj_type, key_type>::hash( const string & key ) const +{ + unsigned int hash_value = 0; + // cout << key << "%"; + + for( size_t i = 0; i < key.size(); i++ ) + hash_value = ( hash_value << 5 ) ^ key[ i ] ^ hash_value; + + return hash_value; +} + +// Method that performs quadratic probing resolution. +// Return the position where the search for x terminates. +template <class obj_type, class key_type> +int hmap<obj_type, key_type>::find_pos( const key_type &k ) +{ + int i_collision_num = 0; + int i_current_pos = hash( k ) % array.size( ); + lookups++; + + while( array[ i_current_pos ].info != EMPTY && + array[ i_current_pos ].key != k ) + { + lookups++; + i_current_pos += 2 * ++i_collision_num - 1; // Compute ith probe + + if( i_current_pos >= array.size( ) ) + i_current_pos -= array.size( ); + } + + return i_current_pos; +} + +// Remove item x from the hash table. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::del_elem( const key_type & k ) +{ + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + array[ i_current_pos ].info = DELETED; +} + +// Remove item x from the hash table. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::rename_key( const key_type & k1, const key_type & k2 ) +{ + int i_current_pos = find_pos( k1 ); + if( is_active( i_current_pos ) ) { + array[ i_current_pos ].info = DELETED; + add_elem( array[ i_current_pos ].element, k2 ); + } +} + +// Finds item x and resets its value. +template <class obj_type, class key_type> +obj_type hmap<obj_type, key_type>::set_elem( const obj_type & x, const key_type & k ) +{ + int i_current_pos = find_pos( k ); + obj_type ret_elem; + + if( is_active( i_current_pos ) ) + { + ret_elem = array[ i_current_pos ].element; + array[ i_current_pos ].element = x; + } + + else + { + add_elem( x, k ); + } + + return ret_elem; +} + +// Find item x in the hash table. +// Return a pointer to the matching item or 0 if not found +template <class obj_type, class key_type> +obj_type hmap<obj_type, key_type>::get_elem( const key_type &k ) +{ + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + { + array[i_current_pos ].hits++; + return array[i_current_pos].element; + } + + return NULL; +} + +template <class obj_type, class key_type> +obj_type hmap<obj_type, key_type>::pop_elem( const key_type &k ) +{ + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + { + array[ i_current_pos ].info = DELETED; + return array[i_current_pos].element; + } + + return NULL; +} + +template <class obj_type, class key_type> +bool hmap<obj_type, key_type>::is_avail( const key_type &k ) +{ + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + return 1; + else + return 0; +} + +// Make the hash table logically empty. +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::make_empty( ) +{ + occupied = 0; + for( int i = 0; i < array.size( ); i++ ) + array[i].info = EMPTY; +} + +template <class obj_type, class key_type> +void hmap<obj_type, key_type>::make_empty( void (*func)(key_type) ) +{ + occupied = 0; + for( int i = 0; i < array.size( ); i++ ) + if ( array[ i ].info != EMPTY ) + { + array[ i ].info = EMPTY; + ( *func ) ( array[ i ].key ); + } +} + +// Return true if i_current_pos exists and is active. +template <class obj_type, class key_type> +bool hmap<obj_type, key_type>::is_active( int i_current_pos ) const +{ + return array[ i_current_pos ].info == ACTIVE; +} + + +// Internal method to test if a positive number is prime. +// Not an efficient algorithm. +template <class obj_type, class key_type> +bool hmap<obj_type, key_type>::is_prime( int n ) const +{ + if( n == 2 || n == 3 ) + return true; + + else if( n == 1 || n % 2 == 0 ) + return false; + + for( int i = 3; i * i <= n; i += 2 ) + if( n % i == 0 ) + return false; + + return true; +} + +// Internal method to return a prime number at least as large as n. +// Assumes n > 0. +template <class obj_type, class key_type> +int hmap<obj_type, key_type>::next_prime( int n ) const +{ + if( n % 2 == 0 ) + n++; + + for( ; !is_prime( n ); n += 2 ) ; + + return n; +} + +template<class obj_type, class key_type> +void +hmap<obj_type, key_type>::run_func( void (*func)(obj_type) ) +{ + for( int i = 0; i < array.size( ); i++ ) + if ( array[i].info == ACTIVE ) + ( *func ) ( array[i].element ); +} + +template<class obj_type, class key_type> +void +hmap<obj_type, key_type>::run_func( void (*func)(obj_type, void*), void* v_arg ) +{ + for( int i = 0; i < array.size( ); i++ ) + if ( array[i].info == ACTIVE ) + ( *func ) ( array[i].element, v_arg ); +} + +template<class obj_type, class key_type> +void +hmap<obj_type, key_type>::run_func_on( void (*func)(obj_type), const key_type & k ) +{ + int i_current_pos = find_pos( k ); + if( is_active( i_current_pos ) ) + ( *func ) ( array[i_current_pos].element ); +} + + +template<class obj_type, class key_type> +vector<key_type>* +hmap<obj_type, key_type>::get_key_vector() +{ + vector<key_type>* p_vec = new vector<key_type>; + for( int i = 0; i < array.size( ); i++ ) + if ( array[i].info == ACTIVE ) + p_vec->push_back( array[i].key ); + + return p_vec; +} + + +template<class obj_type, class key_type> int +hmap<obj_type, key_type>::get_size() +{ + int size = 0; + for( int j = 0; j < array.size( ); j++ ) + if (array[ j ].info == ACTIVE) + size++; + + return size; +} + +#endif diff --git a/src/maps/mtools.h b/src/maps/mtools.h index 5a2b6bb..6062191 100644 --- a/src/maps/mtools.h +++ b/src/maps/mtools.h @@ -1,27 +1,3 @@ -/*:* - *: File: ./src/maps/mtools.h - *: - *: yChat; Homepage: www.yChat.org; Version 0.8.3-CURRENT - *: - *: Copyright (C) 2003 Paul C. Buetow, Volker Richter - *: Copyright (C) 2004 Paul C. Buetow - *: Copyright (C) 2005 EXA Digital Solutions GbR - *: - *: This program is free software; you can redistribute it and/or - *: modify it under the terms of the GNU General Public License - *: as published by the Free Software Foundation; either version 2 - *: of the License, or (at your option) any later version. - *: - *: This program is distributed in the hope that it will be useful, - *: but WITHOUT ANY WARRANTY; without even the implied warranty of - *: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - *: GNU General Public License for more details. - *: - *: You should have received a copy of the GNU General Public License - *: along with this program; if not, write to the Free Software - *: Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - *:*/ - #ifndef MTOOLS_H #define MTOOLS_H @@ -32,4 +8,4 @@ struct mtools }; #include "mtools.tmpl" -#endif +#endif diff --git a/src/maps/mtools.tmpl b/src/maps/mtools.tmpl index dff950f..dd3f89e 100644 --- a/src/maps/mtools.tmpl +++ b/src/maps/mtools.tmpl @@ -1,36 +1,11 @@ -/*:* - *: File: ./src/maps/mtools.tmpl - *: - *: yChat; Homepage: www.yChat.org; Version 0.8.3-CURRENT - *: - *: Copyright (C) 2003 Paul C. Buetow, Volker Richter - *: Copyright (C) 2004 Paul C. Buetow - *: Copyright (C) 2005 EXA Digital Solutions GbR - *: - *: This program is free software; you can redistribute it and/or - *: modify it under the terms of the GNU General Public License - *: as published by the Free Software Foundation; either version 2 - *: of the License, or (at your option) any later version. - *: - *: This program is distributed in the hope that it will be useful, - *: but WITHOUT ANY WARRANTY; without even the implied warranty of - *: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - *: GNU General Public License for more details. - *: - *: You should have received a copy of the GNU General Public License - *: along with this program; if not, write to the Free Software - *: Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - *:*/ - #ifndef MTOOLS_TMPL #define MTOOLS_TMPL template <class type_> void -mtools<type_>::delete_obj( type_ type_obj ) -{ +mtools<type_>::delete_obj( type_ type_obj ) { if ( type_obj ) - delete type_obj; + delete type_obj; } #endif diff --git a/src/maps/nmap.h b/src/maps/nmap.h new file mode 100644 index 0000000..e29da3b --- /dev/null +++ b/src/maps/nmap.h @@ -0,0 +1,22 @@ +#include "../incl.h" + +#ifndef NMAP_H +#define NMAP_H + +#include "smap.h" + +template <class obj_type, class key_type> +class nmap : public smap<obj_type, key_type> +{ + public: + nmap( double moc ); + ~nmap(); + + // Override the get_elem method so that a new object + // will be returned if the required element is not in + // the map! + obj_type get_elem ( const key_type &k ); +}; + +#include "nmap.tmpl" +#endif diff --git a/src/maps/nmap.tmpl b/src/maps/nmap.tmpl new file mode 100644 index 0000000..6fdea2f --- /dev/null +++ b/src/maps/nmap.tmpl @@ -0,0 +1,31 @@ +#ifndef NMAP_CPP +#define NMAP_CPP + +#include "nmap.h" + +template <class obj_type, class key_type> +nmap<obj_type, key_type>::nmap( double moc ) : smap<obj_type, key_type>::smap(moc) +{ +} + +template <class obj_type, class key_type> +nmap<obj_type, key_type>::~nmap() +{ +} + +template <class obj_type, class key_type> +obj_type nmap<obj_type, key_type>::get_elem ( const key_type &k ) { + // Create new object; + obj_type ret_val; + + smap<obj_type, key_type>::lock_mutex(); + int i_current_pos = find_pos( k ); + if( smap<obj_type, key_type>::is_active( i_current_pos ) ) + ret_val = smap<obj_type, key_type>::array[ i_current_pos ].element; + // else + // ret_val = new obj_type(); + smap<obj_type, key_type>::unlock_mutex(); + return ret_val; +} + +#endif diff --git a/src/maps/smap.h b/src/maps/smap.h new file mode 100644 index 0000000..a3ee89d --- /dev/null +++ b/src/maps/smap.h @@ -0,0 +1,55 @@ +// smap := Syncronized hmap +// nmap := Syncronized hmap which's get_elem returns a new obj_type +// instance instead of NULL if for a specific key no value has +// been found + +#include "../incl.h" + +#ifndef SMAP_H +#define SMAP_H + +#include "hmap.h" + +template <class obj_type, class key_type> +class smap : public hmap<obj_type, key_type> +{ + private: + pthread_mutex_t mut_smap; + + protected: + void lock_mutex(); + void unlock_mutex(); + + public: + smap( double moc ); + ~smap(); + int get_size(); + void make_empty(); + void make_empty( void (*func)(key_type) ); + void add_elem ( const obj_type &x, const key_type &k ); + obj_type set_elem ( const obj_type &x, const key_type &k ); + void del_elem ( const key_type &k ); + void rename_key ( const key_type &k1, const key_type &k2 ); + bool is_avail ( const key_type &k ); + obj_type get_elem ( const key_type &k ); + obj_type pop_elem ( const key_type &k ); + void run_func( void (*func)(obj_type) ); + void run_func( void (*func)(obj_type, void*), void* v_arg ); + void run_func_on( void (*func)(obj_type), const key_type &k ); + vector<key_type>* get_key_vector(); + + int get_size_insecure(); + void make_empty_insecure(); + void make_empty_insecure( void (*func)(key_type) ); + void add_elem_insecure ( const obj_type &x, const key_type &k ); + void del_elem_insecure ( const key_type &k ); + bool is_avail_insecure ( const key_type &k ); + obj_type get_elem_insecure ( const key_type &k ); + obj_type pop_elem_insecure ( const key_type &k ); + void run_func_insecure( void (*func)(obj_type) ); + void run_func_insecure( void (*func)(obj_type, void*), void* v_arg ); + vector<key_type>* get_key_vector_insecure(); +}; + +#include "smap.tmpl" +#endif diff --git a/src/maps/smap.tmpl b/src/maps/smap.tmpl new file mode 100644 index 0000000..670b84d --- /dev/null +++ b/src/maps/smap.tmpl @@ -0,0 +1,215 @@ +#ifndef SMAP_CPP +#define SMAP_CPP + +#include "smap.h" + +template <class obj_type, class key_type> +smap<obj_type, key_type>::smap( double moc ) : hmap<obj_type, key_type>::hmap(moc) +{ + pthread_mutex_init( &mut_smap , NULL); +} + +template <class obj_type, class key_type> +smap<obj_type, key_type>::~smap() +{ + pthread_mutex_destroy( &mut_smap ); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::lock_mutex() { + pthread_mutex_lock( &mut_smap ); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::unlock_mutex() { + pthread_mutex_unlock( &mut_smap ); +} + +template <class obj_type, class key_type> int +smap<obj_type, key_type>::get_size() +{ + int i_size; + pthread_mutex_lock ( &mut_smap ); + i_size = hmap<obj_type,key_type>::get_size(); + pthread_mutex_unlock( &mut_smap ); + return i_size; +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::make_empty() +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::make_empty(); + pthread_mutex_unlock( &mut_smap ); +} + +template <class obj_type, class key_type> +void smap<obj_type, key_type>::make_empty( void (*func)(key_type) ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::make_empty( func ); + pthread_mutex_unlock( &mut_smap ); +} + + +template <class obj_type, class key_type> +void smap<obj_type, key_type>::add_elem( const obj_type &x, const key_type &k ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::add_elem( x, k ); + pthread_mutex_unlock( &mut_smap ); +} + +template <class obj_type, class key_type> +obj_type smap<obj_type, key_type>::set_elem( const obj_type &x, const key_type &k ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::set_elem( x, k ); + pthread_mutex_unlock( &mut_smap ); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::del_elem( const key_type & k ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::del_elem( k ); + pthread_mutex_unlock( &mut_smap ); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::rename_key( const key_type & k1, const key_type & k2 ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::rename_key( k1, k2 ); + pthread_mutex_unlock( &mut_smap ); +} + + +template <class obj_type, class key_type> +obj_type smap<obj_type, key_type>::get_elem( const key_type &k ) +{ + pthread_mutex_lock ( &mut_smap ); + obj_type ret_val = hmap<obj_type,key_type>::get_elem( k ); + pthread_mutex_unlock( &mut_smap ); + return ret_val; +} +template <class obj_type, class key_type> +obj_type smap<obj_type, key_type>::pop_elem( const key_type &k ) +{ + pthread_mutex_lock ( &mut_smap ); + obj_type ret_val = hmap<obj_type,key_type>::pop_elem( k ); + pthread_mutex_unlock( &mut_smap ); + return ret_val; +} + +template <class obj_type, class key_type> +bool smap<obj_type, key_type>::is_avail( const key_type &k ) +{ + pthread_mutex_lock ( &mut_smap ); + bool ret_val = hmap<obj_type,key_type>::is_avail( k ); + pthread_mutex_unlock( &mut_smap ); + return ret_val; +} + +template<class obj_type, class key_type> void +smap<obj_type, key_type>::run_func( void (*func)(obj_type) ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::run_func( func ); + pthread_mutex_unlock( &mut_smap ); +} + +template<class obj_type, class key_type> void +smap<obj_type, key_type>::run_func( void (*func)(obj_type, void*), void* v_arg ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::run_func( func, v_arg ); + pthread_mutex_unlock( &mut_smap ); +} + +template<class obj_type, class key_type> void +smap<obj_type, key_type>::run_func_on( void (*func)(obj_type), const key_type & k ) +{ + pthread_mutex_lock ( &mut_smap ); + hmap<obj_type,key_type>::run_func_on( func, k ); + pthread_mutex_unlock( &mut_smap ); +} + +template<class obj_type, class key_type> vector<key_type>* +smap<obj_type, key_type>::get_key_vector() +{ + pthread_mutex_lock ( &mut_smap ); + vector<key_type>* p_ret_vector = hmap<obj_type,key_type>::get_key_vector(); + pthread_mutex_unlock( &mut_smap ); + return p_ret_vector; +} + +// INSECURE METHODS + +template <class obj_type, class key_type> int +smap<obj_type, key_type>::get_size_insecure() +{ + return hmap<obj_type,key_type>::get_size(); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::make_empty_insecure() +{ + hmap<obj_type,key_type>::make_empty(); +} + +template <class obj_type, class key_type> +void smap<obj_type, key_type>::make_empty_insecure( void (*func)(key_type) ) +{ + hmap<obj_type,key_type>::make_empty( func ); +} + +template <class obj_type, class key_type> +void smap<obj_type, key_type>::add_elem_insecure( const obj_type &x, const key_type &k ) +{ + hmap<obj_type,key_type>::add_elem( x, k ); +} + +template <class obj_type, class key_type> void +smap<obj_type, key_type>::del_elem_insecure( const key_type & k ) +{ + hmap<obj_type,key_type>::del_elem( k ); +} + +template <class obj_type, class key_type> +obj_type smap<obj_type, key_type>::get_elem_insecure( const key_type &k ) +{ + return hmap<obj_type,key_type>::get_elem( k ); +} + +template <class obj_type, class key_type> +obj_type smap<obj_type, key_type>::pop_elem_insecure( const key_type &k ) +{ + return hmap<obj_type,key_type>::pop_elem( k ); +} + +template <class obj_type, class key_type> +bool smap<obj_type, key_type>::is_avail_insecure( const key_type &k ) +{ + return hmap<obj_type,key_type>::is_avail( k ); +} + +template<class obj_type, class key_type> void +smap<obj_type, key_type>::run_func_insecure( void (*func)(obj_type) ) +{ + hmap<obj_type,key_type>::run_func( func ); +} + +template<class obj_type, class key_type> void +smap<obj_type, key_type>::run_func_insecure( void (*func)(obj_type, void*), void* v_arg ) +{ + hmap<obj_type,key_type>::run_func( func, v_arg ); +} + +template<class obj_type, class key_type> vector<key_type>* +smap<obj_type, key_type>::get_key_vector_insecure() +{ + return hmap<obj_type,key_type>::get_key_vector(); +} + +#endif |