#include <stdlib.h>
#include <stddef.h>
#include <unistd.h>
#include <string.h>

#include <stdio.h>

#define PART_SIZE 512

//#define DEBUG_STRING

#ifdef DEBUG_STRING
#define debugString(fmt, args...) dprintf(fmt, ##args)
#else
#define debugString noprint
#endif

/*
	X_init(T *t)   - inits structure
	X_clear(T *t)  - release contents
	T* X_new()     - allocs + inits
	X_delete(T *t) - clears + free
*/

struct buf_refcounted {
	size_t size, refcount;
	char data[];
};
typedef struct buf_refcounted buf_t;

struct simple_string {
	buf_t *buf;
	char *data;
	size_t len;
};
typedef struct simple_string sstring_t;

struct string {
	size_t len, part_count;
	sstring_t parts[PART_SIZE];
};
typedef struct string string_t;

/* DO NOT USE THEM ON CHANGING STRINGS */
struct string_pos {
	string_t *str;
	size_t abspos, part, pos;
// current part data
	size_t curlen;
	char *data;
};
typedef struct string_pos string_pos_t;

#define SSTRING_PAGE ((size_t)(1 << 10))
static inline size_t SSTRING_ROUND_UP(size_t size) { return (size + SSTRING_PAGE - 1) & ~(SSTRING_PAGE-1); }

/***************************************
        Buffer implementation
 ***************************************/

// Alloc new buf for given data size
static inline buf_t *buf_new(size_t size) {
	buf_t *buf = (buf_t*) malloc(sizeof(buf_t)+size);
//	debugString("buf new: 0x%08x\n", (unsigned int) buf);
	buf->size = size;
	buf->refcount = 1;
	return buf;
}

// Just free it
static inline void buf_free(buf_t* buf) {
	free(buf);
}

// Release reference
static inline void buf_put(buf_t* buf) {
//	debugString("buf put: 0x%08x\n", (unsigned int) buf);
	if (!--(buf->refcount))
		buf_free(buf);
}

// Get reference
static inline void buf_get(buf_t *buf) {
//	debugString("buf get: 0x%08x\n", (unsigned int) buf);
	if (buf->refcount++ == (size_t)-1) {
		write(2, "Refcount overflow\n", 18);
		exit(-1);
	}
}

// Resizes a copy of buf to size
static inline buf_t *buf_resize(buf_t *buf, size_t size) {
//	debugString("%s\n", __FUNCTION__);
	buf_t *res;
	if (buf->refcount == 1) {
		res = (buf_t*) realloc(buf, sizeof(buf_t)+size);
		res->size = size;
	} else {
		res = buf_new(size);
		memcpy(res->data, buf->data, (size < res->size) ? size : res->size);
		buf_put(buf);
	}
	return res;
}

static inline char* buf_data(buf_t *buf) {
	return buf->data;
}

static inline size_t buf_size(buf_t *buf) {
	return buf->size;
}

/***************************************
        Simple string implementation
 ***************************************/

static inline void sstring_init(sstring_t *str) {
//	debugString("%s\n", __FUNCTION__);
	str->buf = 0; str->data = 0; str->len = 0;
}

static inline void sstring_init_withbuf(sstring_t *str, buf_t *buf) {
//	debugString("%s\n", __FUNCTION__);
	str->buf = buf; str->data = buf_data(buf); str->len = buf->size;
}

static inline void sstring_init_sized(sstring_t *str, size_t size) {
//	debugString("%s\n", __FUNCTION__);
	str->buf = buf_new(size); str->data = buf_data(str->buf); str->len = 0;
}

static inline void sstring_init_with_len(sstring_t *str, const char *data, size_t len) {
//	debugString("%s\n", __FUNCTION__);
	str->buf = buf_new(len); str->len = 0;
	str->data = buf_data(str->buf);
	memcpy(str->data, data, len);
}

static inline void sstring_init_with(sstring_t *str, const char *data) {
//	debugString("%s\n", __FUNCTION__);
	sstring_init_with_len(str, data, strlen(data));
}

// Clear for later reuse
static inline void sstring_zero(sstring_t *str) {
//	debugString("%s\n", __FUNCTION__);
	buf_t *buf = str->buf;
	str->len = 0;
	if (buf->refcount == 1) {
		str->data = buf_data(buf);
	} else {
		buf_put(buf);
		str->buf = 0; str->data = 0;
	}
}

static inline void sstring_clear(sstring_t *str) {
//	debugString("%s\n", __FUNCTION__);
	if (str->buf) buf_put(str->buf);
	str->buf = 0; str->data = 0; str->len = 0;
}

static inline sstring_t *sstring_new() {
//	debugString("%s\n", __FUNCTION__);
	sstring_t *res = (sstring_t*) malloc(sizeof(sstring_t));
	sstring_init(res);
	return res;	
}

