1/* -*- c-basic-offset: 2 -*- */
2/*
3 Copyright(C) 2016-2017 Brazil
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License version 2.1 as published by the Free Software Foundation.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public
15 License along with this library; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17*/
18
19#include "grn_ctx.h"
20#include "grn_db.h"
21#include "grn_expr.h"
22#include "grn_window_function.h"
23
24#include <string.h>
25
26grn_rc
27grn_window_init(grn_ctx *ctx,
28 grn_window *window,
29 grn_obj *table,
30 grn_bool is_sorted)
31{
32 GRN_API_ENTER;
33
34 window->table = table;
35 GRN_RECORD_INIT(&(window->ids), GRN_OBJ_VECTOR, grn_obj_id(ctx, table));
36 window->n_ids = 0;
37 window->current_index = 0;
38 window->direction = GRN_WINDOW_DIRECTION_ASCENDING;
39 window->is_sorted = is_sorted;
40
41 GRN_API_RETURN(GRN_SUCCESS);
42}
43
44grn_rc
45grn_window_fin(grn_ctx *ctx, grn_window *window)
46{
47 GRN_API_ENTER;
48
49 GRN_OBJ_FIN(ctx, &(window->ids));
50
51 GRN_API_RETURN(GRN_SUCCESS);
52}
53
54grn_id
55grn_window_next(grn_ctx *ctx, grn_window *window)
56{
57 grn_id next_id;
58
59 GRN_API_ENTER;
60
61 if (!window) {
62 GRN_API_RETURN(GRN_ID_NIL);
63 }
64
65 if (window->direction == GRN_WINDOW_DIRECTION_ASCENDING) {
66 if (window->current_index >= window->n_ids) {
67 GRN_API_RETURN(GRN_ID_NIL);
68 }
69 } else {
70 if (window->current_index < 0) {
71 GRN_API_RETURN(GRN_ID_NIL);
72 }
73 }
74
75 next_id = GRN_RECORD_VALUE_AT(&(window->ids), window->current_index);
76 if (window->direction == GRN_WINDOW_DIRECTION_ASCENDING) {
77 window->current_index++;
78 } else {
79 window->current_index--;
80 }
81
82 GRN_API_RETURN(next_id);
83}
84
85grn_rc
86grn_window_rewind(grn_ctx *ctx, grn_window *window)
87{
88 GRN_API_ENTER;
89
90 if (!window) {
91 ERR(GRN_INVALID_ARGUMENT, "[window][rewind] window is NULL");
92 GRN_API_RETURN(ctx->rc);
93 }
94
95 if (window->direction == GRN_WINDOW_DIRECTION_ASCENDING) {
96 window->current_index = 0;
97 } else {
98 window->current_index = window->n_ids - 1;
99 }
100
101 GRN_API_RETURN(GRN_SUCCESS);
102}
103
104grn_obj *
105grn_window_get_table(grn_ctx *ctx, grn_window *window)
106{
107 GRN_API_ENTER;
108
109 if (!window) {
110 ERR(GRN_INVALID_ARGUMENT, "[window][rewind] window is NULL");
111 GRN_API_RETURN(NULL);
112 }
113
114 GRN_API_RETURN(window->table);
115}
116
117grn_rc
118grn_window_set_direction(grn_ctx *ctx,
119 grn_window *window,
120 grn_window_direction direction)
121{
122 GRN_API_ENTER;
123
124 if (!window) {
125 ERR(GRN_INVALID_ARGUMENT, "[window][set][direction] window is NULL");
126 GRN_API_RETURN(ctx->rc);
127 }
128
129 switch (direction) {
130 case GRN_WINDOW_DIRECTION_ASCENDING :
131 window->direction = direction;
132 window->current_index = 0;
133 break;
134 case GRN_WINDOW_DIRECTION_DESCENDING :
135 window->direction = direction;
136 window->current_index = window->n_ids - 1;
137 break;
138 default :
139 ERR(GRN_INVALID_ARGUMENT,
140 "[window][set][direction] direction must be "
141 "GRN_WINDOW_DIRECTION_ASCENDING(%d) or "
142 "GRN_WINDOW_DIRECTION_DESCENDING(%d): %d",
143 GRN_WINDOW_DIRECTION_ASCENDING,
144 GRN_WINDOW_DIRECTION_DESCENDING,
145 direction);
146 GRN_API_RETURN(ctx->rc);
147 break;
148 }
149
150 GRN_API_RETURN(GRN_SUCCESS);
151}
152
153static inline void
154grn_window_reset(grn_ctx *ctx,
155 grn_window *window)
156{
157 GRN_BULK_REWIND(&(window->ids));
158}
159
160static inline void
161grn_window_add_record(grn_ctx *ctx,
162 grn_window *window,
163 grn_id record_id)
164{
165 GRN_RECORD_PUT(ctx, &(window->ids), record_id);
166}
167
168static inline grn_bool
169grn_window_is_empty(grn_ctx *ctx,
170 grn_window *window)
171{
172 return GRN_BULK_VSIZE(&(window->ids)) == 0;
173}
174
175grn_bool
176grn_window_is_sorted(grn_ctx *ctx, grn_window *window)
177{
178 GRN_API_ENTER;
179
180 if (!window) {
181 ERR(GRN_INVALID_ARGUMENT, "[window][is-sorted] window is NULL");
182 GRN_API_RETURN(GRN_FALSE);
183 }
184
185 GRN_API_RETURN(window->is_sorted);
186}
187
188size_t
189grn_window_get_size(grn_ctx *ctx,
190 grn_window *window)
191{
192 GRN_API_ENTER;
193
194 GRN_API_RETURN(window->n_ids);
195}
196
197grn_obj *
198grn_window_function_create(grn_ctx *ctx,
199 const char *name,
200 int name_size,
201 grn_window_function_func func)
202{
203 grn_obj *window_function = NULL;
204
205 GRN_API_ENTER;
206
207 if (name_size == -1) {
208 name_size = strlen(name);
209 }
210
211 window_function = grn_proc_create(ctx,
212 name,
213 name_size,
214 GRN_PROC_WINDOW_FUNCTION,
215 NULL, NULL, NULL, 0, NULL);
216 if (!window_function) {
217 ERR(GRN_WINDOW_FUNCTION_ERROR,
218 "[window-function][%.*s] failed to create proc: %s",
219 name_size, name,
220 ctx->errbuf);
221 GRN_API_RETURN(NULL);
222 }
223
224 {
225 grn_proc *proc = (grn_proc *)window_function;
226 proc->callbacks.window_function = func;
227 }
228
229 GRN_API_RETURN(window_function);
230}
231
232static grn_bool
233grn_expr_is_window_function_call(grn_ctx *ctx,
234 grn_obj *window_function_call)
235{
236 grn_expr *expr = (grn_expr *)window_function_call;
237 grn_expr_code *func;
238 grn_expr_code *call;
239
240 func = &(expr->codes[0]);
241 call = &(expr->codes[expr->codes_curr - 1]);
242
243 if (func->op != GRN_OP_PUSH) {
244 return GRN_FALSE;
245 }
246 if (!grn_obj_is_window_function_proc(ctx, func->value)) {
247 return GRN_FALSE;
248 }
249
250 if (call->op != GRN_OP_CALL) {
251 return GRN_FALSE;
252 }
253 if (call->nargs != (expr->codes_curr - 1)) {
254 return GRN_FALSE;
255 }
256
257 return GRN_TRUE;
258}
259
260static grn_rc
261grn_expr_call_window_function(grn_ctx *ctx,
262 grn_obj *output_column,
263 grn_window *window,
264 grn_obj *window_function_call)
265{
266 grn_rc rc;
267 grn_expr *expr = (grn_expr *)window_function_call;
268 grn_proc *proc;
269 int32_t i, n;
270 grn_obj args;
271
272 proc = (grn_proc *)(expr->codes[0].value);
273
274 GRN_PTR_INIT(&args, GRN_OBJ_VECTOR, GRN_ID_NIL);
275 n = expr->codes_curr - 1;
276 for (i = 1; i < n; i++) {
277 /* TODO: Check op. */
278 GRN_PTR_PUT(ctx, &args, expr->codes[i].value);
279 }
280 window->n_ids = GRN_BULK_VSIZE(&(window->ids)) / sizeof(grn_id);
281 if (window->direction == GRN_WINDOW_DIRECTION_ASCENDING) {
282 window->current_index = 0;
283 } else {
284 window->current_index = window->n_ids - 1;
285 }
286 rc = proc->callbacks.window_function(ctx,
287 output_column,
288 window,
289 (grn_obj **)GRN_BULK_HEAD(&args),
290 GRN_BULK_VSIZE(&args) / sizeof(grn_obj *));
291 GRN_OBJ_FIN(ctx, &args);
292
293 return rc;
294}
295
296grn_rc
297grn_table_apply_window_function(grn_ctx *ctx,
298 grn_obj *table,
299 grn_obj *output_column,
300 grn_window_definition *definition,
301 grn_obj *window_function_call)
302{
303 GRN_API_ENTER;
304
305 if (!table) {
306 ERR(GRN_INVALID_ARGUMENT,
307 "[table][apply][window-function] table is NULL");
308 GRN_API_RETURN(ctx->rc);
309 }
310
311 if (!grn_expr_is_window_function_call(ctx, window_function_call)) {
312 grn_obj inspected;
313 GRN_TEXT_INIT(&inspected, 0);
314 grn_inspect(ctx, &inspected, window_function_call);
315 ERR(GRN_INVALID_ARGUMENT,
316 "[table][apply][window-function] must be window function call: %.*s",
317 (int)GRN_TEXT_LEN(&inspected),
318 GRN_TEXT_VALUE(&inspected));
319 GRN_OBJ_FIN(ctx, &inspected);
320 GRN_API_RETURN(ctx->rc);
321 }
322
323 {
324 size_t n_sort_keys;
325 grn_table_sort_key *sort_keys;
326 grn_obj *sorted;
327 grn_window window;
328
329 n_sort_keys = definition->n_group_keys + definition->n_sort_keys;
330 sort_keys = GRN_MALLOCN(grn_table_sort_key, n_sort_keys);
331 if (!sort_keys) {
332 grn_rc rc = ctx->rc;
333 if (rc == GRN_SUCCESS) {
334 rc = GRN_NO_MEMORY_AVAILABLE;
335 }
336 ERR(rc,
337 "[table][apply][window-function] "
338 "failed to allocate internal sort keys: %s",
339 ctx->errbuf);
340 GRN_API_RETURN(ctx->rc);
341 }
342 {
343 size_t i;
344 for (i = 0; i < definition->n_group_keys; i++) {
345 sort_keys[i] = definition->group_keys[i];
346 }
347 for (i = 0; i < definition->n_sort_keys; i++) {
348 sort_keys[i + definition->n_group_keys] = definition->sort_keys[i];
349 }
350 }
351 sorted = grn_table_create(ctx,
352 NULL, 0, NULL,
353 GRN_OBJ_TABLE_NO_KEY,
354 NULL,
355 table);
356 if (!sorted) {
357 grn_rc rc = ctx->rc;
358 if (rc == GRN_SUCCESS) {
359 rc = GRN_NO_MEMORY_AVAILABLE;
360 }
361 GRN_FREE(sort_keys);
362 ERR(rc,
363 "[table][apply][window-function] "
364 "failed to allocate table to store sorted result: %s",
365 ctx->errbuf);
366 GRN_API_RETURN(ctx->rc);
367 }
368 grn_table_sort(ctx,
369 table,
370 0, -1,
371 sorted,
372 sort_keys, n_sort_keys);
373
374 grn_window_init(ctx, &window, table, definition->n_sort_keys > 0);
375 if (definition->n_group_keys > 0) {
376 grn_obj *previous_values;
377 grn_obj *current_values;
378 size_t i, n;
379
380 previous_values = GRN_MALLOCN(grn_obj, definition->n_group_keys);
381 current_values = GRN_MALLOCN(grn_obj, definition->n_group_keys);
382 n = definition->n_group_keys;
383
384 for (i = 0; i < n; i++) {
385 GRN_VOID_INIT(&(previous_values[i]));
386 GRN_VOID_INIT(&(current_values[i]));
387 }
388
389 GRN_TABLE_EACH_BEGIN(ctx, sorted, cursor, id) {
390 void *value;
391 grn_id record_id;
392 grn_bool is_group_key_changed = GRN_FALSE;
393
394 grn_table_cursor_get_value(ctx, cursor, &value);
395 record_id = *((grn_id *)value);
396
397 for (i = 0; i < n; i++) {
398 size_t reverse_i = n - i - 1;
399 grn_obj *previous_value = &(previous_values[reverse_i]);
400 grn_obj *current_value = &(current_values[reverse_i]);
401 grn_obj *group_key = definition->group_keys[reverse_i].key;
402
403 if (is_group_key_changed) {
404 GRN_BULK_REWIND(previous_value);
405 grn_obj_get_value(ctx, group_key, record_id, previous_value);
406 } else {
407 GRN_BULK_REWIND(current_value);
408 grn_obj_get_value(ctx, group_key, record_id, current_value);
409 if ((GRN_BULK_VSIZE(current_value) !=
410 GRN_BULK_VSIZE(previous_value)) ||
411 (memcmp(GRN_BULK_HEAD(current_value),
412 GRN_BULK_HEAD(previous_value),
413 GRN_BULK_VSIZE(current_value)) != 0)) {
414 is_group_key_changed = GRN_TRUE;
415 grn_bulk_write_from(ctx,
416 previous_value,
417 GRN_BULK_HEAD(current_value),
418 0,
419 GRN_BULK_VSIZE(current_value));
420 }
421 }
422 }
423
424 if (is_group_key_changed && !grn_window_is_empty(ctx, &window)) {
425 grn_expr_call_window_function(ctx,
426 output_column,
427 &window,
428 window_function_call);
429 grn_window_reset(ctx, &window);
430 }
431 grn_window_add_record(ctx, &window, record_id);
432 } GRN_TABLE_EACH_END(ctx, cursor);
433 grn_expr_call_window_function(ctx,
434 output_column,
435 &window,
436 window_function_call);
437
438 for (i = 0; i < definition->n_group_keys; i++) {
439 GRN_OBJ_FIN(ctx, &(previous_values[i]));
440 GRN_OBJ_FIN(ctx, &(current_values[i]));
441 }
442 GRN_FREE(previous_values);
443 GRN_FREE(current_values);
444 } else {
445 GRN_TABLE_EACH_BEGIN(ctx, sorted, cursor, id) {
446 void *value;
447 grn_id record_id;
448
449 grn_table_cursor_get_value(ctx, cursor, &value);
450 record_id = *((grn_id *)value);
451 grn_window_add_record(ctx, &window, record_id);
452 } GRN_TABLE_EACH_END(ctx, cursor);
453 grn_expr_call_window_function(ctx,
454 output_column,
455 &window,
456 window_function_call);
457 }
458 grn_window_fin(ctx, &window);
459
460 GRN_FREE(sort_keys);
461 }
462
463 GRN_API_RETURN(ctx->rc);
464}
465