Skip to content

Apple's qsort implementation with support for inlined comparison (by macros)

Notifications You must be signed in to change notification settings

ahmadsalim/qsort-inline

Repository files navigation

Quick Sort with inlined type-safe comparison

This Quick Sort is an extension/reimplementation of C qsort function (based on Apple's code, which is APSL licensed). It allows specialisation of the quicksort function with different types and comparison, such that the comprison function is inlined. This allows greater performance and type safety for qsort in C, though makes a comprimise regarding syntactic safety by using macros and requires an extra definition step.

Example

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "qsort-inline.h"

struct tagPerson {
  int age;
  char* name;
};

//Needs typedef's for complex types as type is a part of generated function name
typedef struct tagPerson* Person;

//Construct a person
Person make_person(int age, const char *name) {
  Person p = malloc(sizeof(struct tagPerson));
  if (!p) goto ret;
  size_t n = strlen(name);
  p->age = age;
  p->name = malloc(sizeof(char)*n);
  if (!(p->name))
    goto cleanup;
  strcpy(p->name, name);
  goto ret;
cleanup:
  free(p);
  p = NULL;
ret:
  return p;
}

//Delete a person
void delete_person(Person p) {
  if (!p) return;
  if (p->name) free(p->name);
  free(p);
}

//Define comparator as usual (Though notice that it is typesafe. This will sort by age, then by name.)
inline int Personcmp(Person * pa, Person * pb) {
  int agecmp = (*pa)->age - (*pb)->age;
  if (!agecmp) {
    return strcmp((*pa)->name, (*pb)->name);
  }
  return agecmp;
}

//Define quicksort overload for Person
DEF_QSORT(Person, Personcmp)

int main()
{
#define N 5
  Person arr[N];
  //Construct persons with random names and ages
  arr[0] = make_person(18, "Peter Peterson");
  arr[1] = make_person(20, "Jack Peterson");
  arr[2] = make_person(53, "Hansel Georgeson");
  arr[3] = make_person(18, "Alexander McWright");
  arr[4] = make_person(64, "Elizabeth Reader");

  QSORT(Person, Personcmp) (arr, N);
  int i = 0;

  //Print persons
  for (i = 0; i < N; i++) {
    if (arr[i])
      printf("Person { age: %d, name: %s }\n", arr[i]->age, arr[i]->name);
  }

  //Delete persons
  for (i = 0; i < N; i++) {
    delete_person(arr[i]);
    arr[i] = NULL;
  }
  return 0;
}

About

Apple's qsort implementation with support for inlined comparison (by macros)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published