Removing Duplicates from a Simple Dynamic Array for C

Introduction

Previously, I described a full implementation for a simple dynamic array in C that I’ve been using in my include-tidy (Tidy) project.

When Tidy prints an #include directive that the file being tidied is missing, it, by default, includes a comment containing the symbol(s) referenced, e.g.:

#include <stdio.h>       // printf, puts

When tidying a C++ source file, there can be duplicate names since C++ allows overloading, e.g.:

// foo.h
void foo( int );
void foo( char const* );

// foo.cpp
void bar() {
  foo( 42 );
  foo( "hello, world" );
}

Even though the functions are distinct, we don’t want the same name repeated in the comment:

#include "foo.h"         // foo, foo

and it would be too verbose to print function signatures. So, given an array of symbols sorted by name, we want to remove duplicates. Let’s add an array_unique function. (The name is borrowed from std::unique in C++’s standard library.)

Initial Version

Here’s an initial version:

void array_unique( array_t *restrict array, array_cmp_fn_t cmp_fn,
                   array_free_fn_t free_fn ) {
  if ( array->len < 2 )
    return;

  char             *dst = array_at_nc( array, 1 );
  char const *const end = array_at_nc( array, array->len );
  size_t const      esize = array->esize;
  void const       *last_unique = array_front_nc( array );

  for ( char *src = dst; src < end; src += esize ) {
    if ( (*cmp_fn)( last_unique, src ) != 0 ) {
      last_unique = src;          // keep current element
      if ( dst != src )
        memcpy( dst, src, esize );
      dst += esize;
    }
    else if ( free_fn != NULL ) {
      (*free_fn)( src );
    }
  } // for

  array->len = (size_t)(dst - (char*)array->elements) / esize;
}

In addition to the array, it takes two pointers to function: the first to check for equality and the second, optionally, to clean-up duplicate elements.

The code uses four pointers:

• last_unique: starts at array[0] and always points to the last unique element.
• end: points at array[len], one past the last element.
• src: starts at array[1] and goes to array[len-1].
• dst: possibly points at a duplicate element to be overwritten.

The code compares last_unique (element i+1) to src (element i):

• If they’re not equal:
  • Updates last_unique.
  • If dst != src, it means the previous element (dst) is a duplicate, so overwrite it.
• If they’re equal:
  • src (the current element) is a duplicate, so clean it up.

Why does the code use pointer arithmetic rather than using an index variable like i? Because you’d have to calculate element addresses anyway by multiplying by i. It’s better just to increment by esize directly and eliminate the ++i and multiplication.

Optimization

Consider an array containing the integers 1, 2, 2, 3, 4, 5. The current code would end up calling memcpy three times, once each for 3, 4, and 5. However, just looking at it, you can intuit that you could instead copy 3, 4, and 5 together as a single batch. For arrays likely having only a few duplicates, this would dramatically reduce the number of calls to memcpy.

To implement this, we add batch_src to point to the start of the current batch of unique elements and batch_len for the length of the batch.

void array_unique( array_t *restrict array, array_cmp_fn_t merge_fn,
                  array_free_fn_t free_fn ) {
  if ( array->len < 2 )
    return;

  void const       *batch_src = NULL;
  size_t            batch_len = 0;
  char             *dst = array_at_nc( array, 1 );
  char const *const end = array_at_nc( array, array->len );
  size_t const      esize = array->esize;
  void const       *last_unique = array_front_nc( array );

  for ( char *src = dst; src < end; src += esize ) {
    if ( (*cmp_fn)( last_unique, src ) != 0 ) {
      last_unique = src;           // keep current element

      if ( batch_src != NULL ) {   // expand current batch
        ++batch_len;
      }
      else if ( dst != src ) {     // start a new batch
        batch_src = src;
        batch_len = 1;
      }
      else {                       // no duplicates found yet
        dst += esize;
      }
    }
    else {                         // found a duplicate
      if ( free_fn != NULL )
        (*free_fn)( src );

      if ( batch_src != NULL ) {   // move unique(s) over dup(s)
        size_t const batch_size = batch_len * esize;
        memmove( dst, batch_src, batch_size );
        batch_src = NULL;
        batch_len = 0;
        dst += batch_size;
      }
    }
  } // for

  if ( batch_src != NULL ) {       // move last batch
    size_t const batch_size = batch_len * esize;
    memmove( dst, batch_src, batch_size );
    dst += batch_size;
  }

  array->len = (size_t)(dst - (char*)array->elements) / esize;
}

Now, when last_unique is compared to src:

• If they’re not equal, there are three cases:
  1. If there’s a current batch, just increment batch_len;
  2. Else if there’s no current batch, start one;
  3. Else just increment dst because no duplicate has been found yet.
