Adaptive Framework  0.9.0
All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
afw_function_higher_order_list.c
Go to the documentation of this file.
1 // See the 'COPYING' file in the project root for licensing information.
2 /*
3  * afw_function_execute_* functions for higher_order_list
4  *
5  * Copyright (c) 2010-2023 Clemson University
6  *
7  */
8 
14 #include "afw_internal.h"
15 
16 typedef struct {
17  const afw_value_function_definition_t *function;
18  const afw_value_t *functor;
19  const afw_list_t *list;
20  afw_size_t n;
21  const afw_data_type_t *data_type;
22  const afw_value_t * *entry_arg_ptr;
23  const void *entry_internal;
24  const afw_value_t *entry_result;
25  void *data;
26  const afw_pool_t *p;
27  afw_xctx_t *xctx;
29 
30 typedef afw_boolean_t
31 (*impl_call_over_list_cb_t)(impl_call_over_list_cb_e_t *e);
32 
33 static void
34 impl_over_list(
36  impl_call_over_list_cb_t callback,
37  void *data)
38 {
39 
40  afw_size_t functor_argc;
41  const afw_value_t * (*functor_argv);
42  const afw_iterator_t *iterator;
44 
45  /* Initialize param. */
46  afw_memory_clear(&e);
47  e.function = x->function;
48  e.data = data;
49  e.p = x->p;
50  e.xctx = x->xctx;
51 
52  /* Create skeleton call. */
53  functor_argc = x->argc - 1;
54  functor_argv = afw_pool_calloc(e.p, sizeof(afw_value_t *) * x->argc,
55  e.xctx);
56  functor_argv[0] = afw_function_evaluate_function_parameter(
57  x->argv[1], e.p, e.xctx);
58  e.functor = afw_value_call_create(NULL, functor_argc, functor_argv,
59  e.p, e.xctx);
60 
61  /*
62  * Evaluate argv[n+1] to the new argv[n]. Replace first typed list with
63  * pointer to an allocated value of the same data type.
64  */
65  for (e.n = 1; e.n <= functor_argc; e.n++) {
66  functor_argv[e.n] = afw_value_evaluate(x->argv[e.n + 1], e.p, e.xctx);
67  if (!e.entry_arg_ptr && afw_value_is_list(functor_argv[e.n])) {
68  e.entry_arg_ptr = &functor_argv[e.n];
69  e.list = ((const afw_value_list_t *)*e.entry_arg_ptr)->internal;
70  *e.entry_arg_ptr = NULL;
71  e.data_type = afw_list_get_data_type(e.list, e.xctx);
72  if (e.data_type) {
73  *e.entry_arg_ptr = (const afw_value_t *)
74  afw_value_evaluated_allocate(e.data_type, e.p, e.xctx);
75  }
76  }
77  }
78 
79  /* There must be a typed list in parameter list. */
80  if (!e.entry_arg_ptr) {
81  AFW_THROW_ERROR_Z(arg_error, "Missing typed list arg", e.xctx);
82  }
83 
84  /* Call function with each entry in typed list as a single value. */
85  if (e.data_type) {
86  for (iterator = NULL;;) {
87  afw_list_get_next_internal(e.list, &iterator, NULL,
88  &e.entry_internal, e.xctx);
89  if (!e.entry_internal) {
90  break;
91  }
92  memcpy(AFW_VALUE_INTERNAL(*e.entry_arg_ptr), e.entry_internal,
93  e.data_type->c_type_size);
94  e.entry_result = afw_value_evaluate(e.functor, e.p, e.xctx);
95 
96  if (!callback(&e))
97  {
98  break;
99  }
100  }
101  }
102 
103  /* Call function with each entry in untyped list as a single value. */
104  else {
105  for (iterator = NULL;;) {
106  *e.entry_arg_ptr = afw_list_get_next_value(
107  e.list, &iterator, NULL, e.xctx);
108  if (!*e.entry_arg_ptr) {
109  break;
110  }
111  e.entry_result = afw_value_evaluate(e.functor, e.p, e.xctx);
112  if (!callback(&e))
113  {
114  break;
115  }
116  }
117  }
118 }
119 
120 
121 typedef struct {
122  /* stop_on passed to impl_of(). */
123  afw_boolean_t stop_on;
124 
125  /* This will be set to stop_on if found. Initialize to !stop_on. */
126  afw_boolean_t result;
128 
129 static afw_boolean_t
130 impl_of_cb(impl_call_over_list_cb_e_t *e)
131 {
132  impl_of_data_t *data = (impl_of_data_t *)e->data;
133 
134  AFW_VALUE_ASSERT_IS_DATA_TYPE(e->entry_result, boolean, e->xctx);
135 
136  /* If function returned stop_on result, return appropriate result. */
137  if (((const afw_value_boolean_t *)e->entry_result)->internal ==
138  data->stop_on)
139  {
140  data->result = data->stop_on;
141  return false;
142  }
143 
144  return true;
145 }
146 
147 static const afw_value_t *
148 impl_of(
150  afw_boolean_t stop_on)
151 {
152  impl_of_data_t data;
153 
154  data.stop_on = stop_on;
155  data.result = !stop_on; /* Assume will not be found. */
156  impl_over_list(x, impl_of_cb, (void *)&data);
157 
158  /* Return true or false based on result. */
159  return data.result ? afw_value_true : afw_value_false;
160 }
161 
162 static const afw_value_t *
163 impl_bag_of_bag(
165  afw_boolean_t all_1, afw_boolean_t all_2)
166 {
167  const afw_value_list_t *list1, *list2, *listx;
168  const afw_data_type_t *data_type_1, *data_type_2;
169  const afw_iterator_t *iterator1, *iterator2;
170  const void *internal1, *internal2;
171  void *e1, *e2;
172  const afw_value_t * f_argv[3];
173  const afw_value_t *v;
174  const afw_value_t *call;
175  afw_boolean_t is_true, any_1, any_2;
176 
177  /* The first arg is the function to call, and other 2 are typed lists. */
178  f_argv[0] = afw_function_evaluate_function_parameter(
179  x->argv[1], x->p, x->xctx);
180  call = afw_value_call_create(NULL, 2, &f_argv[0], x->p, x->xctx);
181 
184 
185  /* Work off of any* variables. */
186  any_1 = !all_1;
187  any_2 = !all_2;
188 
189  /* If any_of_all, reverse bags and any* values. */
190  if (!all_1 && all_2) {
191  listx = list1;
192  list1 = list2;
193  list2 = listx;
194  any_1 = !all_2;
195  any_2 = !all_1;
196  }
197 
198  /* Get required data type from each list. */
199  data_type_1 = afw_list_get_data_type(list1->internal, x->xctx);
200  data_type_2 = afw_list_get_data_type(list2->internal, x->xctx);
201  if (!data_type_1 || !data_type_2) {
202  AFW_THROW_ERROR_Z(general,
203  "list1 and list2 must both be typed",
204  x->xctx);
205  }
206 
207  /* Allocate a single value to use for each bag1 entry. */
209  data_type_1, x->p, x->xctx);
210  e1 = (void *)&((afw_value_evaluated_t *)f_argv[1])->internal;
211 
212  /* Allocate a single value to use for each bag2 entry. */
214  data_type_2, x->p, x->xctx);
215  e2 = (void *)&((afw_value_evaluated_t *)f_argv[2])->internal;
216 
217  /* Call function for each combination of bag1 and bag2 entries. */
218  is_true = true;
219 
220  for (iterator1 = NULL;;) {
221  afw_list_get_next_internal(list1->internal,
222  &iterator1, NULL, &internal1, x->xctx);
223  if (!internal1) {
224  break;
225  }
226  is_true = true;
227  for (iterator2 = NULL;;) {
228  afw_list_get_next_internal(list2->internal,
229  &iterator2, NULL, &internal2, x->xctx);
230  if (!internal2) {
231  break;
232  }
233  memcpy(e1, internal1, data_type_1->c_type_size);
234  memcpy(e2, internal2, data_type_2->c_type_size);
235  v = afw_value_evaluate(call, x->p, x->xctx);
236  if (!afw_value_is_boolean(v)) {
237  AFW_THROW_ERROR_Z(arg_error,
238  "First argument must be a boolean function", x->xctx);
239  }
240 
241  /* If true, indicate and break if any_2 enough. */
242  if (((const afw_value_boolean_t *)v)->internal) {
243  is_true = true;
244  if (any_2) break;
245  }
246 
247  /* If false, indicate and break if all must be true. */
248  else {
249  is_true = false;
250  if (!any_2) break;
251  }
252  }
253 
254  /* If any_1 is ok, return true. */
255  if (any_1 && is_true) break;
256 
257  /* If all must be true, return false. */
258  if (!any_1 && !is_true) break;
259  }
260 
261  /* If made it though loop, result is whatever is_true is. */
262  return (is_true) ? afw_value_true : afw_value_false;
263 }
264 
265 
266 
267 /*
268  * Adaptive function: all_of
269  *
270  * afw_function_execute_all_of
271  *
272  * See afw_function_bindings.h for more information.
273  *
274  * Returns true if all values in a list pass the predicate test.
275  *
276  * This function is pure, so it will always return the same result
277  * given exactly the same parameters and has no side effects.
278  *
279  * Declaration:
280  *
281  * ```
282  * function all_of(
283  * predicate: (function (... values: any): boolean),
284  * values_1: any,
285  * ...values_rest: (list of any)
286  * ): boolean;
287  * ```
288  *
289  * Parameters:
290  *
291  * predicate - (function (... values: any): boolean) This function is called
292  * for each value in the first list in values or until false is returned.
293  * If no calls return false, the result is true.
294  *
295  * values - (1 or more any dataType) These are the parameters passed to
296  * predicate with the exception that the first list is passed one value
297  * at a time. At least one list is required.
298  *
299  * Returns:
300  *
301  * (boolean)
302  */
303 const afw_value_t *
306 {
307  return impl_of(x, false);
308 }
309 
310 
311 
312 /*
313  * Adaptive function: all_of_all
314  *
315  * afw_function_execute_all_of_all
316  *
317  * See afw_function_bindings.h for more information.
318  *
319  * Returns true if the result of calling predicate with all of the combination
320  * of values from list1 and list2 returns true.
321  *
322  * This function is pure, so it will always return the same result
323  * given exactly the same parameters and has no side effects.
324  *
325  * Declaration:
326  *
327  * ```
328  * function all_of_all(
329  * predicate: (function (any value1: any, value2: any): boolean),
330  * list1: list,
331  * list2: list
332  * ): boolean;
333  * ```
334  *
335  * Parameters:
336  *
337  * predicate - (function (any value1: any, value2: any): boolean) The
338  * predicate is passed two parameters, the first is a value from list1
339  * and the second is a value from list2.
340  *
341  * list1 - (list)
342  *
343  * list2 - (list)
344  *
345  * Returns:
346  *
347  * (boolean)
348  */
349 const afw_value_t *
352 {
353  return impl_bag_of_bag(x, true, true);
354 }
355 
356 
357 /*
358  * Adaptive function: all_of_any
359  *
360  * afw_function_execute_all_of_any
361  *
362  * See afw_function_bindings.h for more information.
363  *
364  * This function returns true if the result of calling predicate with all of
365  * the combination of values from list1 and any of the values of list2 returns
366  * true.
367  *
368  * This function is pure, so it will always return the same result
369  * given exactly the same parameters and has no side effects.
370  *
371  * Declaration:
372  *
373  * ```
374  * function all_of_any(
375  * predicate: (function (value1: any, value2: any): boolean),
376  * list1: list,
377  * list2: list
378  * ): boolean;
379  * ```
380  *
381  * Parameters:
382  *
383  * predicate - (function (value1: any, value2: any): boolean) The predicate
384  * is passed two parameters, the first is a value from list1 and the
385  * second is a value from list2.
386  *
387  * list1 - (list)
388  *
389  * list2 - (list)
390  *
391  * Returns:
392  *
393  * (boolean)
394  */
395 const afw_value_t *
398 {
399  return impl_bag_of_bag(x, true, false);
400 }
401 
402 
403 
404 /*
405  * Adaptive function: any_of
406  *
407  * afw_function_execute_any_of
408  *
409  * See afw_function_bindings.h for more information.
410  *
411  * Returns true if any value in a list pass the predicate test.
412  *
413  * This function is pure, so it will always return the same result
414  * given exactly the same parameters and has no side effects.
415  *
416  * Declaration:
417  *
418  * ```
419  * function any_of(
420  * predicate: (function (... values: any): boolean),
421  * values_1: any,
422  * ...values_rest: (list of any)
423  * ): boolean;
424  * ```
425  *
426  * Parameters:
427  *
428  * predicate - (function (... values: any): boolean) This function is called
429  * for each value in the first list in values or until true is returned.
430  * If no calls return true, the result is false.
431  *
432  * values - (1 or more any dataType) These are the parameters passed to
433  * predicate with the exception that the first list is passed one value
434  * at a time. At least one list is required.
435  *
436  * Returns:
437  *
438  * (boolean)
439  */
440 const afw_value_t *
443 {
444  return impl_of(x, true);
445 }
446 
447 
448 
449 /*
450  * Adaptive function: any_of_all
451  *
452  * afw_function_execute_any_of_all
453  *
454  * See afw_function_bindings.h for more information.
455  *
456  * Returns true if the result of calling predicate with all of the combination
457  * of values from list2 and any of the values of list1 returns true.
458  *
459  * This function is pure, so it will always return the same result
460  * given exactly the same parameters and has no side effects.
461  *
462  * Declaration:
463  *
464  * ```
465  * function any_of_all(
466  * predicate: (function (value1: any, value2: any):boolean),
467  * list1: list,
468  * list2: list
469  * ): boolean;
470  * ```
471  *
472  * Parameters:
473  *
474  * predicate - (function (value1: any, value2: any):boolean) The predicate is
475  * passed two parameters, the first is a value from list1 and the second
476  * is a value from list2.
477  *
478  * list1 - (list)
479  *
480  * list2 - (list)
481  *
482  * Returns:
483  *
484  * (boolean)
485  */
486 const afw_value_t *
489 {
490  return impl_bag_of_bag(x, false, true);
491 }
492 
493 
494 
495 /*
496  * Adaptive function: any_of_any
497  *
498  * afw_function_execute_any_of_any
499  *
500  * See afw_function_bindings.h for more information.
501  *
502  * This function returns true if the result of calling predicate with any of
503  * the combination of values from list1 and list2 returns true.
504  *
505  * This function is pure, so it will always return the same result
506  * given exactly the same parameters and has no side effects.
507  *
508  * Declaration:
509  *
510  * ```
511  * function any_of_any(
512  * predicate: (function (value1: any, value2: any): boolean),
513  * list1: list,
514  * list2: list
515  * ): boolean;
516  * ```
517  *
518  * Parameters:
519  *
520  * predicate - (function (value1: any, value2: any): boolean) The predicate
521  * is passed two parameters, the first is a value from list1 and the
522  * second is a value from list2.
523  *
524  * list1 - (list)
525  *
526  * list2 - (list)
527  *
528  * Returns:
529  *
530  * (boolean)
531  */
532 const afw_value_t *
535 {
536  return impl_bag_of_bag(x, false, false);
537 }
538 
539 
540 
541 typedef struct {
542  const afw_list_t *filtered_list;
544 
545 static afw_boolean_t
546 impl_filter_cb(impl_call_over_list_cb_e_t *e)
547 {
548  impl_filter_data_t * data = (impl_filter_data_t *)e->data;
549 
550  AFW_VALUE_ASSERT_IS_DATA_TYPE(e->entry_result, boolean, e->xctx);
551 
552  if (((const afw_value_boolean_t *)e->entry_result)->internal) {
553  afw_list_add_internal(data->filtered_list,
554  e->data_type, e->entry_internal, e->xctx);
555  }
556 
557  return true;
558 }
559 
560 /*
561  * Adaptive function: filter
562  *
563  * afw_function_execute_filter
564  *
565  * See afw_function_bindings.h for more information.
566  *
567  * This produces a list containing only values from another list that pass a
568  * predicate test.
569  *
570  * This function is pure, so it will always return the same result
571  * given exactly the same parameters and has no side effects.
572  *
573  * Declaration:
574  *
575  * ```
576  * function filter(
577  * predicate: (function (... values: any): boolean),
578  * values_1: any,
579  * ...values_rest: (list of any)
580  * ): list;
581  * ```
582  *
583  * Parameters:
584  *
585  * predicate - (function (... values: any): boolean) This is a boolean
586  * function that is called to determine if a list entry should be
587  * included in the returned list.
588  *
589  * values - (1 or more any dataType) These are the values passed to the
590  * predicate with the exception that the first list is passed as the
591  * single current value from the list. At least one list is required.
592  *
593  * Returns:
594  *
595  * (list) This is the resulting filtered list.
596  */
597 const afw_value_t *
600 {
601  impl_filter_data_t data;
602 
603  data.filtered_list = afw_list_create_with_options(0, NULL, x->p, x->xctx);
604  impl_over_list(x, impl_filter_cb, (void *)&data);
605 
606  return afw_value_create_list(data.filtered_list, x->p, x->xctx);
607 }
608 
609 
610 
611 typedef struct {
612  const afw_value_t *found_value;
614 
615 static afw_boolean_t
616 impl_find_cb(impl_call_over_list_cb_e_t *e)
617 {
618  impl_find_data_t * data = (impl_find_data_t *)e->data;
619 
620  AFW_VALUE_ASSERT_IS_DATA_TYPE(e->entry_result, boolean, e->xctx);
621 
622  if (((const afw_value_boolean_t *)e->entry_result)->internal) {
623  data->found_value = afw_value_evaluated_create(
624  e->entry_internal, e->data_type, e->p, e->xctx);
625  return false;
626  }
627 
628  return true;
629 }
630 
631 /*
632  * Adaptive function: find
633  *
634  * afw_function_execute_find
635  *
636  * See afw_function_bindings.h for more information.
637  *
638  * The predicate is called for each value in the first list in values until
639  * true is returned, then that value is returned.
640  *
641  * This function is pure, so it will always return the same result
642  * given exactly the same parameters and has no side effects.
643  *
644  * Declaration:
645  *
646  * ```
647  * function find(
648  * predicate: (function (... values: any): boolean),
649  * values_1: any,
650  * ...values_rest: (list of any)
651  * ): any;
652  * ```
653  *
654  * Parameters:
655  *
656  * predicate - (function (... values: any): boolean) This is a boolean
657  * function that is called to determine if a list entry passes the test.
658  *
659  * values - (1 or more any dataType) These are the values passed to the
660  * predicate with the exception that the first list is passed as the
661  * single current value from the list. At least one list is required.
662  *
663  * Returns:
664  *
665  * (any dataType) The first value that passes the test is returned.
666  */
667 const afw_value_t *
670 {
671  impl_find_data_t data;
672 
673  afw_memory_clear(&data);
674  impl_over_list(x, impl_find_cb, (void *)&data);
675 
676  return (data.found_value) ? data.found_value : afw_value_null;
677 }
678 
679 
680 
681 typedef struct {
682  const afw_value_t *functor;
683  const afw_data_type_t *data_type;
684  const afw_list_t *mapped_list;
686 
687 static afw_boolean_t
688 impl_map_cb(impl_call_over_list_cb_e_t *e)
689 {
690  impl_map_data_t * data = (impl_map_data_t *)e->data;
691 
692  if (!data->mapped_list) {
693  data->data_type = e->data_type;
694  data->functor = e->functor;
695  data->mapped_list = afw_list_create_generic(e->p, e->xctx);
696  }
697 
698  afw_list_add_value(data->mapped_list, e->entry_result, e->xctx);
699 
700  return true;
701 }
702 
703 /*
704  * Adaptive function: map
705  *
706  * afw_function_execute_map
707  *
708  * See afw_function_bindings.h for more information.
709  *
710  * This function creates a list of the results of calling functor with each
711  * value of the first list in values
712  *
713  * This function is pure, so it will always return the same result
714  * given exactly the same parameters and has no side effects.
715  *
716  * Declaration:
717  *
718  * ```
719  * function map(
720  * functor: (function (... values: any): any),
721  * values_1: any,
722  * ...values_rest: (list of any)
723  * ): list;
724  * ```
725  *
726  * Parameters:
727  *
728  * functor - (function (... values: any): any)
729  *
730  * values - (1 or more any dataType) These are the parameters passed to
731  * functor with the exception that the first list is passed one value at
732  * a time. At least one list is required.
733  *
734  * Returns:
735  *
736  * (list)
737  */
738 const afw_value_t *
741 {
742  impl_map_data_t data;
743 
744  afw_memory_clear(&data);
745  impl_over_list(x, impl_map_cb, (void *)&data);
746 
747  if (!data.mapped_list) {
748  if (((afw_value_function_definition_t *)data.functor)->data_type)
749  {
751  data.functor)->data_type->empty_list_value;
752  }
753  else {
754  return afw_data_type_null->empty_list_value;
755  }
756  }
757 
759 
760  return afw_value_create_list(data.mapped_list, x->p, x->xctx);
761 }
762 
763 
764 
765 /*
766  * Adaptive function: reduce
767  *
768  * afw_function_execute_reduce
769  *
770  * See afw_function_bindings.h for more information.
771  *
772  * Reduce calls functor for each value in list with two parameters, accumulator
773  * and value, and must return a value of any dataType. Parameter accumulator is
774  * the reduce() accumulator parameter value on first call and the return value
775  * of previous functor() call on subsequent calls. The dataType of the return
776  * value should normally be the same as accumulator, but this is not required.
777  *
778  * This function is pure, so it will always return the same result
779  * given exactly the same parameters and has no side effects.
780  *
781  * Declaration:
782  *
783  * ```
784  * function reduce(
785  * functor: (function (accumulator: any, value: any): any),
786  * accumulator: any,
787  * list: list
788  * ): any;
789  * ```
790  *
791  * Parameters:
792  *
793  * functor - (function (accumulator: any, value: any): any) This function is
794  * called for each value in a list. The returned value is passed as the
795  * accumulator parameter on the next call to functor().
796  *
797  * accumulator - (any dataType) This is an initial accumulator value passed
798  * to functor(). Normally, the dataType of accumulator will be the
799  * dataTape for the reduce() return value, but this is not required.
800  *
801  * list - (list) This is a list to be reduced.
802  *
803  * Returns:
804  *
805  * (any dataType) This is the final return value from functor() or the
806  * accumulator parameter value if list is empty.
807  */
808 const afw_value_t *
811 {
812  const afw_value_list_t *list;
813  const afw_value_t *accumulator;
814  const afw_iterator_t *iterator;
815  const afw_value_t * f_argv[3];
816  const afw_value_t *call;
817 
818  f_argv[0] = afw_function_evaluate_function_parameter(
819  x->argv[1], x->p, x->xctx);
820  call = afw_value_call_create(NULL, 2, &f_argv[0], x->p, x->xctx);
823 
824  for (iterator = NULL;;) {
825  f_argv[2] = afw_list_get_next_value(list->internal, &iterator,
826  x->p, x->xctx);
827  if (!f_argv[2]) {
828  break;
829  }
830  f_argv[1] = accumulator;
831  accumulator = afw_value_evaluate(call, x->p, x->xctx);
832  }
833 
834  return accumulator;
835 }
836 
837 
838 
839 typedef struct {
840  const afw_value_t *compareFunction;
841  afw_value_evaluated_t *args[3];
842  const void **values;
843  afw_size_t c_type_size;
844  afw_size_t count;
845  const afw_pool_t *p;
846  afw_xctx_t *xctx;
848 
849 static afw_size_t
850 impl_partition(
851  impl_sort_ctx_t *ctx,
852  afw_size_t low,
853  afw_size_t high)
854 {
855  const void *pivot;
856  const void *value;
857  const afw_value_t *return_value;
858  afw_size_t i, j;
859 
860  /* Start pivot from high. */
861  pivot = ctx->values[high];
862 
863  /* Put everything to right and left of pivot based on compare. */
864  memcpy(&(ctx->args[2]->internal), pivot, ctx->c_type_size);
865  for (i = low, j = low; j <= high - 1; j++)
866  {
867  /* Call compareFunction with ctx->values[j] and pivot. */
868  memcpy(&(ctx->args[1]->internal), ctx->values[j], ctx->c_type_size);
869  return_value = afw_value_evaluate(ctx->compareFunction,
870  ctx->p, ctx->xctx);
871  AFW_VALUE_ASSERT_IS_DATA_TYPE(return_value, boolean, ctx->xctx);
872 
873  /*
874  * if compareFunction(values[j], pivot) is true, swap values[i] and
875  * value[j] then increment i
876  */
877  if (((const afw_value_boolean_t *)return_value)->internal)
878  {
879  value = ctx->values[i];
880  ctx->values[i] = ctx->values[j];
881  ctx->values[j] = value;
882  i++;
883  }
884  }
885 
886  /* Swap values[new pivot index] and values[high] */
887  value = ctx->values[i];
888  ctx->values[i] = ctx->values[high];
889  ctx->values[high] = value;
890 
891  /* Return new pivot index. */
892  return i;
893 }
894 
895 static void
896 impl_quick_sort(
897  impl_sort_ctx_t *ctx,
898  afw_size_t low,
899  afw_size_t high)
900 {
901  afw_size_t pivot_i;
902 
903  if (low < high)
904  {
905  pivot_i = impl_partition(ctx, low, high);
906  if (pivot_i > 0) {
907  impl_quick_sort(ctx, low, pivot_i - 1);
908  }
909  impl_quick_sort(ctx, pivot_i + 1, high);
910  }
911 }
912 
913 /*
914  * Adaptive function: sort
915  *
916  * afw_function_execute_sort
917  *
918  * See afw_function_bindings.h for more information.
919  *
920  * This produces a list with values sorted based on result of compareFunction.
921  * The compareFunction is passed two values from the list and must return an
922  * integer less than 0 if the first value is less than the second value, 0 if
923  * they are equal, and a integer greater than 0 if the first value is greater
924  * than the second value.
925  *
926  * This function is pure, so it will always return the same result
927  * given exactly the same parameters and has no side effects.
928  *
929  * Declaration:
930  *
931  * ```
932  * function sort(
933  * compareFunction: (function (value1: any, value2: any): integer),
934  * list: list
935  * ): list;
936  * ```
937  *
938  * Parameters:
939  *
940  * compareFunction - (function (value1: any, value2: any): integer) This
941  * function is called with two value from list.
942  *
943  * list - (list) This is the list to sort.
944  *
945  * Returns:
946  *
947  * (list) This the the resulting sorted list.
948  */
949 const afw_value_t *
952 {
953  const afw_value_list_t *list;
954  const afw_list_t *result_list;
955  const afw_data_type_t *data_type;
956  const afw_iterator_t *iterator;
957  const void **value;
958  impl_sort_ctx_t ctx;
959 
960  /* Initialize sort ctx. */
961  afw_memory_clear(&ctx);
962  ctx.p = x->p;
963  ctx.xctx = x->xctx;
964 
965  /* The first arg is the function to call, and other 2 are typed lists. */
966  ctx.args[0] = (afw_value_evaluated_t *)
967  afw_function_evaluate_function_parameter(x->argv[1], ctx.p, ctx.xctx);
968  ctx.compareFunction = afw_value_call_create(NULL,
969  2, (const afw_value_t * const *)&ctx.args[0], ctx.p, ctx.xctx);
971 
972  /* Get the data type and count. If count is 0, return empty list. */
973  data_type = afw_list_get_data_type(list->internal, ctx.xctx);
974  if (!data_type) {
975  AFW_THROW_ERROR_Z(general,
976  "sort() requires list to be typed", ctx.xctx);
977  }
978  ctx.c_type_size = data_type->c_type_size;
979  ctx.count = afw_list_get_count(list->internal, ctx.xctx);
980  if (ctx.count == 0) {
981  return data_type->empty_list_value;
982  }
983 
984  /* Allocate two values of the correct data type. */
985  ctx.args[1] = afw_value_evaluated_allocate(data_type, ctx.p, ctx.xctx);
986  ctx.args[2] = afw_value_evaluated_allocate(data_type, ctx.p, ctx.xctx);
987 
988  /* Make array of pointers to internal values. */
989  ctx.values = afw_pool_malloc(ctx.p, sizeof(void *) * ctx.count, ctx.xctx);
990  for (iterator = NULL, value = ctx.values;
991  afw_list_get_next_internal(list->internal, &iterator,
992  NULL, value, ctx.xctx);
993  value++);
994 
995  /* Sort. */
996  if (ctx.count > 0) {
997  impl_quick_sort(&ctx, 0, ctx.count - 1);
998  }
999 
1000  /* Return sorted list. */
1001  result_list = afw_list_create_wrapper_for_array(
1002  ctx.values, true, data_type, ctx.count, ctx.p, ctx.xctx);
1003  return afw_value_create_list(result_list, ctx.p, ctx.xctx);
1004 }
Adaptive Framework Core Internal.
#define afw_value_is_boolean(A_VALUE)
Macro to determine if value is evaluated boolean.
afw_value_create_list(const afw_list_t *internal, const afw_pool_t *p, afw_xctx_t *xctx)
Create function for unmanaged data type list value.
#define afw_value_is_list(A_VALUE)
Macro to determine if value is evaluated list.
afw_data_type_null
Data type struct for null.
struct afw_iterator_s afw_iterator_t
_Bool afw_boolean_t
Definition: afw_common.h:373
apr_size_t afw_size_t
size_t.
Definition: afw_common.h:151
#define AFW_THROW_ERROR_Z(code, message_z, xctx)
Macro used to set error and 0 rv in xctx and throw it.
Definition: afw_error.h:283
#define AFW_FUNCTION_EVALUATE_REQUIRED_DATA_TYPE_PARAMETER(A_RESULT, A_N, A_TYPE)
Evaluate an arg for a particular data type.
Definition: afw_function.h:328
#define AFW_FUNCTION_EVALUATE_REQUIRED_PARAMETER(A_RESULT, A_N)
Evaluate an required parameter.
Definition: afw_function.h:295
const afw_value_t * afw_function_execute_sort(afw_function_execute_t *x)
Adaptive Function sort
const afw_value_t * afw_function_execute_reduce(afw_function_execute_t *x)
Adaptive Function reduce
const afw_value_t * afw_function_execute_find(afw_function_execute_t *x)
Adaptive Function find
const afw_value_t * afw_function_execute_all_of_all(afw_function_execute_t *x)
Adaptive Function all_of_all
const afw_value_t * afw_function_execute_any_of(afw_function_execute_t *x)
Adaptive Function any_of
const afw_value_t * afw_function_execute_any_of_all(afw_function_execute_t *x)
Adaptive Function any_of_all
const afw_value_t * afw_function_execute_map(afw_function_execute_t *x)
Adaptive Function map
const afw_value_t * afw_function_execute_filter(afw_function_execute_t *x)
Adaptive Function filter
const afw_value_t * afw_function_execute_all_of(afw_function_execute_t *x)
Adaptive Function all_of
const afw_value_t * afw_function_execute_all_of_any(afw_function_execute_t *x)
Adaptive Function all_of_any
const afw_value_t * afw_function_execute_any_of_any(afw_function_execute_t *x)
Adaptive Function any_of_any
#define afw_list_get_next_internal(instance, iterator, data_type, internal, xctx)
Call method get_next_internal of interface afw_list.
#define afw_list_get_next_value(instance, iterator, p, xctx)
Call method get_next_value of interface afw_list.
#define afw_list_get_data_type(instance, xctx)
Call method get_data_type of interface afw_list.
#define afw_list_get_count(instance, xctx)
Call method get_count of interface afw_list.
afw_list_determine_data_type_and_set_immutable(const afw_list_t *instance, afw_xctx_t *xctx)
Set list to immutable and determine data type of entries.
Definition: afw_list.c:60
afw_list_create_wrapper_for_array(const void *array, afw_boolean_t indirect, const afw_data_type_t *data_type, afw_size_t count, const afw_pool_t *p, afw_xctx_t *xctx)
Create a immutable list wrapper for an array.
afw_list_add_internal(const afw_list_t *instance, const afw_data_type_t *data_type, const void *internal, afw_xctx_t *xctx)
Call method add of interface afw_list_setter.
Definition: afw_list.c:78
#define afw_list_create_generic(p, xctx)
Create an value list in memory.
Definition: afw_list.h:81
afw_list_add_value(const afw_list_t *instance, const afw_value_t *value, afw_xctx_t *xctx)
Call method add_value of interface afw_list_setter.
Definition: afw_list.c:104
const afw_list_t * afw_list_create_with_options(int options, const afw_data_type_t *data_type, const afw_pool_t *p, afw_xctx_t *xctx)
Create an list in memory with options.
#define afw_memory_clear(to)
Clear preallocated memory for sizeof(*(to)).
Definition: afw_memory.h:47
#define afw_pool_malloc(instance, size, xctx)
Call method malloc of interface afw_pool.
#define afw_pool_calloc(instance, size, xctx)
Call method calloc of interface afw_pool.
#define afw_value_evaluate(value, p, xctx)
Evaluate value if needed using specific pool.
Definition: afw_value.h:841
afw_value_evaluated_t * afw_value_evaluated_allocate(const afw_data_type_t *data_type, const afw_pool_t *p, afw_xctx_t *xctx)
Allocate function for an evaluated data type value.
afw_value_false
Adaptive value false.
Definition: afw_value.h:354
const afw_value_t * afw_value_evaluated_create(const void *value, const afw_data_type_t *data_type, const afw_pool_t *p, afw_xctx_t *xctx)
Create function for an evaluated data type value.
#define AFW_VALUE_INTERNAL(_VALUE_)
Macro to get const void * of the internal of a value.
Definition: afw_value.h:856
const afw_value_t * afw_value_call_create(const afw_compile_value_contextual_t *contextual, afw_size_t argc, const afw_value_t *const *argv, const afw_pool_t *p, afw_xctx_t *xctx)
Create function for call value.
#define AFW_VALUE_ASSERT_IS_DATA_TYPE(A_VALUE, A_DATA_TYPE, A_SCOPE)
Throw and error if A_VALUE is not evaluated data type A_DATA_TYPE.
Definition: afw_value.h:768
afw_value_null
Adaptive value null.
Definition: afw_value.h:320
afw_value_true
Adaptive value true.
Definition: afw_value.h:348
Interface afw_data_type public struct.
Function execute parameter.
Definition: afw_function.h:53
const afw_value_t *const * argv
This is the function parameters.
Definition: afw_function.h:86
afw_xctx_t * xctx
The execution context (xctx) of caller.
Definition: afw_function.h:62
const afw_value_function_definition_t * function
The evaluated function definition.
Definition: afw_function.h:71
const afw_pool_t * p
Pool for result.
Definition: afw_function.h:59
afw_size_t argc
This is the argv count not counting argv[0].
Definition: afw_function.h:89
Interface afw_list public struct.
Interface afw_pool public struct.
struct for data type boolean values.
Struct to access internal of all evaluated values.
Definition: afw_value.h:60
Struct for function value.
Definition: afw_value.h:102
struct for data type list values.
Interface afw_value public struct.
Interface afw_xctx public struct.