Avatar of vlzware

vlzware's solution

to React in the C Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Implement a basic reactive system.

Reactive programming is a programming paradigm that focuses on how values are computed in terms of each other to allow a change to one value to automatically propagate to other values, like in a spreadsheet.

Implement a basic reactive system with cells with settable values ("input" cells) and cells with values computed in terms of other cells ("compute" cells). Implement updates so that when an input value is changed, values propagate to reach a new stable system state.

In addition, compute cells should allow for registering change notification callbacks. Call a cell’s callbacks when the cell’s value in a new stable state has changed from the previous stable state.

Getting Started

Make sure you have read the C page on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

Passing the Tests

Get the first test compiling, linking and passing by following the three rules of test-driven development.

The included makefile can be used to create and run the tests using the test task.

make test

Create just the functions you need to satisfy any compiler errors and get the test to fail. Then write just enough code to get the test to pass. Once you've done that, move onto the next test.

As you progress through the tests, take the time to refactor your implementation for readability and expressiveness and then go on to the next test.

Try to use standard C99 facilities in preference to writing your own low-level algorithms or facilities by hand.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

test_react.c

#include <stddef.h>
#include <stdio.h>
#include "vendor/unity.h"
#include "../src/react.h"

void setUp(void)
{
}

void tearDown(void)
{
}

void test_input_cells_have_value(void)
{
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 2);

   TEST_ASSERT_EQUAL_INT(2, get_cell_value(input));

   destroy_reactor(r);
}

void test_input_cells_value_can_be_set(void)
{
   TEST_IGNORE();               // delete this line to run test
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 4);

   set_cell_value(input, 20);
   TEST_ASSERT_EQUAL_INT(20, get_cell_value(input));

   destroy_reactor(r);
}

static int plus1(int x)
{
   return x + 1;
}

void test_compute_cells_calculate_initial_value(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *output = create_compute1_cell(r, input, plus1);

   TEST_ASSERT_EQUAL_INT(2, get_cell_value(output));

   destroy_reactor(r);
}

static int concat_digits(int a, int b)
{
   TEST_IGNORE();
   return b * 10 + a;
}

void test_compute_cells_take_inputs_in_the_right_order(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *one = create_input_cell(r, 1);
   struct cell *two = create_input_cell(r, 2);
   struct cell *output = create_compute2_cell(r, one, two, concat_digits);

   TEST_ASSERT_EQUAL_INT(21, get_cell_value(output));

   destroy_reactor(r);
}

void test_compute_cells_update_value_when_dependencies_are_changed(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *output = create_compute1_cell(r, input, plus1);

   set_cell_value(input, 3);
   TEST_ASSERT_EQUAL_INT(4, get_cell_value(output));

   destroy_reactor(r);
}

static int times2(int x)
{
   return x * 2;
}

static int times30(int x)
{
   return x * 30;
}

static int plus(int x, int y)
{
   return x + y;
}

void test_compute_cells_can_depend_on_other_compute_cells(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *times_two = create_compute1_cell(r, input, times2);
   struct cell *times_thirty = create_compute1_cell(r, input, times30);
   struct cell *output = create_compute2_cell(r, times_two, times_thirty, plus);

   TEST_ASSERT_EQUAL_INT(32, get_cell_value(output));
   set_cell_value(input, 3);
   TEST_ASSERT_EQUAL_INT(96, get_cell_value(output));

   destroy_reactor(r);
}

struct cbinfo {
   int last_value;
   int times_called;
};

static void cb_spy(void *obj, int v)
{
   struct cbinfo *cbinfo = (struct cbinfo *)obj;
   cbinfo->last_value = v;
   ++cbinfo->times_called;
}

void test_compute_cells_fire_callbacks(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *output = create_compute1_cell(r, input, plus1);

   struct cbinfo cbinfo = { -1, 0 };
   add_callback(output, &cbinfo, cb_spy);

   set_cell_value(input, 3);
   TEST_ASSERT_EQUAL_INT(1, cbinfo.times_called);
   TEST_ASSERT_EQUAL_INT(4, cbinfo.last_value);

   destroy_reactor(r);
}

static void cb_noop(void *obj, int v)
{
   (void)obj;
   (void)v;
}

void test_compute_cells_dont_access_callback_obj(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *output = create_compute1_cell(r, input, plus1);

   add_callback(output, NULL, cb_noop);

   set_cell_value(input, 3);

   destroy_reactor(r);
}

