node blocks realloc test

node_realloc_test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int prints;

#define NODEBLOCK_CAP 256

#define MAX(a, b) \
    ((a > b) ? a : b)

#define GRAPH_NODE_COUNT_TO_BLOCK_COUNT(n) \
    MAX(1, n / NODEBLOCK_CAP)

typedef struct {
    size_t block_count;             // Number of node blocks.
    size_t node_cap;                // Number of nodes graph can hold.
    size_t node_count;              // Number of nodes stored.
} Graph;

void Original_Graph_ResizeNodes(Graph *g, size_t n) {
    // Make sure we have room to store nodes.
    if (g->node_count + n < g->node_cap)
      return;

    int delta = (g->node_count + n) - g->node_cap;
    // Add some additional extra space for future inserts.
    delta += g->node_cap*2;

    // Determine number of required NodeBlocks.
    int new_blocks = GRAPH_NODE_COUNT_TO_BLOCK_COUNT(delta);
    g->block_count += new_blocks;

    g->node_cap = g->block_count * NODEBLOCK_CAP;
    printf("Realloc %d - %lu blocks\t\t: %lu node_cap\n", ++prints, g->block_count, g->node_cap);
}

void New_Graph_ResizeNodes(Graph *g, size_t n) {
    int total_nodes = g->node_count + n;

    // Make sure we have room to store nodes.
    if (total_nodes < g->node_cap)
      return;

    int last_block = g->block_count - 1;

    int increase_factor = (total_nodes / g->node_cap) + 2;

    g->block_count *= increase_factor;

    g->node_cap = g->block_count * NODEBLOCK_CAP;
    printf("Realloc %d - %lu blocks\t\t: %lu node_cap\n", ++prints, g->block_count, g->node_cap);
}

void graph_init(Graph *g) {
  g->node_cap = 2 * NODEBLOCK_CAP;
  g->block_count = 2;
  g->node_count = 0;
}

int main(int argc, char **argv) {
  Graph g;
  int new_nodes;
  int seed;
  if (argc > 1) {
    seed = atoi(argv[1]);
  } else {
    seed = time(NULL);
  }

  graph_init(&g);
  int denom = RAND_MAX / 10000 + 1;
  srand(seed);
  prints = 0;

  printf("Default method:\n");
  for (int i = 0; i < 10000; i ++) {
    // (Fairly) random value 
    new_nodes = rand() / denom + 1;
    Original_Graph_ResizeNodes(&g, new_nodes);
    g.node_count += new_nodes;
  }

  graph_init(&g);
  srand(seed);
  prints = 0;

  printf("\nNew method:\n");
  for (int i = 0; i < 10000; i ++) {
    new_nodes = rand() / denom + 1;
    New_Graph_ResizeNodes(&g, new_nodes);
    g.node_count += new_nodes;
  }
  printf("\n%lu total nodes.\n", g.node_count);
}