nit/set.c

/*    This file is part of nit.
 *
 *    Nit is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU Lesser General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    Nit is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Lesser General Public License for more details.
 *
 *    You should have received a copy of the GNU Lesser General Public License
 *    along with nit.  If not, see <http://www.gnu.org/licenses/>.
*/

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

#include "set.h"

#define BIN_MAX_DENSITY 5
#define H_SEED 37

const int bin_num[31] = {
	1, 3,
	8 + 3, 16 + 3, 32 + 5, 64 + 3, 128 + 3, 256 + 27, 512 + 9,
	1024 + 9, 2048 + 5, 4096 + 3, 8192 + 27, 16384 + 43, 32768 + 3,
	65536 + 45, 131072 + 29, 262144 + 3, 524288 + 21, 1048576 + 7,
	2097152 + 17, 4194304 + 15, 8388608 + 9, 16777216 + 43, 33554432 + 35,
	67108864 + 15, 134217728 + 29, 268435456 + 3, 536870912 + 11,
	1073741824 + 85, 0
};

#define ROT32(x, y) ((x << y) | (x >> (32 - y)))

static uint32_t
murmur3_32(const char *key, uint32_t len, uint32_t seed)
{
	static const uint32_t c1 = 0xcc9e2d51;
	static const uint32_t c2 = 0x1b873593;
	static const uint32_t r1 = 15;
	static const uint32_t r2 = 13;
	static const uint32_t m = 5;
	static const uint32_t n = 0xe6546b64;

	uint32_t h = seed;

	const int nblocks = len / 4;
	const uint32_t *blocks = (const uint32_t *) key;
	int i;
	uint32_t k;

	for (i = 0; i < nblocks; i++) {
		k = blocks[i];
		k *= c1;
		k = ROT32(k, r1);
		k *= c2;

		h ^= k;
		h = ROT32(h, r2) * m + n;
	}

	const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
	uint32_t k1 = 0;

	switch (len & 3) {
	case 3:
		k1 ^= tail[2] << 16;
		/* fallthru */
	case 2:
		k1 ^= tail[1] << 8;
		/* fallthru */
	case 1:
		k1 ^= tail[0];

		k1 *= c1;
		k1 = ROT32(k1, r1);
		k1 *= c2;
		h ^= k1;
	}

	h ^= len;
	h ^= (h >> 16);
	h *= 0x85ebca6b;
	h ^= (h >> 13);
	h *= 0xc2b2ae35;
	h ^= (h >> 16);
	return h;
}

static int
key_same(const Set_entry *entry, uint32_t key_len, const void *dat)
{
	if (key_len != entry->key_len)
		return 0;

	return !memcmp(entry->dat, dat, key_len);
}

Nit_error
set_init(Set *set, Disposer *disposer, int bin_pos)
{
	set->disposer = disposer;

	if (!(set->bins = calloc(bin_num[bin_pos], sizeof(*set->bins))))
		return NIT_ERROR_MEMORY;

	set->bin_pos = bin_pos;
	set->size = 0;
	return NIT_ERROR_FINE;
}

void
set_dispose(Set *set, Set_dispose set_dispose)
{
	for (int i = 0; i < bin_num[set->bin_pos]; ++i) {
	        Set_entry *entry = set->bins[i];

		while (entry) {
			Set_entry *tmp = entry->next;

			if (set_dispose)
				set_dispose(set->disposer, entry->key_len,
					    entry->dat);
			else if (set->disposer)
				set->disposer->dispose(entry->dat,
						     set->disposer->extra);

			free(entry);
			entry = tmp;
		}
	}

	free(set->bins);
}

static int
row_num(const void *key, uint32_t key_len, int num)
{
	return murmur3_32(key, key_len, H_SEED) % num;
}

static Set_entry *
set_entry(uint32_t key_len, const void *dat, uint32_t hash, Set_entry *next)
{
	Set_entry *entry = malloc(sizeof(*entry));

	if (!entry)
		return NULL;

	entry->dat = (void *) dat;
	entry->key_len = key_len;
	entry->hash = hash;
	entry->next = next;
	return entry;
}

static int
rehash(Set *set)
{
	int new_bin_num = bin_num[set->bin_pos + 1];
	Set_entry **new_bins = calloc(new_bin_num, sizeof(*set->bins));

	if (!new_bins)
		return -1;

	for (int i = 0; i < bin_num[set->bin_pos]; ++i) {
		for (Set_entry *entry = set->bins[i]; entry;) {
			Set_entry *tmp = entry->next;
			uint32_t row = entry->hash % new_bin_num;

		        entry->next = new_bins[row];
			new_bins[row] = entry;
			entry = tmp;
		}
	}

	free(set->bins);
	set->bins = new_bins;
	++set->bin_pos;
	return 0;
}