static int big_if_three(int x)
{
   return x < 3 ? 111 : 222;
}

void test_callbacks_only_fire_on_change(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *output = create_compute1_cell(r, input, big_if_three);

   struct cbinfo cbinfo = { -1, 0 };
   add_callback(output, &cbinfo, cb_spy);

   set_cell_value(input, 2);
   TEST_ASSERT_EQUAL_INT(0, cbinfo.times_called);

   set_cell_value(input, 4);
   TEST_ASSERT_EQUAL_INT(1, cbinfo.times_called);
   TEST_ASSERT_EQUAL_INT(222, cbinfo.last_value);

   destroy_reactor(r);
}

void test_callbacks_can_be_added_and_removed(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 11);
   struct cell *output = create_compute1_cell(r, input, plus1);

   struct cbinfo cbinfo1 = { -1, 0 };
   callback_id cb1 = add_callback(output, &cbinfo1, cb_spy);
   struct cbinfo cbinfo2 = { -1, 0 };
   add_callback(output, &cbinfo2, cb_spy);

   set_cell_value(input, 31);

   remove_callback(output, cb1);
   struct cbinfo cbinfo3 = { -1, 0 };
   add_callback(output, &cbinfo3, cb_spy);

   set_cell_value(input, 41);

   TEST_ASSERT_EQUAL_INT(1, cbinfo1.times_called);
   TEST_ASSERT_EQUAL_INT(32, cbinfo1.last_value);
   TEST_ASSERT_EQUAL_INT(2, cbinfo2.times_called);
   TEST_ASSERT_EQUAL_INT(42, cbinfo2.last_value);
   TEST_ASSERT_EQUAL_INT(1, cbinfo3.times_called);
   TEST_ASSERT_EQUAL_INT(42, cbinfo3.last_value);

   destroy_reactor(r);
}

void test_removing_most_recent_callback(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 11);
   struct cell *output = create_compute1_cell(r, input, plus1);

   struct cbinfo cbinfo1 = { -1, 0 };
   add_callback(output, &cbinfo1, cb_spy);
   struct cbinfo cbinfo2 = { -1, 0 };
   callback_id cb2 = add_callback(output, &cbinfo2, cb_spy);
   remove_callback(output, cb2);

   set_cell_value(input, 31);

   TEST_ASSERT_EQUAL_INT(1, cbinfo1.times_called);
   TEST_ASSERT_EQUAL_INT(32, cbinfo1.last_value);
   TEST_ASSERT_EQUAL_INT(0, cbinfo2.times_called);

   destroy_reactor(r);
}

void test_removing_a_callback_multiple_times(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 11);
   struct cell *output = create_compute1_cell(r, input, plus1);

   struct cbinfo cbinfo1 = { -1, 0 };
   callback_id cb1 = add_callback(output, &cbinfo1, cb_spy);
   struct cbinfo cbinfo2 = { -1, 0 };
   add_callback(output, &cbinfo2, cb_spy);
   for (int i = 0; i < 10; ++i) {
      remove_callback(output, cb1);
   }

   set_cell_value(input, 2);

   TEST_ASSERT_EQUAL_INT(0, cbinfo1.times_called);
   TEST_ASSERT_EQUAL_INT(1, cbinfo2.times_called);
   TEST_ASSERT_EQUAL_INT(3, cbinfo2.last_value);

   destroy_reactor(r);
}

static int minus1(int x)
{
   return x - 1;
}

static int times(int x, int y)
{
   return x * y;
}

void test_callbacks_only_called_once_even_if_multiple_inputs_change(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *plus_one = create_compute1_cell(r, input, plus1);
   struct cell *minus_one1 = create_compute1_cell(r, input, minus1);
   struct cell *minus_one2 = create_compute1_cell(r, minus_one1, minus1);
   struct cell *output = create_compute2_cell(r, plus_one, minus_one2, times);

   struct cbinfo cbinfo = { -1, 0 };
   add_callback(output, &cbinfo, cb_spy);

   set_cell_value(input, 4);

   TEST_ASSERT_EQUAL_INT(1, cbinfo.times_called);
   TEST_ASSERT_EQUAL_INT(10, cbinfo.last_value);

   destroy_reactor(r);
}

static int minus(int x, int y)
{
   return x - y;
}

