#include "system.h"

#include <stdio.h>

#include <stdlib.h>

#include <rpm/rpmstring.h>

#include <rpm/rpmstrpool.h>

#include "debug.h"

#define STRDATA_CHUNKS 1024

#define STRDATA_CHUNK 65536

#define STROFFS_CHUNK 2048

/* XXX this is ridiculously small... */

#define STRHASH_INITSIZE 1024

static int pool_debug = 0;

typedef struct poolHash_s * poolHash;

typedef struct poolHashBucket_s poolHashBucket;

struct poolHashBucket_s {

    rpmsid keyid;

};

struct poolHash_s {

    int numBuckets;

    poolHashBucket * buckets;

    int keyCount;

};

struct rpmstrPool_s {

    const char ** offs;		/* pointers into data area */

    rpmsid offs_size;		/* largest offset index */;

    rpmsid offs_alloced;	/* offsets allocation size */

    char ** chunks;		/* memory chunks for storing the strings */

    size_t chunks_size;		/* current chunk */

    size_t chunks_allocated;	/* allocated size of the chunks array */

    size_t chunk_allocated;	/* size of the current chunk */

    size_t chunk_used;		/* usage of the current chunk */

    poolHash hash;		/* string -> sid hash table */

    int frozen;			/* are new id additions allowed? */

    int nrefs;			/* refcount */

};

/* calculate hash and string length on at once */

static inline unsigned int rstrlenhash(const char * str, size_t * len)

{

    /* Jenkins One-at-a-time hash */

    unsigned int hash = 0xe4721b68;

    const char * s = str;

    while (*s != '\0') {

      hash += *s;

      hash += (hash << 10);

      hash ^= (hash >> 6);

      s++;

    }

    hash += (hash << 3);

    hash ^= (hash >> 11);

    hash += (hash << 15);

    if (len)

	*len = (s - str);

    return hash;

}

static inline unsigned int rstrnlenhash(const char * str, size_t n, size_t * len)

{

    /* Jenkins One-at-a-time hash */

    unsigned int hash = 0xe4721b68;

    const char * s = str;

    while (*s != '\0' && n-- > 0) {

      hash += *s;

      hash += (hash << 10);

      hash ^= (hash >> 6);

      s++;

    }

    hash += (hash << 3);

    hash ^= (hash >> 11);

    hash += (hash << 15);

    if (len)

	*len = (s - str);

    return hash;

}

static inline unsigned int rstrnhash(const char * string, size_t n)

{

    return rstrnlenhash(string, n, NULL);

}

unsigned int rstrhash(const char * string)

{

    return rstrlenhash(string, NULL);

}

static inline unsigned int hashbucket(unsigned int hash, unsigned int number)

{

    return hash + number*number;

}

static poolHash poolHashCreate(int numBuckets)

{

    poolHash ht;

    ht = xmalloc(sizeof(*ht));

    ht->numBuckets = numBuckets;

    ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));

    ht->keyCount = 0;

    return ht;

}

static void poolHashResize(rpmstrPool pool, int numBuckets)

{

    poolHash ht = pool->hash;

    poolHashBucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));

    for (int i=0; i<ht->numBuckets; i++) {

        if (!ht->buckets[i].keyid) continue;

        unsigned int keyHash = rstrhash(rpmstrPoolStr(pool, ht->buckets[i].keyid));

        for (unsigned int j=0;;j++) {

            unsigned int hash = hashbucket(keyHash, j) % numBuckets;

            if (!buckets[hash].keyid) {

                buckets[hash].keyid = ht->buckets[i].keyid;

                break;

            }

        }

    }

    free((void *)(ht->buckets));

    ht->buckets = buckets;

    ht->numBuckets = numBuckets;

}

static void poolHashAddHEntry(rpmstrPool pool, const char * key, unsigned int keyHash, rpmsid keyid)

{

    poolHash ht = pool->hash;

    /* keep load factor between 0.25 and 0.5 */

    if (2*(ht->keyCount) > ht->numBuckets) {

        poolHashResize(pool, ht->numBuckets * 2);

    }

    for (unsigned int i=0;;i++) {

        unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;

        if (!ht->buckets[hash].keyid) {

            ht->buckets[hash].keyid = keyid;

            ht->keyCount++;

            break;

        } else if (!strcmp(rpmstrPoolStr(pool, ht->buckets[hash].keyid), key)) {

            return;

        }

    }

}

