FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
bulk_operate_ext.h
1 #ifndef __BULK_OPERATE_EXT_H__
2 #define __BULK_OPERATE_EXT_H__
3 
4 /*
5  * Copyright 2015 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of FlashMatrix.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include "comm_exception.h"
24 #include "bulk_operate.h"
25 
26 namespace fm
27 {
28 
29 /*
30  * This is the interface for aggregating elements into a single element.
31  */
32 class agg_operate
33 {
34  bulk_operate::const_ptr agg;
35  bulk_operate::const_ptr combine;
36 
37  agg_operate(bulk_operate::const_ptr agg, bulk_operate::const_ptr combine) {
38  this->agg = agg;
39  this->combine = combine;
40  }
41 public:
42  typedef std::shared_ptr<const agg_operate> const_ptr;
43 
44  static const_ptr create(bulk_operate::const_ptr agg);
45 
46  static const_ptr create(bulk_operate::const_ptr agg,
47  bulk_operate::const_ptr combine);
48 
49  bool has_combine() const {
50  return combine != NULL;
51  }
52 
53  const bulk_operate &get_agg() const {
54  return *agg;
55  }
56 
57  const bulk_operate &get_combine() const {
58  return *combine;
59  }
60 
61  void runAgg(size_t num_eles, const void *left_arr, const void *orig,
62  void *output) const {
63  agg->runAgg(num_eles, left_arr, orig, output);
64  }
65 
66  /*
67  * This combines the partially aggregated result.
68  * The input and output types of this method are both the output type of
69  * the aggregation.
70  */
71  void runCombine(size_t num_eles, const void *in, const void *orig,
72  void *out) const {
73  assert(combine);
74  combine->runAgg(num_eles, in, orig, out);
75  }
76 
77  const scalar_type &get_input_type() const {
78  return agg->get_left_type();
79  }
80  const scalar_type &get_output_type() const {
81  return agg->get_output_type();
82  }
83 };
84 
85 /*
86  * Find the first location where its element is different from the first
87  * element in the array.
88  */
89 template<class T>
90 class find_next_impl: public bulk_operate
91 {
92 public:
93  virtual void runAA(size_t num_eles, const void *left_arr,
94  const void *right_arr, void *output_arr) const {
95  throw unsupported_exception();
96  }
97  virtual void runAE(size_t num_eles, const void *left_arr,
98  const void *right, void *output_arr) const {
99  throw unsupported_exception();
100  }
101  virtual void runEA(size_t num_eles, const void *left,
102  const void *right_arr, void *output_arr) const {
103  throw unsupported_exception();
104  }
105 
106  /*
107  * The first element in the array is pointed by `left_arr' and there are
108  * `num_eles' in the array.
109  * If all elements are the same, it returns the number of elements
110  * in the array.
111  */
112  virtual void runAgg(size_t num_eles, const void *left_arr, const void *orig,
113  void *output) const {
114  const T *curr = (const T *) left_arr;
115  T val = *curr;
116  size_t loc = 1;
117  for (; loc < num_eles && curr[loc] == val; loc++);
118  *(size_t *) output = loc;
119  }
120 
121  virtual const scalar_type &get_left_type() const {
122  return get_scalar_type<T>();
123  }
124  virtual const scalar_type &get_right_type() const {
125  return get_scalar_type<T>();
126  }
127  virtual const scalar_type &get_output_type() const {
128  return get_scalar_type<size_t>();
129  }
130 };
131 
132 /*
133  * Search backwards and find the first location where its element is different
134  * from the last element in the array.
135  */
136 template<class T>
137 class find_prev_impl: public bulk_operate
138 {
139 public:
140  virtual void runAA(size_t num_eles, const void *left_arr,
141  const void *right_arr, void *output_arr) const {
142  throw unsupported_exception();
143  }
144  virtual void runAE(size_t num_eles, const void *left_arr,
145  const void *right, void *output_arr) const {
146  throw unsupported_exception();
147  }
148  virtual void runEA(size_t num_eles, const void *left,
149  const void *right_arr, void *output_arr) const {
150  throw unsupported_exception();
151  }
152 
153  /*
154  * The end of the array is indicated by `arr_end'. The last element
155  * is right before `arr_end'. There are `num_eles' elements in the array.
156  * If all elements are the same, it returns the number of elements
157  * in the array.
158  */
159  virtual void runAgg(size_t num_eles, const void *arr_end, const void *orig,
160  void *output) const {
161  const T *curr = ((const T *) arr_end) - 1;
162  T val = *curr;
163  const T *first = ((const T *) arr_end) - num_eles;
164  for (; curr > first && *curr == val; curr--);
165  if (*curr != val)
166  curr++;
167  assert(*curr == val);
168  *(size_t *) output = ((const T *) arr_end) - curr;
169  }
170 
171  virtual const scalar_type &get_left_type() const {
172  return get_scalar_type<T>();
173  }
174  virtual const scalar_type &get_right_type() const {
175  return get_scalar_type<T>();
176  }
177  virtual const scalar_type &get_output_type() const {
178  return get_scalar_type<size_t>();
179  }
180 };
181 
182 template<class T>
183 class count_operate: public bulk_operate
184 {
185 public:
186  virtual void runAA(size_t num_eles, const void *left_arr,
187  const void *right_arr, void *output_arr) const {
188  throw unsupported_exception();
189  }
190  virtual void runAE(size_t num_eles, const void *left_arr,
191  const void *right, void *output_arr) const {
192  throw unsupported_exception();
193  }
194  virtual void runEA(size_t num_eles, const void *left,
195  const void *right_arr, void *output_arr) const {
196  throw unsupported_exception();
197  }
198 
199  virtual void runAgg(size_t num_eles, const void *in, const void *orig,
200  void *output) const {
201  size_t *t_out = (size_t *) output;
202  if (orig == NULL)
203  t_out[0] = num_eles;
204  else
205  t_out[0] = (*(const size_t *) orig) + num_eles;
206  }
207 
208  virtual const scalar_type &get_left_type() const {
209  return get_scalar_type<T>();
210  }
211  virtual const scalar_type &get_right_type() const {
212  return get_scalar_type<T>();
213  }
214  virtual const scalar_type &get_output_type() const {
215  return get_scalar_type<size_t>();
216  }
217 };
218 
219 class agg_ops
220 {
221 protected:
222  agg_operate::const_ptr count;
223  agg_operate::const_ptr find_next;
224  agg_operate::const_ptr find_prev;
225 public:
226  typedef std::shared_ptr<agg_ops> ptr;
227 
228  agg_operate::const_ptr get_count() const {
229  return count;
230  }
231  agg_operate::const_ptr get_find_next() const {
232  return find_next;
233  }
234  agg_operate::const_ptr get_find_prev() const {
235  return find_prev;
236  }
237 };
238 
239 template<class InType, class OutType>
240 class agg_ops_impl: public agg_ops
241 {
242 public:
243  agg_ops_impl() {
244  bulk_operate::const_ptr count_agg
245  = bulk_operate::const_ptr(new count_operate<InType>());
246  count = agg_operate::create(count_agg,
247  bulk_operate::conv2ptr(
248  count_agg->get_output_type().get_basic_ops().get_add()));
249  find_next = agg_operate::create(
250  bulk_operate::const_ptr(new find_next_impl<InType>()),
251  bulk_operate::const_ptr());
252  find_prev = agg_operate::create(
253  bulk_operate::const_ptr(new find_prev_impl<InType>()),
254  bulk_operate::const_ptr());
255  }
256 };
257 
258 template<class T1, class T2>
259 class type_cast: public bulk_uoperate
260 {
261 public:
262  virtual void runA(size_t num, const void *in, void *out) const {
263  const T1 *t_in = (const T1 *) in;
264  T2 *t_out = (T2 *) out;
265  for (size_t i = 0; i < num; i++)
266  t_out[i] = t_in[i];
267  }
268  virtual const scalar_type &get_input_type() const {
269  return get_scalar_type<T1>();
270  }
271  virtual const scalar_type &get_output_type() const {
272  return get_scalar_type<T2>();
273  }
274 };
275 
276 }
277 
278 #endif