void test_callbacks_not_called_if_inputs_change_but_output_doesnt(void)
{
   TEST_IGNORE();
   struct reactor *r = create_reactor();
   struct cell *input = create_input_cell(r, 1);
   struct cell *plus_one = create_compute1_cell(r, input, plus1);
   struct cell *minus_one = create_compute1_cell(r, input, minus1);
   struct cell *always_two =
       create_compute2_cell(r, plus_one, minus_one, minus);

   struct cbinfo cbinfo = { -1, 0 };
   add_callback(always_two, &cbinfo, cb_spy);

   for (int i = 0; i < 10; ++i) {
      set_cell_value(input, i);
   }

   TEST_ASSERT_EQUAL_INT(0, cbinfo.times_called);

   destroy_reactor(r);
}

int main(void)
{
   UnityBegin("test/test_react.c");

   RUN_TEST(test_input_cells_have_value);
   RUN_TEST(test_input_cells_value_can_be_set);
   RUN_TEST(test_compute_cells_calculate_initial_value);
   RUN_TEST(test_compute_cells_take_inputs_in_the_right_order);
   RUN_TEST(test_compute_cells_update_value_when_dependencies_are_changed);
   RUN_TEST(test_compute_cells_can_depend_on_other_compute_cells);
   RUN_TEST(test_compute_cells_fire_callbacks);
   RUN_TEST(test_compute_cells_dont_access_callback_obj);
   RUN_TEST(test_callbacks_only_fire_on_change);
   RUN_TEST(test_callbacks_can_be_added_and_removed);
   RUN_TEST(test_removing_most_recent_callback);
   RUN_TEST(test_removing_a_callback_multiple_times);
   RUN_TEST(test_callbacks_only_called_once_even_if_multiple_inputs_change);
   RUN_TEST(test_callbacks_not_called_if_inputs_change_but_output_doesnt);

   UnityEnd();

   return 0;
}

src/react.c

#include "react.h"
#include <stdlib.h>
#include <stdio.h>

void check_alloc(void *p);
void free_list(struct cell* p);
void free_deps(struct dep* p);
int add_deps(struct cell *c, struct cell *dst);
void call_deps(struct cell *c);
void scv_helper(struct cell *c, int new_value);
void set_state(struct cell *p);
void parse_state(struct cell *p);

struct reactor *r_global = NULL;

struct reactor *create_reactor()
{
	if (r_global != NULL) {
		fprintf(stderr, "Only one reactor possible!\n");
		return NULL;
	}
	r_global = (struct reactor*) malloc(sizeof(struct reactor));
	check_alloc(r_global);

	r_global->head = NULL;

	return r_global;
}

void destroy_reactor(struct reactor *r)
{
	if (r != r_global) {
		fprintf(stderr, "Invalid reactor!\n");
		return;
	}
	free_list(r_global->head);
	free(r_global);
	r_global = NULL;
}

struct cell *create_input_cell(struct reactor *r, int initial_value)
{
	struct cell* tmp = (struct cell*) malloc(sizeof(struct cell));
	check_alloc(tmp);

	tmp->next = r->head;
	tmp->val = initial_value;
	tmp->type = INPUT;
	tmp->deps = NULL;
	int i;
	for (i = 0; i < MAXCLB; i++)
		tmp->clb[i] = NULL;

	r->head = tmp;

	return r->head;
}

struct cell *create_compute1_cell(struct reactor *r, struct cell *c,
				  compute1 fun)
{
	int val = fun(get_cell_value(c));

	struct cell *res = create_input_cell(r, val);
	res->type = ONE_VAR;
	res->fun1 = fun;
	res->dep_a = c;

	add_deps(c, res);

	return res;
}

struct cell *create_compute2_cell(struct reactor *r, struct cell *ca,
				  struct cell *cb, compute2 fun)
{
	int val = fun(get_cell_value(ca), get_cell_value(cb));

	struct cell *res = create_input_cell(r, val);
	res->type = TWO_VARS;
	res->fun2 = fun;
	res->dep_a = ca;
	res->dep_b = cb;

	add_deps(ca, res);
	add_deps(cb, res);

	return res;
}

int get_cell_value(struct cell *c)
{
	if (c == NULL)
		return -1;
	return c->val;
}

void set_cell_value(struct cell *c, int new_value)
{
	set_state(r_global->head);

	scv_helper(c, new_value);

	parse_state(r_global->head);
}

