remove duplicates from an array without preserving the order of elements in C

amit.c

/**
   gcc -std=c99 -Wall -g *.c && ./a.out
*/
#include <assert.h>
#include <iso646.h> // and, or
#include <stdio.h>  // putchar
#include <stdlib.h> // size_t
#include <string.h> // strcspn
#include <stddef.h> // ptrdiff_t

typedef struct {
  size_t size; // number of character in a string (no ending '\0')
  const char *chars;
} *String;

/** Create a new String.

    It doesn't copy `chars`.
   `chars` must point to a valid memory until String_destroy() is called
*/
String String_create(const char* chars, size_t size) {
  if (not chars) return NULL;
  String string = malloc(sizeof(*string));
  if (not string) return NULL;
  string->size = size;
  string->chars = chars;
  return string;
}

void String_destroy(String self) {
  if (not self) return;
  self->size = 0;
  self->chars = NULL;
  free(self);
}

/** Print string to stdout appending `end` at the end. */
void String_dump(const String self, const char *end) {
  if (not (self and end and self->chars)) return;
  printf("%.*s%s", (int)self->size, self->chars, end);
}

/** Compare strings.

    The strings are equal if they have the same characters.
    Return values are the same as for qsort's cmp
*/
int String_cmp(const String a, const String b) {
  assert(a and b);
  size_t i = 0;
  for ( ; i < a->size and i < b->size; ++i) {
    if (a->chars[i] < b->chars[i]) return -1;
    if (a->chars[i] > b->chars[i]) return 1;
  }
  if (i == a->size and i == b->size) return 0;
  return a->size - b->size;
}

/** Copy from `from` string to `to` string. */
void String_copy(String to, const String from) {
  if (not (to and from)) return;
  *to = *from;
}

typedef struct {
  size_t size;
  size_t capacity;
  String items; // used as an array of *String type
} *StringArray;

/** Create a new empty array */
StringArray StringArray_create() {
  StringArray self = malloc(sizeof(*self));
  if (not self) return NULL;
  self->size = 0;
  self->capacity = 0;
  self->items = NULL;
  return self;
}

void StringArray_destroy(StringArray self) {
  if (not self) return;
  self->size = 0;
  self->capacity = 0;
  if (self->items != NULL) {
    free(self->items);
    self->items = NULL;
  }
  free(self);
}

/** Print items from the array separated by `sep`. */
void StringArray_dump(const StringArray self, const char* sep) {
  if (not self) return;
  String last = self->items + self->size;
  for (String first = self->items; first != last; ++first)
    String_dump(first, sep);
  putchar('\n');
}

static int ensure_capacity(StringArray self) {
  assert(self and self->size <= self->capacity);
  if (self->size == self->capacity) { // increase capacity
    const size_t capacity = self->capacity + (self->capacity >> 3) + 6;
    String p = realloc(self->items, sizeof(*p)*capacity);
    if (not p) return -2;
    self->capacity = capacity;
    self->items = p;
  }
  return 0;
}

/** Append the string to the array.

    On error leave the array unchanged and return < 0
*/
int StringArray_append(StringArray self, const String string) {
  if (not (self and string)) return -1;
  if (ensure_capacity(self) < 0) return -2;
  assert(self->size < self->capacity);

  String_copy(self->items + self->size, string);
  ++self->size;
  return 0; // ok
}

/** Adapt String_cmp() for qsort() */
static int compare_strings(const void *pa, const void *pb) {
  return String_cmp((String)pa, (String)pb);
}

/** Sort strings using String_cmp() as a comparison function */
void StringArray_sort(StringArray self) {
  if (not (self and self->items)) return;
  qsort((void*)self->items, self->size, sizeof(*self->items), compare_strings);
}

/** Remove range [first, last) from the array.

    Deallocate unused items i.e., newcapacity == newsize
 */
int StringArray_remove(StringArray self, String first, String last) {
  const ptrdiff_t remove_count = last - first; // may overflow
  if (first > last) return -1; // invalid args
  if (not (self and self->items and self->size and remove_count > 0))
    return 0; // nothing todo

  if (first < self->items or last > (self->items + self->size) or
      (ptrdiff_t)self->size < remove_count)
    return -1; // invalid args

  if (last != (self->items + self->size) or first == self->items or
      (ptrdiff_t)self->size == remove_count)
      return -1; //XXX removing in the middle or whole array is not supported,
               // if first==self.items use StringArray_destroy() instead of

  const size_t newsize = self->size - remove_count;
  assert(newsize < self->size);
  String p = realloc(self->items, sizeof(*p)*newsize);
  if (not p) return -2;
  self->size = newsize;
  self->capacity = newsize;
  self->items = p;
  return 0;
}

/** Split input text into words with whitespace as a delimiter.

    Return a new StringArray
    A caller must destroy it with StringArray_destroy()
*/
static StringArray split(const char* text, size_t size) {
  if (not (text and text[size-1] == '\0')) return NULL;

  StringArray array = StringArray_create();
  if (not array) return NULL;

  size_t n = -1;
  for (const char* p = text; p != text+size; p += n+1) {
    n = strcspn(p, " \t\n"); // find index of the next whitespace
    if (n == 0) continue; // skip consecutive whitespace

    // append characters in range [p, p+n)
    // as a string to the array
    const String string = String_create(p, n);
    if (StringArray_append(array, string) < 0) {
      String_destroy(string);
      StringArray_destroy(array);
      return NULL;
    }
    String_destroy(string);
   }
  return array;
}

/** Remove duplicate items from the array without preserving order.

    Return <0 in case of an error
*/
static int remove_duplicates(StringArray array) {
  if (not (array and array->items)) return 0; // empty array or NULL

  StringArray_sort(array); // sort

  // unique_copy()
  String result = array->items, last = array->items + array->size;
  for (String first = array->items; first != last; ++result) {
    String_copy(result, first); // copy first to result
    for (String prev = first; ++first != last and String_cmp(prev, first) == 0;)
      { /* skip adjacent equal items */ }
  }
  // shrink
  return StringArray_remove(array, result, last);
}

int main() {
  char text[] = "Mahesh Amit  Hanish Amit";
  StringArray array = split(text, sizeof(text));
  StringArray_dump(array, "<"); // print array before removing duplicates
  if (remove_duplicates(array) < 0)
    perror("error remove_duplicates(), OS error if any");
  StringArray_dump(array, ">"); // print it after
  StringArray_destroy(array);
  return 0;
}