Nit_error
set_add(Set *set, uint32_t key_len, const void *dat)
{
	uint32_t hash = murmur3_32(dat, key_len, H_SEED);
	Set_entry **bin;
	Set_entry *new_entry;

	if ((set->size + 1) / bin_num[set->bin_pos] >= BIN_MAX_DENSITY &&
	    rehash(set) < 0)
		return NIT_ERROR_MEMORY;

	bin = &set->bins[hash % bin_num[set->bin_pos]];

	for (Set_entry *entry = *bin; entry; entry = entry->next)
		if (key_same(entry, key_len, dat))
			return NIT_ERROR_ALREADY;

	if (!(new_entry = set_entry(key_len, dat, hash, *bin)))
		return NIT_ERROR_MEMORY;

	*bin = new_entry;
	++set->size;
	return NIT_ERROR_FINE;
}

Nit_error
set_remove(Set *set, uint32_t key_len, void **dat)
{
        uint32_t row = row_num(*dat, key_len, bin_num[set->bin_pos]);

	for (Set_entry **entry = &set->bins[row]; *entry;
	     entry = &(*entry)->next)
		if (key_same(*entry, key_len, *dat)) {
			Set_entry *tmp = *entry;

			*dat = tmp->dat;
			*entry = tmp->next;
			free(tmp);
			return NIT_ERROR_FINE;
		}

	return NIT_ERROR_NOT_FOUND;
}

int
set_get(const Set *set, uint32_t key_len, void **dat)
{
        uint32_t row = row_num(*dat, key_len, bin_num[set->bin_pos]);

	for (Set_entry *entry = set->bins[row]; entry; entry = entry->next)
		if (key_same(entry, key_len, *dat)) {
			*dat = entry->dat;
			return 1;
		}

	return 0;
}

int
set_contains(const Set *set, uint32_t key_len, const void *dat)
{
	void **dat_ref = (void **) &dat;

	return !!set_get(set, key_len, dat_ref);
}

int
set_subset(const Set *super, const Set *sub)
{
	int i;

	if (sub->size > super->size)
		return 0;

	for (i = 0; i <= bin_num[sub->bin_pos]; ++i)
		for (Set_entry *entry = sub->bins[i]; entry;
		     entry = entry->next)
			if (!set_contains(super, entry->key_len, entry->dat))
				return 0;

	return 1;
}

int
set_equal(const Set *set1, const Set *set2)
{
	return set1->size != set2->size ? 0 : set_subset(set1, set2);
}

Nit_error
set_fill(Set *des, const Set *src)
{
	int bin;
	Set_entry *entry;

	set_foreach (src, bin, entry) {
		Nit_error error;

		if (set_contains(des, entry->key_len, entry->dat))
			continue;

		if ((error = set_add(des, entry->key_len, entry->dat)))
			return error;
	}

	return NIT_ERROR_FINE;
}

Nit_error
set_compl(Set *des, const Set *src, const Set *dif)
{
	int bin;
	Set_entry *entry;

	set_foreach (src, bin, entry) {
		Nit_error error;

		if (set_contains(des, entry->key_len, entry->dat) ||
		    set_contains(dif, entry->key_len, entry->dat))
			continue;

		if ((error = set_add(des, entry->key_len, entry->dat)))
			return error;
	}

	return NIT_ERROR_FINE;
}

Nit_error
set_inter(Set *des, const Set *src1, const Set *src2)
{
	const Set *large;
	const Set *small;
	int bin;
	Set_entry *entry;

	if (src1->size >= src2->size) {
		large = src1;
		small = src2;
	} else {
		large = src2;
		small = src1;
	}

	set_foreach (small, bin, entry) {
		Nit_error error;

		if (set_contains(des, entry->key_len, entry->dat) ||
		    !set_contains(large, entry->key_len, entry->dat))
			continue;

		if ((error = set_add(des, entry->key_len, entry->dat)))
			return error;
	}

	return NIT_ERROR_FINE;
}

static void
key_dsp(void *dat, void *extra)
{
	(void) extra;
	free(dat);
}

Disposer key_dspr = {
	.extra = NULL,
	.dispose = key_dsp
};

Nit_error
set_list(const Set *set, List *list, int init, int copy)
{
	int bin;
	Set_entry *sentry;
	Set_key *new_key;
	Nit_error error;

	if (!set->size)
		return NIT_ERROR_EMPTY;

	if (init)
		list_init(list, copy ? &key_dspr : NULL);

	set_foreach(set, bin, sentry) {
		List_entry *prev = NULL;
		List_entry *lentry;

		list_foreach (lentry, list) {
			Set_key *key = lentry->data;

			if (sentry->key_len < key->key_len)
				break;

			if (sentry->key_len == key->key_len) {
				int cmp = memcmp(sentry->dat, key->dat,
						 key->key_len);

				if (!cmp)
					goto next;

				if (cmp < 0)
					break;
			}

			prev = lentry;
		}

		if (!copy) {
			new_key = (Set_key *) sentry;
		} else {
			if (!(new_key = malloc(sizeof(*new_key))))
				return NIT_ERROR_MEMORY;

			new_key->key_len = sentry->key_len;

			if (!(new_key->dat = malloc(new_key->key_len))) {
				error = NIT_ERROR_MEMORY;
				goto err_dat;
			}

			memcpy(new_key->dat, sentry->dat, new_key->key_len);
		}

		if ((error = list_add(list, prev, new_key)))
			goto err_add;
	next:
		continue;
	}

	return NIT_ERROR_FINE;
err_add:
	free(new_key->dat);
err_dat:
	free(new_key);
	return error;
}