• If they’re equal:
  • Clean-up src as before; and:
  • If there’s a current batch, move the whole batch and update dst.

After the loop terminates, if there was a batch in progress, move the last batch.

Unlike the original code, the source and destination memory regions being copied may now overlap which means we have to use memmove rather than memcpy.

Merging

For array elements that are 100% duplicates, array_unique is fine; however, in Tidy’s case, the elements are symbols:

struct tidy_symbol {
  char const *key;        // Unique key.
  char const *name;       // Symbol name without signature.
  unsigned    ref_count;  // Number of times referenced.
};

Symbols in the array can have duplicate names, but their ref_counts are different. You can tell Tidy to make the #include comment contain either symbols sorted descendingly by ref_count or only the most-used symbol.

However, if we naively just eliminate duplicates (by name), we lose the duplicates’ ref_counts. For example, if foo(int) is used twice and foo(char const*) is used once, we want to end up with foo (collectively) being used three times.

Hence, instead of simply overwriting a duplicate, we want to merge it by extracting information from it before overwriting it (in Tidy’s case, it’s ref_count) and adding it in.

It turns out the existing code for array_unique is almost exactly right for doing merging instead. It just needs a few tweaks.

The first is that we need a new function type:

typedef int (*array_merge_fn_t)( void *unique, void const *maybe_dup );

The only difference is that its first argument is now a pointer to non-const because it’s the element to merge into. Given that, an implementation for comparing and possibly merging tidy_symbol objects is:

static int symbol_merge_by_name( tidy_symbol *unique_sym,
                                 tidy_symbol const *maybe_dup_sym ) {
  int const cmp = strcmp( unique_sym->name, maybe_dup_sym->name );
  if ( cmp == 0 )
    unique_sym->ref_count += maybe_dup_sym->ref_count;
  return cmp;
}

The new array_merge function is almost identical to array_unique:

void array_merge( array_t *restrict array, array_merge_fn_t merge_fn,
                  array_free_fn_t free_fn ) {
 if ( array->len < 2 )
    return;

  void const       *batch_src = NULL;
  size_t            batch_len = 0;
  char             *dst = array_at_nc( array, 1 );
  char const *const end = array_at_nc( array, array->len );
  size_t const      esize = array->esize;
  void             *last_unique = array_front_nc( array );

  for ( char *src = dst; src < end; src += esize ) {
    if ( (*merge_fn)( last_unique, src ) != 0 ) {
      last_unique = src;           // keep current element

      if ( batch_src != NULL ) {   // expand current batch
        ++batch_len;
      }
      else if ( dst != src ) {     // start a new batch
        batch_src = src;
        batch_len = 1;
      }
      else {                       // no duplicate found yet
        dst += esize;
      }
    }
    else {                         // found a duplicate
      if ( free_fn != NULL )
        (*free_fn)( src );

      if ( batch_src != NULL ) {   // move unique(s) over dup(s)
        size_t const batch_size = batch_len * esize;
        memmove( dst, batch_src, batch_size );
        batch_src = NULL;
        batch_len = 0;
        dst += batch_size;
        last_unique = dst - esize; // <-- KEY DIFFERENCE!
      }
    }
  } // for

  if ( batch_src != NULL ) {       // move last batch
    size_t const batch_size = batch_len * esize;
    memmove( dst, batch_src, batch_size );
    dst += batch_size;
  }

  array->len = (size_t)(dst - (char*)array->elements) / esize;
}

The differences are:

• It uses merge_fn instead of cmp_fn.
• Most importantly, last_unique is updated after a memmove.

The reason last_unique needs to be updated is because the element to which it points is possibly updated — in Tidy’s case, the symbol’s ref_count.

Consider the array {“A”,1}, {“A”,1}, {“B”,1}, {“C”,1}, {“C”,1}, {“C”,1}. At some point during the merge, the array will look like:

In the original code, last_unique is left pointing at the wrong element. It didn’t matter for array_unique because the names at a[2] and a[3] are the same; but for merging, the wrong ref_count will be subsequently updated. By repositioning last_unique, things will instead look like:

which is correct.

Code Reuse

It turns out that updating last_unique is harmless if it were also done in the original array_unique code. Given that, we can make array_unique simply call array_merge that just casts the function pointer:

inline void array_unique( array_t *restrict array, array_cmp_fn_t cmp_fn,
                          array_free_fn_t free_fn ) {
  array_merge( array, (array_merge_fn_t)cmp_fn, free_fn );
}

Conclusion

Implementing array_unique is a nice example of pointer arithmetic and memory-copying optimization. Extending it to array_merge is a nice example of making code more generically useful and of code reuse.