source: branches/parallel/src/TableTraverse.cpp@ 2283

Last change on this file since 2283 was 2283, checked in by KohjiNakamura, 14 years ago

Non-PlainColumn supported by TableTraverse

File size: 5.9 KB
Line 
1//
2// C++ Interface: Scantable
3//
4// Description:
5//
6// Copyright: See COPYING file that comes with this distribution
7//
8
9#include <stdio.h>
10#include <stdlib.h>
11#include <TableTraverse.h>
12#include <tables/Tables/TableColumn.h>
13#include <tables/Tables/PlainColumn.h>
14#include <tables/Tables/DataManager.h>
15
16#define TIMING 0
17
18#if TIMING
19#include <sys/time.h>
20#endif
21
22static const char version[] = "$Id$";
23
24using namespace casa;
25
26namespace asap {
27 class Comparator {
28 public:
29 virtual ~Comparator() {}
30 virtual int compare(const void *a, const void *b) = 0;
31 };
32
33 class CompContext: public Comparator {
34 uInt nCols;
35 void const *const *colValues;
36 const TypeManager *const* typeManagers;
37 public:
38 CompContext(uInt nCols, void const *const colValues[],
39 const TypeManager *const typeManagers[])
40 : nCols(nCols), colValues(colValues), typeManagers(typeManagers) {
41 DebugAssert(colValues != NULL, AipsError);
42 DebugAssert(typeManagers != NULL, AipsError);
43 for (uInt i = 0; i < nCols; i++) {
44 DebugAssert(colValues[i] != NULL, AipsError);
45 DebugAssert(typeManagers[i] != NULL, AipsError);
46 }
47 }
48
49 virtual int compare(const void *a, const void *b) {
50 uInt ai = *(uInt*)a;
51 uInt bi = *(uInt*)b;
52 for (size_t i = 0; i < nCols; i++) {
53 const size_t valueSize = typeManagers[i]->sizeOf();
54 const char *values = (const char *)colValues[i];
55 int diff = typeManagers[i]->getComparator()->comp(&values[ai*valueSize], &values[bi*valueSize]);
56 if (diff != 0) {
57 return diff;
58 }
59 }
60 return 0;
61 }
62 };
63}
64
65#if TIMING
66static double currenttime()
67{
68 struct timeval tv;
69 int result = gettimeofday(&tv, NULL);
70 return tv.tv_sec + ((double)tv.tv_usec) / 1000000.;
71}
72#endif
73
74static inline void swap_(char *a, char *b, size_t size)
75{
76 char tmp[size];
77 char *p = tmp;
78 do {
79 *p = *a;
80 *a++ = *b;
81 *b++ = *p++;
82 } while (--size > 0);
83}
84
85static inline void cpy(char *dest, char *src, size_t size)
86{
87 for (size_t i = 0; i < size; i++) {
88 dest[i] = src[i];
89 }
90}
91
92static void sort_(char *left, char *right, const size_t size,
93 asap::Comparator *comp, int level)
94{
95 const size_t len = (right - left) / size;
96 if (len < 2) {
97 return;
98 }
99 size_t mid = len >> 1;
100 char *l = left;
101 char *r = right - size;
102 char pivot[size] __attribute__ ((aligned (16)));
103 cpy(pivot, &left[mid*size], size);
104 while (true) {
105 while (l < r && comp->compare(l, pivot) < 0) {
106 l += size;
107 }
108 while (l < r && comp->compare(r, pivot) > 0) {
109 r -= size;
110 }
111 if (l >= r) {
112 break;
113 }
114 swap_(l, r, size);
115 l += size;
116 r -= size;
117 }
118 sort_(left, l, size, comp, level + 1);
119 sort_(l, right, size, comp, level + 1);
120}
121
122static inline void modernQSort(void *base, size_t elements, size_t size,
123 asap::Comparator *comp)
124{
125 sort_((char *)base, &((char *)base)[elements * size], size, comp, 0);
126}
127
128namespace asap {
129 class ROTableColumnBackDoor: public ROTableColumn {
130 public:
131 static BaseColumn *baseColumnPtr(const ROTableColumn *col)
132 {
133 return ((ROTableColumnBackDoor*)col)->baseColPtr();
134 }
135 };
136
137 static void copyColumnData(void *colValues, size_t elementSize, uInt nRows,
138 BaseColumn *refCol)
139 {
140 char *base = (char *)colValues;
141 for (uInt i = 0; i < nRows; i++) {
142 refCol->get(i, &base[elementSize * i]);
143 }
144 }
145
146 void traverseTable(const Table &table,
147 const char *const columnNames[],
148 const TypeManager *const typeManagers[],
149 TableVisitor *visitor,
150 Bool doSort)
151 {
152#if TIMING
153 double s = currenttime();
154#endif
155 uInt colCount = 0;
156 for (; columnNames[colCount]; colCount++) {
157 AlwaysAssert(typeManagers[colCount], AipsError);
158 }
159
160 ROTableColumn *cols[colCount];
161 void *colValues[colCount];
162 for (uInt i = 0; i < colCount; i++) {
163 cols[i] = NULL;
164 colValues[i] = NULL;
165 }
166 size_t sizes[colCount];
167 const uInt nRows = table.nrow();
168 for (uInt i = 0; i < colCount; i++) {
169 cols[i] = new ROTableColumn(table, columnNames[i]);
170 colValues[i] = typeManagers[i]->allocArray(nRows);
171 sizes[i] = typeManagers[i]->sizeOf();
172 BaseColumn *baseCol = ROTableColumnBackDoor::baseColumnPtr(cols[i]);
173 PlainColumn *col = dynamic_cast <PlainColumn *>(baseCol);
174 if (col) {
175 const uInt gotRows = col->dataManagerColumn()->
176 getBlockV(0, nRows, colValues[i]);
177 DebugAssert(gotRows == nRows, AipsError);
178 } else {
179 copyColumnData(colValues[i], typeManagers[i]->sizeOf(), nRows, baseCol);
180 }
181 }
182
183 uInt *idx = new uInt[nRows];
184 for (uInt i = 0; i < nRows; i++) {
185 idx[i] = i;
186 }
187
188 try {
189 if (doSort) {
190 CompContext compCtx(colCount, colValues, typeManagers);
191 modernQSort(idx, nRows, sizeof(idx[0]), &compCtx);
192 }
193
194 visitor->start();
195 Bool first = True;
196 for (uInt i = 0; i < nRows; i++) {
197 if (visitor->visit(first, idx[i], colCount, colValues) == False) {
198 break;
199 }
200 first = False;
201 }
202 visitor->finish();
203 } catch (...) {
204 delete[] idx;
205 for (uInt i = 0; i < colCount; i++) {
206 typeManagers[i]->freeArray(colValues[i]);
207 delete cols[i];
208 }
209 throw;
210 }
211
212 delete[] idx;
213 for (uInt i = 0; i < colCount; i++) {
214 typeManagers[i]->freeArray(colValues[i]);
215 delete cols[i];
216 }
217
218#if TIMING
219 double e = currenttime();
220 printf("%s took %.3f sec\n", __PRETTY_FUNCTION__, e - s);
221#endif
222 }
223}
224
225#if 0
226using namespace asap ;
227
228class MyComp: public Comparator {
229public:
230 virtual int compare(const void *a, const void *b) {
231 return (*(int*)a) - (*(int*)b);
232 }
233};
234
235int main()
236{
237 srand((int)currenttime());
238 int x[100];
239 printf("init\n");
240 for (int i = 0; i < 100; i++) {
241 x[i] = rand() % 100;
242 }
243 MyComp myComp;
244 printf("sorting\n");
245 modernQSort(x, 1, sizeof(x[0]), &myComp);
246 modernQSort(x, 2, sizeof(x[0]), &myComp);
247 modernQSort(x, 3, sizeof(x[0]), &myComp);
248 modernQSort(x, 100, sizeof(x[0]), &myComp);
249 for (int i = 0; i < 100; i++) {
250 printf("%d\n", x[i]);
251 }
252}
253#endif
Note: See TracBrowser for help on using the repository browser.