AssocArray Refactor

assoc_array.c

#include <stdbool.h>
#include <stdlib.h>

#include "assoc_array.h"

typedef struct AssocArrayItem {
  char key;
  unsigned int value;
} AssocArrayItem;

typedef struct AssocArrayBucket {
  unsigned int n_items;
  AssocArrayItem *items;
} AssocArrayBucket;

typedef struct AssocArray {
  unsigned int n_buckets;
  AssocArrayBucket *buckets;
} AssocArray;

AssocArray *aaAlloc(unsigned int n_buckets) {
  AssocArray *aa = malloc(sizeof(AssocArray));

  if (aa == NULL) {
    return NULL;
  }

  aa->n_buckets = n_buckets;
  aa->buckets = calloc(aa->n_buckets, sizeof(AssocArrayBucket));

  if (aa->buckets == NULL) {
    return NULL;
  }

  return aa;
}

void aaFree(AssocArray *assoc_array) {
  if (assoc_array == NULL) {
    return;
  }

  if (assoc_array->buckets != NULL) {
    for (int bucket_idx = 0; bucket_idx < assoc_array->n_buckets;
         bucket_idx++) {
      AssocArrayBucket *current_bucket = &assoc_array->buckets[bucket_idx];

      if (current_bucket != NULL && current_bucket->items != NULL) {
        free(current_bucket->items);
      }
    }
    free(assoc_array->buckets);
  }

  free(assoc_array);
}

static int initializeBucket(AssocArrayBucket *bucket, char key) {
  unsigned int initial_size = 1;
  unsigned int initial_value = 1;

  bucket->n_items = initial_size;
  bucket->items = calloc(initial_size, sizeof(AssocArrayItem));

  if (bucket->items == NULL) {
    return -1;
  }

  bucket->items[0].key = key;
  bucket->items[0].value = initial_value;

  return initial_value;
}

static int resizeBucket(AssocArrayBucket *bucket, char key) {
  bucket->n_items++;
  bucket->items =
      realloc(bucket->items, bucket->n_items * sizeof(AssocArrayItem));

  if (bucket->items == NULL) {
    return -1;
  }

  unsigned int new_item_idx = bucket->n_items - 1;

  bucket->items[new_item_idx].key = key;
  bucket->items[new_item_idx].value = 1;

  return bucket->items[new_item_idx].value;
}

static unsigned int bucketKey(unsigned int n_buckets, char key) {
  return key % n_buckets;
}

int aaIncrement(AssocArray *assoc_array, char key) {
  if (assoc_array == NULL) {
    return -1;
  }

  unsigned int idx = bucketKey(assoc_array->n_buckets, key);
  AssocArrayBucket *bucket = &assoc_array->buckets[idx];

  if (bucket == NULL) {
    return initializeBucket(bucket, key);
  }

  for (int item_idx = 0; item_idx < bucket->n_items; item_idx++) {
    AssocArrayItem *item = &bucket->items[item_idx];

    if (item->key == key) {
      item->value++;

      return item->value;
    }
  }

  return resizeBucket(bucket, key);
}

unsigned int aaValue(AssocArray *assoc_array, char key) {
  if (assoc_array != NULL) {
    unsigned int idx = bucketKey(assoc_array->n_buckets, key);
    AssocArrayBucket *bucket = &assoc_array->buckets[idx];

    if (bucket != NULL && bucket->items != NULL) {
      for (int item_idx = 0; item_idx < bucket->n_items; item_idx++) {
        if (bucket->items[item_idx].key == key) {
          return bucket->items[item_idx].value;
        }
      }
    }
  }

  return 0;
}

assoc_array.h

#ifndef __ASSOC_ARRAY_H__
#define __ASSOC_ARRAY_H__

/*
 * A data structure to map characters to positive integer values.
 *
 * A value always starts at 0, and can be incremented from there.
 *
 * There's a space/speed trade-off based on the `size` provided.
 * A character, `c`, will be inserted according to `c % size`.
 *
 * When more than one character maps to the same bucket, a linear
 * search is used to differentiate between those characters.
 *
 * More buckets results in less collisions and faster access, but
 * at the cost of more memory. A small number of buckets tends to
 * result in slower access, but less memory.
 */
typedef struct AssocArray AssocArray;

/*
 * Create an array of N buckets. Every bucket holds a dynamic array
 * of items, which grows when there are collisions between keys.
 */
AssocArray *aaAlloc(unsigned int n_buckets);

/*
 * Free all heap-allocated memory for the given `assoc_array`.
 */
void aaFree(AssocArray *assoc_array);

/*
 * Increment the value associated with `key`.
 *
 * Since the value of missing `key`s are considered to be 0, this
 * function will return 1 upon the first successful call, and then
 * continue to increment the number for subsequent calls.
 *
 * Returns -1 if the operation fails for some reason.
 */
int aaIncrement(AssocArray *assoc_array, char key);

/*
 * Return the value associated with the given `key`.
 */
unsigned int aaValue(AssocArray *assoc_array, char key);

#endif

assoc_array_test.c

#include <assert.h>
#include <stdio.h>
#include <unistd.h>

#include "assoc_array.h"

void printPass() {
  if (isatty(STDOUT_FILENO)) {
    printf("\e[32mPASS\e[0m\n");
  } else {
    printf("PASS\n");
  }
}

void test1() {
  printf("[TEST] Characters that end up in the same bucket inc'd correctly\t");

  AssocArray *aa = aaAlloc(26);

  // 'm' % 26 == 5
  // 'S' % 26 == 5
  assert(aaIncrement(aa, 'm') == 1);
  assert(aaIncrement(aa, 'm') == 2);
  assert(aaIncrement(aa, 'S') == 1);
  assert(aaIncrement(aa, 'm') == 3);
  assert(aaIncrement(aa, 'S') == 2);

  aaFree(aa);

  printPass();
}

void test2() {
  printf("[TEST] Able to increment and get values\t\t\t\t\t");

  AssocArray *aa = aaAlloc(26);

  assert(aaValue(aa, 'a') == 0);
  assert(aaIncrement(aa, 'a') == 1);
  assert(aaValue(aa, 'a') == 1);

  assert(aaIncrement(aa, 'a') == 2);
  assert(aaValue(aa, 'a') == 2);

  assert(aaValue(aa, 'G') == 0);
  assert(aaIncrement(aa, 'G') == 1);
  assert(aaValue(aa, 'G') == 1);

  assert(aaIncrement(aa, 'G') == 2);
  assert(aaIncrement(aa, 'G') == 3);
  assert(aaValue(aa, 'G') == 3);

  assert(aaValue(aa, 'a') == 2);

  assert(aaValue(aa, 'p') == 0);
  assert(aaIncrement(aa, 'p') == 1);
  assert(aaIncrement(aa, 'p') == 2);

  aaFree(aa);

  printPass();
}

int main() {
  printf("\n");

  test1();
  test2();

  return 0;
}

gistfile1.txt

clang -g -Wall assoc_array.c assoc_array_test.c -o assoc_array_test