Binary Search Tree in C

binarytree.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "sds/sds.h"
#include "cplayground.h"

BinaryTree* new_BinaryTree(void* val) {
  BinaryTree* bt = xmalloc(sizeof(BinaryTree));
  bt->val = val;
  bt->left = NULL;
  bt->right = NULL;
  return bt;
}

void free_BinaryTree(BinaryTree* root, BT_VAL_FREE free_val) {
  if (root == NULL) {
    return;
  }
  free_BinaryTree(root->left, free_val);
  root->left = NULL;
  
  free_BinaryTree(root->right, free_val);
  root->right = NULL;
  
  free_val(root->val);
  root->val = NULL;
  free(root);
}

BinaryTree* insert(BinaryTree* root, void* val, BT_VAL_CMP cmp) {
  if (root == NULL) {
    return new_BinaryTree(val);
  }

  // root->val >= val
  if (cmp(root->val, val) <= 0) {
    root->left = insert(root->left, val, cmp);
  }

  // root->val < val
  if (cmp(root->val, val) > 0) {
    root->right = insert(root->right, val, cmp);
  }
 
  return root;
}

BinaryTree* find(BinaryTree* root, void* val, BT_VAL_CMP cmp) {
  if (root == NULL) {
    return NULL;
  }

  if (cmp(root->val, val) == 0) {
    return root;
  }

  return find(val < root->val ? root->left : root->right, val, cmp);
}

bool exsists(BinaryTree* root, void* val, BT_VAL_CMP cmp) {
  return find(root, val, cmp) != NULL;
}

static sds rep_str(sds pat, size_t n) {
  sds ret = sdsempty();

  for (size_t i = 0; i < n; i++) {
    ret = sdscatprintf(ret, "%s", pat);
  }

  return ret;
}

static sds stringifyImpl(BinaryTree* root, BT_VAL_SHOW show, size_t depth);

static sds stringifyORNull(BinaryTree* t, BT_VAL_SHOW show, size_t depth) {
  if (t == NULL) {
    return sdsnew("NULL");
  }

  return stringifyImpl(t, show, depth);
}

static sds stringifyImpl(BinaryTree* root, BT_VAL_SHOW show, size_t depth) {
  sds pad = rep_str("  ", depth);

  return sdscatprintf(sdsempty(),
"%s<%s>"
"\n%s |L--%s"
"\n%s |R--%s", pad, show(root->val), pad, stringifyORNull(root->left, show, depth + 1),
                                                    pad, stringifyORNull(root->right, show, depth + 1));
}

sds stringify(BinaryTree* root, BT_VAL_SHOW show) {
  return stringifyImpl(root, show, 0);
}

cplayground.h

#ifndef __CPLAYGROUND_HEADER_INCLUDED__
#define __CPLAYGROUND_HEADER_INCLUDED__

#include <stddef.h>
#include "sds/sds.h"

///////////////// util ////////////////
void* xmalloc(size_t);
void xfree(void**);


/////////////// binary tree //////////////

typedef struct BinaryTree {
  void* val;
  struct BinaryTree* left;
  struct BinaryTree* right;
} BinaryTree;

typedef void(*BT_VAL_FREE)(void*);
typedef int(*BT_VAL_CMP)(void*, void*);
typedef sds(*BT_VAL_SHOW)(void*);

BinaryTree* new_BinaryTree(void* val);
void free_BinaryTree(BinaryTree* root, BT_VAL_FREE free_val);
BinaryTree* insert(BinaryTree* root, void* val, BT_VAL_CMP cmp);
BinaryTree* find(BinaryTree* root, void* val, BT_VAL_CMP cmp);
bool exists(BinaryTree* root, void* val, BT_VAL_CMP cmp);

sds stringify(BinaryTree* root, BT_VAL_SHOW show);
#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "sds/sds.h"
#include "cplayground.h"

#define ARRAY_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
#define INT_TO_VoPTR(i) ((void*)(intptr_t)i)

int int_cmp(void* lhs, void* rhs) {
  int vl = (intptr_t)lhs;
  int vr = (intptr_t)rhs;

  if (vl < vr) {
    return -1;
  }

  if (vl == vr) {
    return 0;
  }

  return 1;
}

sds int_show(void* val) {
  return sdscatprintf(sdsempty(), "%ld", (intptr_t)val);
}

void int_free(void* _) {}

int main(int argc, char const* argv[]) {
  BinaryTree* root = new_BinaryTree(INT_TO_VoPTR(1));
  int data[] = {
    2,3,4,1,1,4,2,1,5,6,3,2,3,4,2,3,7,5,6,7,5,6,2,3,5,4,2,3
  };
  size_t data_len = ARRAY_LEN(data);

  for (size_t i = 0; i < data_len; i++) {
    insert(root, INT_TO_VoPTR(data[i]), int_cmp);
  }

  printf("%s", stringify(root, int_show));

  free_BinaryTree(root, int_free);

  return 0;
}

Makefile

.PHONY: all test clean

CC := cc
CFLAGS := -Wextra -Wall -g 

TARGET = cplayground
SRCS = \
	$(shell find ./ -maxdepth 1 -name "*.c") \
	$(shell find ./sds -name "*.c")
OBJS = $(shell find ./ -name "*.o")

GENERATED = generated

TEST_TARGET = cplayground_test
TEST_SRCS = \
	$(shell find ./ ! -name "main.c" -name "*.c") \
	$(shell find ./sds -name "*.c") \
	$(shell find ./tests -name "*.c")

all: $(TARGET)

test: build_test run_test

build_test: $(TEST_TARGET)

run_test:
	$(GENERATED)/$(TEST_TARGET)

$(TARGET): $(SRCS) | $(GENERATED)
	$(CC) -o $(addprefix $(GENERATED)/, $@) $^ $(CFLAGS)

$(TEST_TARGET): $(TEST_SRCS) | $(GENERATED)
	$(CC) -o $(addprefix $(GENERATED)/, $@) $^ $(CFLAGS)  -I ./

$(GENERATED):
	@mkdir -p $(GENERATED)

clean:
	$(RM) $(OBJS) $(addprefix $(GENERATED)/, $(TARGET) $(TEST_TARGET))

tester.c

#include <stdio.h>

int main(int argc, char const* argv[]) {
  printf("Test main\n");
  return 0;
}

util.c

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

void* xmalloc(size_t size) {
  void* ptr = malloc(size);
  if (ptr == NULL) {
    fprintf(stderr, "Failed to allocate memory\n");
    exit(EXIT_FAILURE);
  }
  return ptr;
}

void xfree(void** p_ptr) {
  if (p_ptr == NULL || *p_ptr == NULL) {
    fprintf(stderr, "Given pointer is NULL");
    exit(EXIT_FAILURE);
  }

  free(*p_ptr);
  *p_ptr = NULL;
}