Rcpp Version 0.12.12
SelfHash.h
Go to the documentation of this file.
1 // -*- mode: C++; c-indent-level: 4; c-basic-offset: 4; tab-width: 4 -*-
2 //
3 // hash.h: Rcpp R/C++ interface class library -- hashing utility, inspired
4 // from Simon's fastmatch package
5 //
6 // Copyright (C) 2010, 2011 Simon Urbanek
7 // Copyright (C) 2012 Dirk Eddelbuettel and Romain Francois
8 //
9 // This file is part of Rcpp.
10 //
11 // Rcpp is free software: you can redistribute it and/or modify it
12 // under the terms of the GNU General Public License as published by
13 // the Free Software Foundation, either version 2 of the License, or
14 // (at your option) any later version.
15 //
16 // Rcpp is distributed in the hope that it will be useful, but
17 // WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU General Public License
22 // along with Rcpp. If not, see <http://www.gnu.org/licenses/>.
23 
24 #ifndef RCPP__HASH__SELF_HASH_H
25 #define RCPP__HASH__SELF_HASH_H
26 
27 namespace Rcpp{
28 namespace sugar{
29 
30 
31  template <int RTYPE>
32  class SelfHash {
33  public:
36 
37  SelfHash( SEXP table ) : n(Rf_length(table)), m(2), k(1),
38  src( (STORAGE*)dataptr(table) ), data(), indices(), size_(0)
39  {
40  int desired = n*2 ;
41  while( m < desired ){ m *= 2 ; k++ ; }
42  data.resize( m ) ;
43  indices.resize( m ) ;
44  }
45 
48  int* res = INTEGER(result) ;
49  for( int i=0; i<n; i++) res[i] = add_value_get_index(i) ;
50  return result ;
51  }
52 
53  inline int size() const {
54  return size_ ;
55  }
56 
57  int n, m, k ;
58  STORAGE* src ;
59  std::vector<int> data ;
60  std::vector<int> indices ;
61  int size_ ;
62 
63  int add_value_get_index(int i){
64  STORAGE val = src[i++] ;
65  unsigned int addr = get_addr(val) ;
66  while (data[addr] && src[data[addr] - 1] != val) {
67  addr++;
68  if (addr == static_cast<unsigned int>(m)) addr = 0;
69  }
70  if (!data[addr]) {
71  data[addr] = i ;
72  indices[addr] = ++size_ ;
73  }
74  return indices[addr] ;
75  }
76 
77  /* NOTE: we are returning a 1-based index ! */
78  unsigned int get_index(STORAGE value) const {
79  unsigned int addr = get_addr(value) ;
80  while (data[addr]) {
81  if (src[data[addr] - 1] == value)
82  return data[addr];
83  addr++;
84  if (addr == static_cast<unsigned int>(m)) addr = 0;
85  }
86  return NA_INTEGER;
87  }
88 
89  // defined below
90  unsigned int get_addr(STORAGE value) const ;
91  } ;
92 
93  template <>
94  inline unsigned int SelfHash<INTSXP>::get_addr(int value) const {
95  return RCPP_HASH(value) ;
96  }
97  template <>
98  inline unsigned int SelfHash<REALSXP>::get_addr(double val) const {
99  unsigned int addr;
100  union dint_u {
101  double d;
102  unsigned int u[2];
103  };
104  union dint_u val_u;
105  /* double is a bit tricky - we nave to normalize 0.0, NA and NaN */
106  if (val == 0.0) val = 0.0;
107  if (internal::Rcpp_IsNA(val)) val = NA_REAL;
108  else if (internal::Rcpp_IsNaN(val)) val = R_NaN;
109  val_u.d = val;
110  addr = RCPP_HASH(val_u.u[0] + val_u.u[1]);
111  return addr ;
112  }
113 
114  template <>
115  inline unsigned int SelfHash<STRSXP>::get_addr(SEXP value) const {
116  intptr_t val = (intptr_t) value;
117  unsigned int addr;
118  #if (defined _LP64) || (defined __LP64__) || (defined WIN64)
119  addr = RCPP_HASH((val & 0xffffffff) ^ (val >> 32));
120  #else
121  addr = RCPP_HASH(val);
122  #endif
123  return addr ;
124  }
125 
126 } // sugar
127 } // Rcpp
128 
129 #endif
SelfHash(SEXP table)
Definition: SelfHash.h:37
int size() const
Definition: SelfHash.h:53
std::vector< int > data
Definition: SelfHash.h:59
unsigned int get_index(STORAGE value) const
Definition: SelfHash.h:78
no_init_vector no_init(R_xlen_t size)
Definition: no_init.h:69
unsigned int get_addr(STORAGE value) const
IntegerVector table(const VectorBase< RTYPE, NA, T > &x)
Definition: table.h:126
void * dataptr(SEXP)
Definition: routines.h:206
#define RCPP_HASH(X)
Definition: IndexHash.h:46
std::vector< int > indices
Definition: SelfHash.h:60
Vector< RTYPE > VECTOR
Definition: SelfHash.h:35
int add_value_get_index(int i)
Definition: SelfHash.h:63
Rcpp API.
Definition: algo.h:28
IntegerVector fill_and_self_match()
Definition: SelfHash.h:46
traits::storage_type< RTYPE >::type STORAGE
Definition: SelfHash.h:34