#include <limits.h>

 #include <string.h>

 #include <sys/stat.h>

 #include <stdlib.h>

 #include <stdio.h>

 #include <stdint.h>

 #include <unistd.h>

 #include "razor-internal.h"

 int

 razor_create_dir(const char *root, const char *path)

 {

 	char buffer[PATH_MAX], *p;

 	const char *slash, *next;

 	struct stat buf;

 	/* Create all sub-directories in dir. We know root exists and

 	 * is a dir, root does not end in a '/', and path has a

 	 * leading '/'. */

 	strcpy(buffer, root);

 	p = buffer + strlen(buffer);

 	slash = path;

 	for (slash = path; *slash != '\0'; slash = next) {

 		next = strchr(slash + 1, '/');

 		if (next == NULL)

 			break;

 		memcpy(p, slash, next - slash);

 		p += next - slash;

 		*p = '\0';

 		if (stat(buffer, &buf) == 0) {

 			if (!S_ISDIR(buf.st_mode)) {

 				fprintf(stderr,

 					"%s exists but is not a directory\n",

 					buffer);

 				return -1;

 			}

 		} else if (mkdir(buffer, 0777) < 0) {

 			fprintf(stderr, "failed to make directory %s: %m\n",

 				buffer);

 			return -1;

 		}

 		/* FIXME: What to do about permissions for dirs we

 		 * have to create but are not in the cpio archive? */

 	}

 	return 0;

 }

 int

 razor_write(int fd, const void *data, size_t size)

 {

 	size_t rest;

 	ssize_t written;

 	const unsigned char *p;

 	rest = size;

 	p = data;

 	while (rest > 0) {

 		written = write(fd, p, rest);

 		if (written < 0) {

 			fprintf(stderr, "write error: %m\n");

 			return -1;

 		}

 		rest -= written;

 		p += written;

 	}

 	return 0;

 }

 struct qsort_context {

 	size_t size;

 	razor_compare_with_data_func_t compare;

 	void *data;

 };

 static void

 qsort_swap(void *p1, void *p2, size_t size)

 {

 	char buffer[size];

 	memcpy(buffer, p1, size);

 	memcpy(p1, p2, size);

 	memcpy(p2, buffer, size);

 }

 static void

 __qsort_with_data(void *base, size_t nelem, uint32_t *map,

 		  struct qsort_context *ctx)

 {

 	void *p, *start, *end, *pivot;

 	uint32_t *mp, *mstart, *mend, tmp;

 	int left, right, result;

 	size_t size = ctx->size;

 	p = base;

 	start = base;

 	end = base + nelem * size;

 	mp = map;

 	mstart = map;

 	mend = map + nelem;

 	pivot = base + (random() % nelem) * size;

 	while (p < end) {

 		result = ctx->compare(p, pivot, ctx->data);

 		if (result < 0) {

 			qsort_swap(p, start, size);

 			tmp = *mp;

 			*mp = *mstart;

 			*mstart = tmp;

 			if (start == pivot)

 				pivot = p;

 			start += size;

 			mstart++;

 			p += size;

 			mp++;

 		} else if (result == 0) {

 			p += size;

 			mp++;

 		} else {

  			end -= size;

 			mend--;

 			qsort_swap(p, end, size);

 			tmp = *mp;

 			*mp = *mend;

 			*mend = tmp;

 			if (end == pivot)

 				pivot = p;

 		}

 	}

 	left = (start - base) / size;

 	right = (base + nelem * size - end) / size;

 	if (left > 1)

 		__qsort_with_data(base, left, map, ctx);

 	if (right > 1)

 		__qsort_with_data(end, right, mend, ctx);

 }

 uint32_t *

 razor_qsort_with_data(void *base, size_t nelem, size_t size,

 		      razor_compare_with_data_func_t compare, void *data)

 {

 	struct qsort_context ctx;

 	uint32_t *map;

 	int i;

 	if (nelem == 0)

 		return NULL;

 	ctx.size = size;

 	ctx.compare = compare;

 	ctx.data = data;

 	map = malloc(nelem * sizeof (uint32_t));

 	for (i = 0; i < nelem; i++)

 		map[i] = i;

 	__qsort_with_data(base, nelem, map, &ctx);

 	return map;

 }