static void poolHashAddEntry(rpmstrPool pool, const char * key, rpmsid keyid)

{

    poolHashAddHEntry(pool, key, rstrhash(key), keyid);

}

static void poolHashEmpty( poolHash ht)

{

    unsigned int i;

    if (ht->keyCount == 0) return;

    for (i = 0; i < ht->numBuckets; i++) {

	ht->buckets[i].keyid = 0;

    }

    ht->keyCount = 0;

}

static poolHash poolHashFree(poolHash ht)

{

    if (ht==NULL)

        return ht;

    poolHashEmpty(ht);

    ht->buckets = _free(ht->buckets);

    ht = _free(ht);

    return NULL;

}

static void poolHashPrintStats(rpmstrPool pool)

{

    poolHash ht = pool->hash;

    int i;

    int collisions = 0;

    int maxcollisions = 0;

    for (i=0; i<ht->numBuckets; i++) {

        unsigned int keyHash = rstrhash(rpmstrPoolStr(pool, ht->buckets[i].keyid));

        for (unsigned int j=0;;j++) {

            unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;

            if (hash==i) {

                collisions += j;

                maxcollisions = maxcollisions > j ? maxcollisions : j;

                break;

            }

        }

    }

    fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);

    fprintf(stderr, "Keys: %i\n", ht->keyCount);

    fprintf(stderr, "Collisions: %i\n", collisions);

    fprintf(stderr, "Max collisions: %i\n", maxcollisions);

}

static void rpmstrPoolRehash(rpmstrPool pool)

{

    int sizehint;

    if (pool->offs_size < STRHASH_INITSIZE)

	sizehint = STRHASH_INITSIZE;

    else

	sizehint = pool->offs_size * 2;

    if (pool->hash)

	pool->hash = poolHashFree(pool->hash);

    pool->hash = poolHashCreate(sizehint);

    for (int i = 1; i <= pool->offs_size; i++)

	poolHashAddEntry(pool, rpmstrPoolStr(pool, i), i);

}

rpmstrPool rpmstrPoolCreate(void)

{

    rpmstrPool pool = xcalloc(1, sizeof(*pool));

    pool->offs_alloced = STROFFS_CHUNK;

    pool->offs = xcalloc(pool->offs_alloced, sizeof(*pool->offs));

    pool->chunks_allocated = STRDATA_CHUNKS;

    pool->chunks = xcalloc(pool->chunks_allocated, sizeof(*pool->chunks));

    pool->chunks_size = 1;

    pool->chunk_allocated = STRDATA_CHUNK;

    pool->chunks[pool->chunks_size] = xcalloc(1, pool->chunk_allocated);

    pool->offs[1] = pool->chunks[pool->chunks_size];

    rpmstrPoolRehash(pool);

    pool->nrefs = 1;

    return pool;

}

rpmstrPool rpmstrPoolFree(rpmstrPool pool)

{

    if (pool) {

	if (pool->nrefs > 1) {

	    pool->nrefs--;

	} else {

	    if (pool_debug)

		poolHashPrintStats(pool);

	    poolHashFree(pool->hash);

	    free(pool->offs);

	    for (int i=1;i<=pool->chunks_size;i++) {

		pool->chunks[i] = _free(pool->chunks[i]);

	    }

	    free(pool->chunks);

	    free(pool);

	}

    }

    return NULL;

}

rpmstrPool rpmstrPoolLink(rpmstrPool pool)

{

    if (pool)

	pool->nrefs++;

    return pool;

}

void rpmstrPoolFreeze(rpmstrPool pool, int keephash)

{

    if (pool && !pool->frozen) {

	if (!keephash) {

	    pool->hash = poolHashFree(pool->hash);

	}

	pool->offs_alloced = pool->offs_size + 2; /* space for end marker */

	pool->offs = xrealloc(pool->offs,

			      pool->offs_alloced * sizeof(*pool->offs));

	pool->frozen = 1;

    }

}

void rpmstrPoolUnfreeze(rpmstrPool pool)

{

    if (pool) {

	if (pool->hash == NULL) {

	    rpmstrPoolRehash(pool);

	}

	pool->frozen = 0;

    }

}

