strset.c 3.17 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
/* the Music Player Daemon (MPD)
 * Copyright (C) 2008 Max Kellermann <max@duempel.org>
 * This project's homepage is: http://www.musicpd.org
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "strset.h"
#include "utils.h"
#include "os_compat.h"

#define NUM_SLOTS 16384

struct strset_slot {
	struct strset_slot *next;
	const char *value;
};

struct strset {
	unsigned size;

	struct strset_slot *current_slot;
	unsigned next_slot;

	struct strset_slot slots[NUM_SLOTS];
};

static unsigned calc_hash(const char *p) {
	unsigned hash = 5381;

	assert(p != NULL);

	while (*p != 0)
		hash = (hash << 5) + hash + *p++;

	return hash;
}

mpd_malloc struct strset *strset_new(void)
{
	struct strset *set = xcalloc(1, sizeof(*set));
	return set;
}

void strset_free(struct strset *set)
{
	unsigned i;

	for (i = 0; i < NUM_SLOTS; ++i) {
		struct strset_slot *slot = set->slots[i].next, *next;

		while (slot != NULL) {
			next = slot->next;
			free(slot);
			slot = next;
		}
	}

	free(set);
}

void strset_add(struct strset *set, const char *value)
{
	struct strset_slot *base_slot
		= &set->slots[calc_hash(value) % NUM_SLOTS];
	struct strset_slot *slot = base_slot;

	if (base_slot->value == NULL) {
		/* empty slot - put into base_slot */
		assert(base_slot->next == NULL);

		base_slot->value = value;
		++set->size;
		return;
	}

88
	for (slot = base_slot; slot != NULL; slot = slot->next)
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
		if (strcmp(slot->value, value) == 0)
			/* found it - do nothing */
			return;

	/* insert it into the slot chain */
	slot = xmalloc(sizeof(*slot));
	slot->next = base_slot->next;
	slot->value = value;
	base_slot->next = slot;
	++set->size;
}

int strset_get(const struct strset *set, const char *value)
{
	const struct strset_slot *slot = &set->slots[calc_hash(value)];

	if (slot->value == NULL)
		return 0;

	for (slot = slot->next; slot != NULL; slot = slot->next)
		if (strcmp(slot->value, value) == 0)
			/* found it - do nothing */
			return 1;

	return 0;
}

unsigned strset_size(const struct strset *set)
{
	return set->size;
}

void strset_rewind(struct strset *set)
{
	set->current_slot = NULL;
	set->next_slot = 0;
}

const char *strset_next(struct strset *set)
{
	if (set->current_slot != NULL && set->current_slot->next != NULL) {
		set->current_slot = set->current_slot->next;
		return set->current_slot->value;
	}

	while (set->next_slot < NUM_SLOTS &&
	       set->slots[set->next_slot].value == NULL)
		++set->next_slot;

	if (set->next_slot >= NUM_SLOTS)
		return NULL;

	set->current_slot = &set->slots[set->next_slot++];
	return set->current_slot->value;
}