static inline void sstring_append_char(sstring_t *dest, char c) {
//	debugString("%s\n", __FUNCTION__);
	buf_t *buf = dest->buf, *nbuf;
	if (!buf) {
		buf = dest->buf = buf_new(SSTRING_PAGE);
		dest->data = buf_data(buf);
	} else if (
		(buf->refcount != 1)	// Cope on Write
		|| (dest->len >= (buf->size + buf_data(buf) - dest->data))) // More space needed
	{
		if (buf_data(buf) != dest->data) {
			// Remove unused area at the beginning of buf
			nbuf = dest->buf = buf_new(SSTRING_ROUND_UP(dest->len+1));
			char *olddata = dest->data;
			dest->data = buf_data(nbuf);
			memcpy(dest->data, olddata, dest->len);
			buf_put(buf);
		} else {
			// Resize buf
			buf = dest->buf = buf_resize(buf, SSTRING_ROUND_UP(dest->len+1));
			dest->data = buf_data(buf);
		}
	}
	dest->data[dest->len++] = c;
}

static inline int sstring_has_space(sstring_t *str, size_t size) {
//	debugString("%s\n", __FUNCTION__);
	buf_t *buf = str->buf;
	if (!buf || buf->refcount != 1) return 0;
	return (buf->size - str->len + buf_data(buf) - str->data) >= size;
}

static inline char* sstring_data(sstring_t *str) {
	return str->data;
}

static inline char* sstring_data_end(sstring_t *str) {
	return &str->data[str->len];
}

static inline size_t sstring_len(sstring_t *str) {
	return str->len;
}

/***************************************
        String implementation
 ***************************************/

static void string_check(string_t *str) {
#ifdef DEBUG_STRING
	size_t len = 0;
	for (size_t i = 0, l = str->part_count; i < l; i++)
		len += str->parts[i].len;
	if (len != str->len) {
		*(int*)0 = 0;
	}
#endif
}

static inline void string_init(string_t *str) {
//	debugString("%s\n", __FUNCTION__);
	str->len = 0; str->part_count = 0;
}

static inline string_t* string_new() {
//	debugString("%s\n", __FUNCTION__);
	string_t *str = malloc(sizeof(string_t));
	str->len = 0; str->part_count = 0;
	return str;
}

static inline void string_clear(string_t *str) {
//	debugString("%s\n", __FUNCTION__);
	for (size_t i = 0, l = str->part_count; i < l; i++)
		sstring_clear(&str->parts[i]);
	str->len = 0; str->part_count = 0;
	memset(str, 0, sizeof(*str));
}

static inline void string_free(string_t *str) {
//	debugString("%s\n", __FUNCTION__);
	for (size_t i = 0, l = str->part_count; i < l; i++)
		sstring_clear(&str->parts[i]);
	str->len = 0; str->part_count = 0;
	memset(str, 0, sizeof(*str));
	free(str);
}

static inline char* string_flatten(string_t *str) {
	debugString("%s\n", __FUNCTION__);
	string_check(str);
	if (!str->len) return 0;
	if (str->part_count == 1)
		return buf_data(str->parts->buf);
	buf_t *buf = buf_new(str->len);
	char *data = buf_data(buf);
	for (size_t i = 0, l = str->part_count; i < l; i++) {
		memcpy(data, sstring_data(&str->parts[i]), sstring_len(&str->parts[i]));
		data += sstring_len(&str->parts[i]);
		sstring_clear(&str->parts[i]);
	}
	str->part_count = 1;
	memset(str->parts, 0, sizeof(str->parts));
	sstring_init_withbuf(str->parts, buf);
	debugString("%s end\n", __FUNCTION__);
	return buf_data(buf);
}

static inline void string_simplify(string_t *str) {
	const size_t maxlen_step = 2*1024;
	if (str->part_count == 1) return;
	size_t newpc = 0;
	size_t len, len1, j;
	sstring_t *part, newpart;
	for (size_t i = 0, l = str->part_count; i < l; i++) {
		part = &str->parts[i];
		len = part->len;
		size_t maxlen = maxlen_step;
		for (j = i + 1; (j < l) && ((len1 = len + (++part)->len) < maxlen); j++, maxlen += maxlen_step)
			len = len1;
		j--;
		if (j > i) {
			part = &str->parts[i];
			sstring_init_sized(&newpart, len);
			char *data = sstring_data(&newpart);
			newpart.len = len;
			for ( ; i <= j; i++, part++ ) {
				memcpy(data, sstring_data(part), sstring_len(part));
				data += sstring_len(part);
				sstring_clear(part);
			}
			str->parts[newpc] = newpart;
			i--;
		} else {
			if (newpc != i)
				str->parts[newpc] = str->parts[i];
		}
		newpc++;
	}
	str->part_count = newpc;
}