callback_id add_callback(struct cell *c, void *v, callback call)
{
	callback_id res = 0;
	while ((res < MAXCLB) && (c->clb[res] != NULL))
		res++;
	if (res == MAXCLB) {
		fprintf(stderr, "MAXCLB reached!\n");
		return -1;
	}

	c->clb[res] = call;
	c->clb_obj[res] = v;

	return res;
}

void remove_callback(struct cell *c, callback_id id)
{
	if (id < 0 || id >= MAXCLB) {
		fprintf(stderr, "Invalid callback_id!\n");
		return;
	}

	c->clb[id] = NULL;
}


/*
 ****************************************************
 * helpers
 ****************************************************
 */

void set_state(struct cell *p)
{
	if (p == NULL)
	 	return;

	if (p->next != NULL)
		set_state(p->next);

	p->clb_fire = 0;
}

void parse_state(struct cell *p)
{
	if (p == NULL)
		return;

	if (p->next != NULL)
		parse_state(p->next);

	if (p->clb_fire == 0)
	 	return;

	call_deps(p);

	int i;
	for (i = 0; i < MAXCLB; i++)
		if (p->clb[i] != NULL)
			p->clb[i](p->clb_obj[i], p->val);
}

 /* set cell values */
 void scv_helper(struct cell *c, int new_value)
 {
 	if ((c == NULL) || (c->val == new_value))
 		return;

	c->val = new_value;
	c->clb_fire = 1;
 }

void check_alloc(void *p)
{
	if (p == NULL) {
		fprintf(stderr, "Memory error!\n");
		exit(1);
	}
}

void free_list(struct cell *p)
{
	if (p == NULL)
		return;

	if (p->deps != NULL)
		free_deps(p->deps);

	if (p->next != NULL)
		free_list(p->next);

	free(p);
}

void free_deps(struct dep *p)
{
	if (p->next != NULL)
		free_deps(p->next);
	free(p);
}


int add_deps(struct cell *c, struct cell *dst)
{
	struct dep* tmp = (struct dep*) malloc(sizeof(struct dep));
	check_alloc(tmp);

	tmp->next = c->deps;
	tmp->dep = dst;
	c->deps = tmp;

	return 0;
}

void call_deps(struct cell *c)
{
	struct dep *dp = c->deps;
	while (dp != NULL) {
		struct cell *tmp = dp->dep;
		if (tmp->type == ONE_VAR)
			scv_helper(tmp,
				tmp->fun1(c->val));
		else if (tmp->type == TWO_VARS)
			scv_helper(tmp,
				tmp->fun2(tmp->dep_a->val, tmp->dep_b->val));
		dp = dp->next;
	}
}

src/react.h

/**
 * Design:
 * reactor->head points to a linked list of all cell's
 * each cell can be input, or two types of output (see compute_type)
 * dep_a and dep_b point to the cells needed to calculate fun1/fun2
 * deps is a linked list which contains every cell which depends on
 * 	the content of the current cell
 * each cell can have up to MAXCLB callbacks with their clb_obj
 * clb_fire get set to 1 if the value got updated between state changes
 */

#ifndef REACT_H
#define REACT_H

#define MAXCLB 5 /* max callbacks pro cell */

typedef int (*compute1) (int);
typedef int (*compute2) (int, int);

typedef void (*callback) (void *, int);
typedef int callback_id;

enum compute_type {INPUT, ONE_VAR, TWO_VARS};

struct dep {
	struct dep *next;
	struct cell *dep;
};

struct cell {
	int val;
	struct cell *next;

	enum compute_type type;
	compute1 fun1;
	compute2 fun2;
	struct cell *dep_a;
	struct cell *dep_b;

	struct dep *deps;

	callback clb[MAXCLB];
	void *clb_obj[MAXCLB];

	int clb_fire;
};

struct reactor {
	struct cell *head;
};

struct reactor *create_reactor();
// destroy_reactor should free all cells created under that reactor.
void destroy_reactor(struct reactor *r);

struct cell *create_input_cell(struct reactor *, int initial_value);
struct cell *create_compute1_cell(struct reactor *, struct cell *, compute1);
struct cell *create_compute2_cell(struct reactor *, struct cell *,
                                  struct cell *, compute2);

int get_cell_value(struct cell *);
void set_cell_value(struct cell *, int new_value);

// The callback should be called with the same void * given in add_callback.
callback_id add_callback(struct cell *, void *, callback);
void remove_callback(struct cell *, callback_id);

#endif

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?