/*
 * Remove duplicate fields in CSV file after column three.
 *
 * Compile native Windows program with:
 * cl -nologo -DUSE_HASH -W3 -O2 -Oi- -GS- -Zl test_native_hash.c \
 *   memcpy64.obj memset64.obj memcmp64.obj strchr64.obj \
 *   -link -release -entry:start -subsystem:console -map kernel32.lib
 */

#ifdef _WIN32
  #define UNICODE
  #include <windows.h>
#else /* Linux */
  #include <unistd.h>
  #include <fcntl.h>
  #define INVALID_HANDLE_VALUE -1
  #define TEXT(s) s
  typedef char *PSTR, *PTSTR;
  typedef size_t SIZE_T;
  typedef void VOID, *PVOID;
  typedef int INT, HANDLE;
  typedef unsigned UINT;
#endif

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define STATIC static
#define INLINE static __inline

#define NELEM(ar)   (sizeof(ar)/sizeof(*ar))
#define HASHLEN     256
#define MAXFIELDS   64
#define LINELEN     (2*4096)
#define BUFLEN      (16*4096)


typedef struct {    /* Simple Input/Output Buffer */
    PSTR ptr, end, buf;
    SIZE_T len;
    HANDLE file;
} IOBUF;


STATIC PVOID alloc_memory(SIZE_T size)
{
    PVOID p;

#ifdef _WIN32
    p = VirtualAllocEx((HANDLE)-1, NULL, size,
            MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE);
#else
    if ((p = sbrk(size)) == (PVOID)-1)
        p = NULL;
#endif
    return p;
}


STATIC INT open_file(IOBUF *fp, PTSTR filename, PTSTR mode)
{
    if (!(fp->buf = alloc_memory(BUFLEN+1)))
        return -1;
    fp->len = BUFLEN;
    fp->ptr = fp->buf;

    if (mode[0] == 'r') {
#ifdef _WIN32
        fp->file = CreateFile(filename, GENERIC_READ, 0, NULL,
                OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
#else
        fp->file = open(filename, O_RDONLY);
#endif
        fp->end = fp->buf;
    } else {
#ifdef _WIN32
        fp->file = CreateFile(filename, GENERIC_WRITE, 0, NULL,
                CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
#else
        fp->file = open(filename, O_WRONLY|O_TRUNC|O_CREAT, 0644);
#endif
        fp->end = fp->buf + fp->len;
    }
    fp->end[0] = '\0';
    return (fp->file == INVALID_HANDLE_VALUE)? -1 : 0;
}


STATIC SIZE_T fill_buf(IOBUF *fp)
{
#ifdef _WIN32
    DWORD k;
#else
    SIZE_T k;
#endif
    SIZE_T n = 0;

    if (fp->ptr < fp->end) {
        /* move unread bytes to start of buffer */
        n = fp->end - fp->ptr;
        memcpy(fp->buf, fp->ptr, n);
    }

#ifdef _WIN32
    if (!ReadFile(fp->file, fp->buf + n, (DWORD)(fp->len - n), &k, NULL))
        return -1;
    n += k;
#else
    if ((k = read(fp->file, fp->buf + n, fp->len - n)) == -1)
        return -1;
    n += k;
#endif
    fp->ptr = fp->buf;
    fp->end = fp->buf + n;
    fp->end[0] = '\0';

    return k;
}


STATIC INT flush_buf(IOBUF *fp)
{
#ifdef _WIN32
    DWORD k;
#endif
    SIZE_T n = fp->ptr - fp->buf;

    fp->ptr = fp->buf;
#ifdef _WIN32
    if (!WriteFile(fp->file, fp->buf, (DWORD)n, &k, NULL))
        return -1;
#else
    if (write(fp->file, fp->buf, n) != n)
        return -1;
#endif
    return 0;
}


STATIC VOID exit_process(INT status)
{
#ifdef _WIN32
    ExitProcess(status);
#else
    _exit(status);
#endif
}


typedef struct {
    PSTR    str;
    SIZE_T  length;
} FIELD;


#if 0
INLINE UINT hash(PSTR key, SIZE_T len)
{
	UINT hash = 0;

	for(SIZE_T i = 0; i < len; i++)
		hash = 31 * hash + key[i];
	return hash;
}
#else
INLINE UINT hash(PSTR key, SIZE_T len)
{
	UINT hash = key[0] + key[len-1];
	return hash;
}
#endif


INLINE int equal_fields(FIELD *a, FIELD *b)
{
    return a->length == b->length && !memcmp(a->str, b->str, a->length);
}


INLINE FIELD *insert(FIELD *hashtbl[], FIELD *elem)
{
    FIELD *p;
    UINT n = hash(elem->str, elem->length) % HASHLEN;

    if (!(p = hashtbl[n])) {
        hashtbl[n] = elem;
        return elem;
    }

    if (equal_fields(p, elem))
        return p;

    while (++n < HASHLEN) {
        if (!hashtbl[n]) {
            hashtbl[n] = elem;
            return elem;
        }
    }

    return NULL;
}


#ifndef USE_HASH
INLINE INT search_field(FIELD *hashtbl[], FIELD tbl[], SIZE_T len, FIELD *elem)
{
    FIELD *rp;

    if (elem < (rp = tbl + 3))
        return 0;
    while (rp < elem) {
        if (equal_fields(rp, elem))
            return 1;
        rp++;
    }
    return 0;
}
#else
INLINE INT search_field(FIELD *hashtbl[], FIELD tbl[], SIZE_T len, FIELD *elem)
{
    FIELD *p;

    if (elem < (tbl + 3))
        return 0;
    p = insert(hashtbl, elem);
    return p != elem;
}
#endif


INT start()
{
    PSTR s, p;
    SIZE_T n, k, len;
    IOBUF in, out;
    FIELD *rp, tbl[MAXFIELDS];
    FIELD *hashtbl[HASHLEN];

    if (open_file(&in, TEXT("list.txt"), TEXT("r")))
E:      exit_process(-1);

    if (open_file(&out, TEXT("nodup.txt"), TEXT("w")))
        goto E;

    len = 0;
    p = in.ptr;
    memset(&tbl, 0, sizeof(tbl));
    memset(&hashtbl, 0, sizeof(hashtbl));

    for (;;) {

        if ((s = strchr(p, ';'))) {

            /* found field terminated with ';' */
            rp = tbl + len++;
            rp->str = p;
            rp->length = (s - p);

            if (*++s == '\n') { /* end of line */

                /* make space in output buffer */
                if (out.end - out.ptr < LINELEN)
                    flush_buf(&out);

                /* for each field in line */
                for (n = 0; n < len; n++) {
                    rp = tbl + n;
                    if (!search_field(hashtbl, tbl, len, rp)) {
                        memcpy(out.ptr, rp->str, rp->length);
                        out.ptr += rp->length;
                    }
                    *out.ptr++ = ';';
                }
                *out.ptr++ = '\n';

                /* finished with this line */
                n = s - in.ptr;
                in.ptr += n + 1;
                s = in.ptr;

                /* reset line field data */
                memset(&tbl, 0, sizeof(tbl));
                memset(&hashtbl, 0, sizeof(hashtbl));
                len = 0;
            }

            p = s;  /* start of next field */
        }
        else {
            /* read bytes from input */
            s = in.ptr;
            if ((n = fill_buf(&in)) < 0)
                goto E;
            if (n == 0)
                break;
            k = s - in.ptr;
            p -= k;
            for (n = 0; n < len; n++)
                tbl[n].str -= k;
        }
    }

    flush_buf(&out);
    exit_process(0);
}