/* Returns a buffer at the end of the string,
   which can be filled e.g. with file reading */
static inline char* string_buf_reserve(string_t *str, size_t size) {
//	debugString("%s\n", __FUNCTION__);
	size_t pc = str->part_count;
	if (pc && sstring_has_space(&str->parts[pc-1], size))
		return sstring_data_end(&str->parts[pc-1]);
	if (str->part_count >= PART_SIZE-1)
		string_flatten(str);
	pc = str->part_count++;
	sstring_init_sized(&str->parts[pc], size);
	return sstring_data(&str->parts[pc]);
}

/* Increases length of string (use after buf_reserve with the count of bytes really readed
   must be <= space reserved with buf_reserve! */
static inline void string_buf_used(string_t *str, size_t len) {
//	debugString("%s\n", __FUNCTION__);
	size_t pc = str->part_count-1;
	if (len == 0)  {
		if (sstring_len(&str->parts[pc]) == 0) {
			sstring_clear(&str->parts[pc]);
			str->part_count = pc;
		}
	} else {
		str->len += len;
		str->parts[pc].len += len;
	}
}

static inline void string_append_char(string_t *str, char c) {
	debugString("%s\n", __FUNCTION__);
	size_t pc = str->part_count;
	if (pc && sstring_has_space(&str->parts[pc-1], 1)) {
		sstring_append_char(&str->parts[pc-1], c);
	} else {
		if (str->part_count >= PART_SIZE-1)
			string_flatten(str);
		pc = str->part_count++;
		sstring_init_sized(&str->parts[pc], SSTRING_PAGE);
		sstring_append_char(&str->parts[pc], c);
	}
	str->len++;
}

static inline void string_append_sstring(string_t *str, sstring_t *fs) {
	debugString("%s\n", __FUNCTION__);
	string_check(str);
	if (!fs->len) return;
	if (str->part_count >= PART_SIZE-1)
		string_flatten(str);
	size_t pc = str->part_count++;
	str->parts[pc] = *fs;
	buf_get(fs->buf);
	str->len += fs->len;
	string_check(str);
	debugString("%s end\n", __FUNCTION__);
}

// Do not append to the same string!!!
static inline void string_append_string(string_t *str, string_t *fs) {
	debugString("%s\n", __FUNCTION__);
	string_check(str);
	if (!fs->part_count) return;
	if (str == fs) return;
	size_t addparts = fs->part_count;
	int doflatten = 0;
	if (str->part_count + addparts >= PART_SIZE-1) {
		string_flatten(str);
		if (str->part_count + addparts >= PART_SIZE-1)
			doflatten = 1;
	}
	sstring_t *part = &str->parts[str->part_count];
	memcpy(part, fs->parts, fs->part_count * sizeof(sstring_t));
	for (size_t i = 0; i < fs->part_count; i++, part++)
		buf_get(part->buf);
	str->part_count += fs->part_count;
	str->len += fs->len;
	if (doflatten)
		string_flatten(str);
	string_check(str);
	debugString("%s end\n", __FUNCTION__);
}

// Do not append to the same string!!!
static inline void string_append_from(string_t *str, string_pos_t *from) {
	debugString("%s\n", __FUNCTION__);
	string_check(str);
	string_t *fs = from->str;
	if (!fs || !fs->part_count) return;
	if (str == fs) return;
	size_t addparts = fs->part_count - from->part;
	int doflatten = 0;
	if (str->part_count + addparts >= PART_SIZE-1) {
		string_flatten(str);
		if (str->part_count + addparts >= PART_SIZE-1)
			doflatten = 1;
	}
	sstring_t *part = &str->parts[str->part_count];
	memcpy(part, &fs->parts[from->part], addparts * sizeof(sstring_t));
	part->len -= from->pos;
	part->data += from->pos;
	for (size_t i = 0; i < addparts; i++, part++)
		buf_get(part->buf);
	str->part_count += addparts;
	str->len += fs->len - from->abspos;
	if (doflatten)
		string_flatten(str);
	string_check(str);
}

// Do not append to the same string!!!
static inline void string_append_range(string_t *str, string_pos_t *from, string_pos_t *to) {
	debugString("%s\n", __FUNCTION__);
	string_check(str);
	if (!to->str) {
		string_append_from(str, from);
		return;
	}
	string_t *fs = from->str;
	if (!fs || !fs->part_count || to->str != fs) return;
	if (str == fs) return;
	size_t addparts = to->part - from->part + 1;
	int doflatten = 0;
	if (str->part_count + addparts >= PART_SIZE-1) {
		string_flatten(str);
		if (str->part_count + addparts >= PART_SIZE-1)
			doflatten = 1;
		string_check(str);
	}
	sstring_t *part = &str->parts[str->part_count];
	string_check(str);
	str->part_count += addparts;
	sstring_t *lastpart = &str->parts[str->part_count-1];
	memcpy(part, &fs->parts[from->part], addparts * sizeof(sstring_t));
	lastpart->len = to->pos;
	part->len -= from->pos; part->data += from->pos;
	for (size_t i = 0; i < addparts; i++, part++)
		buf_get(part->buf);
	str->len += to->abspos - from->abspos;
	string_check(str);
	if (doflatten)
		string_flatten(str);
	string_check(str);
}