static rpmsid rpmstrPoolPut(rpmstrPool pool, const char *s, size_t slen, unsigned int hash)

{

    char *t = NULL;

    size_t ssize = slen + 1;

    pool->offs_size += 1;

    if (pool->offs_alloced <= pool->offs_size) {

	pool->offs_alloced += STROFFS_CHUNK;

	pool->offs = xrealloc(pool->offs,

			      pool->offs_alloced * sizeof(*pool->offs));

    }

    /* Do we need a new chunk to store the string? */

    if (ssize > pool->chunk_allocated - pool->chunk_used) {

	pool->chunks_size += 1;

	/* Grow chunks array if needed */

	if (pool->chunks_size >= pool->chunks_allocated) {

	    pool->chunks_allocated += pool->chunks_allocated;

	    pool->chunks = xrealloc(pool->chunks,

				pool->chunks_allocated * sizeof(*pool->chunks));

	}

	/* Ensure the string fits in the new chunk we're about to allocate */

	if (ssize > pool->chunk_allocated) {

	    pool->chunk_allocated = 2 * ssize;

	}

	pool->chunks[pool->chunks_size] = xcalloc(1, pool->chunk_allocated);

	pool->chunk_used = 0;

    }

    /* Copy the string into current chunk, ensure termination */

    t = memcpy(pool->chunks[pool->chunks_size] + pool->chunk_used, s, slen);

    t[slen] = '\0';

    pool->chunk_used += ssize;

    /* Actually add the string to the pool */

    pool->offs[pool->offs_size] = t;

    poolHashAddHEntry(pool, t, hash, pool->offs_size);

    return pool->offs_size;

}

static rpmsid rpmstrPoolGet(rpmstrPool pool, const char * key, size_t keylen,

			    unsigned int keyHash)

{

    poolHash ht = pool->hash;

    const char * s;

    for (unsigned int i=0;; i++) {

        unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;

        if (!ht->buckets[hash].keyid) {

            return 0;

        }

	s = rpmstrPoolStr(pool, ht->buckets[hash].keyid);

	/* pool string could be longer than keylen, require exact matche */

	if (strncmp(s, key, keylen) == 0 && s[keylen] == '\0')

	    return ht->buckets[hash].keyid;

    }

}

static inline rpmsid strn2id(rpmstrPool pool, const char *s, size_t slen,

			     unsigned int hash, int create)

{

    rpmsid sid = 0;

    if (pool && pool->hash) {

	sid = rpmstrPoolGet(pool, s, slen, hash);

	if (sid == 0 && create && !pool->frozen)

	    sid = rpmstrPoolPut(pool, s, slen, hash);

    }

    return sid;

}

rpmsid rpmstrPoolIdn(rpmstrPool pool, const char *s, size_t slen, int create)

{

    rpmsid sid = 0;

    if (s != NULL) {

	unsigned int hash = rstrnhash(s, slen);

	sid = strn2id(pool, s, slen, hash, create);

    }

    return sid;

}

rpmsid rpmstrPoolId(rpmstrPool pool, const char *s, int create)

{

    rpmsid sid = 0;

    if (s != NULL) {

	size_t slen;

	unsigned int hash = rstrlenhash(s, &slen);

	sid = strn2id(pool, s, slen, hash, create);

    }

    return sid;

}

const char * rpmstrPoolStr(rpmstrPool pool, rpmsid sid)

{

    const char *s = NULL;

    if (pool && sid > 0 && sid <= pool->offs_size)

	s = pool->offs[sid];

    return s;

}

size_t rpmstrPoolStrlen(rpmstrPool pool, rpmsid sid)

{

    size_t slen = 0;

    if (pool && sid > 0 && sid <= pool->offs_size) {

	slen = strlen(pool->offs[sid]);

    }

    return slen;

}

int rpmstrPoolStreq(rpmstrPool poolA, rpmsid sidA,

		    rpmstrPool poolB, rpmsid sidB)

{

    if (poolA == poolB)

	return (sidA == sidB);

    else

	return rstreq(rpmstrPoolStr(poolA, sidA), rpmstrPoolStr(poolB, sidB));

}

rpmsid rpmstrPoolNumStr(rpmstrPool pool)

{

    return (pool != NULL) ? pool->offs_size : 0;

}