static inline size_t string_len(string_t *str) {
	return str->len;
}

/***************************************
        String pos implementation
 ***************************************/
/* DO NOT USE THEM ON CHANGING STRINGS */

static inline void string_begin(string_t *str, string_pos_t *pos) {
	if (str->len) {
		pos->str = str; pos->abspos = pos->pos = pos->part = 0;
		sstring_t *pa = str->parts;
		while (pa->len == 0) { pos->part++; pa++; }
		pos->curlen = pa->len;
		pos->data = pa->data;
	}
}

static inline void string_pos_clear(string_pos_t *pos) {
	pos->str = 0;
	pos->abspos = pos->pos = pos->part = pos->curlen = 0;
	pos->data = 0;
}

static inline void string_end(string_t *str, string_pos_t *pos) {
	string_pos_clear(pos);
}

static inline int string_pos_eos(string_pos_t *pos) {
	return pos->str == 0;
}

static inline void string_pos_prev(string_pos_t *pos, string_t *str) {
	if (!pos->str) {
		pos->str = str;
		sstring_t *pa = &str->parts[pos->part = str->part_count-1];
		pos->pos = pa->len - 1;
		pos->curlen = pa->len;
		pos->data = &pa->data[pos->pos];
		pos->abspos = str->len - 1;
	} else if (pos->pos) {
		pos->pos--; pos->abspos--; pos->data--;
	} else {
		if (pos->abspos == 0) return;
		pos->abspos--;
		sstring_t *pa = &str->parts[pos->part = str->part_count-1];
		while (pa->len == 0) {
			pos->part--;
			pa--;
		}
		pos->pos = pa->len - 1;
		pos->curlen = pa->len;
		pos->data = &pa->data[pos->pos];
	}
}

static inline void string_pos_next(string_pos_t *pos) {
	string_t *str = pos->str;
	if (!str) return;
	pos->abspos++; pos->pos++;
	if (pos->pos < pos->curlen) {
		pos->data++;
	} else if (pos->abspos >= str->len) {
		string_pos_clear(pos);
	} else {
		pos->pos = 0;
		pos->part++;
		sstring_t *pa = &str->parts[pos->part];
		while (pa->len == 0) { pos->part++; pa++; }
		pos->curlen = pa->len;
		pos->data = pa->data;
	}
}

static inline void string_pos_inc(string_pos_t *pos, size_t step) {
	string_t *str = pos->str;
	if (!str) return;
	pos->abspos += step; pos->pos += step;
	if (pos->pos < pos->curlen) {
		pos->data += step;
	} else if (pos->abspos >= str->len) {
		string_pos_clear(pos);
	} else {
		pos->pos -= pos->curlen;
		pos->part++;
		sstring_t *pa = &str->parts[pos->part];
		while (pos->pos >= pa->len) {
			pos->pos -= pa->len;
			pa++;
			pos->part++;
		}
		pos->curlen = pa->len;
		pos->data = &pa->data[pos->pos];
	}
}

static inline char string_pos_get(string_pos_t *pos) {
	if (!pos->str) return 0;
	return *(pos->data);
}

static inline int string_pos_take(string_pos_t *pos, char *c) {
	if (!pos->str) return 0;
	*c = *pos->data;
	string_pos_next(pos);
	return 1;
}

static inline size_t string_pos_remain(string_pos_t *pos) {
	if (!pos->str) return 0;
	return pos->str->len - pos->abspos;
}

/***************************************
        Search algorithm
 ***************************************/

static inline int string_find_sstring(string_pos_t *pos_haystack, sstring_t *needle) {
	char *search = sstring_data(needle);
	size_t len = sstring_len(needle);
	char match[len];
	for (int i = 0; i < len; i++) {
		match[i] = string_pos_get(pos_haystack);
		string_pos_next(pos_haystack);
		if (string_pos_eos(pos_haystack)) return 0;
	}
	size_t mpos = 0;
	for (;;) {
		for (size_t j = mpos, i = 0; i < len; i++, j = (j+1)%len)
			if (match[j] != search[i]) goto nextchar;
		return 1;
nextchar:
		if (!string_pos_take(pos_haystack, &match[mpos])) return 0;
		mpos = (mpos + 1) % len;
	}
}