|
/**
|
|
* Copyright © 2019, Oracle and/or its affiliates. All rights reserved.
|
|
*
|
|
* Licensed under the Universal Permissive License v 1.0 as shown at
|
|
* http://oss.oracle.com/licenses/upl
|
|
*
|
|
*/
|
|
#include "stringset.h"
|
|
#include "hashfun.h"
|
|
#include "malloc.h"
|
|
#include <assert.h>
|
|
#include <string.h>
|
|
struct stringset {
|
|
size_t n;
|
|
size_t limit;
|
|
char **strings;
|
|
};
|
|
struct stringset *mk_stringset(void) {
|
|
struct stringset *MALLOC(r);
|
|
const size_t N = 2;
|
|
char **MALLOC_N(strings, N);
|
|
for (size_t i = 0; i < N; i++) {
|
|
strings[i] = NULL;
|
|
}
|
|
*r = (struct stringset){0, N, strings};
|
|
return r;
|
|
}
|
|
struct stringset *stringset_destroy(struct stringset *stringset) {
|
|
for (size_t i = 0; i < stringset->limit; i++) {
|
|
if (stringset->strings[i]) {
|
|
FREE(stringset->strings[i]);
|
|
}
|
|
}
|
|
FREE(stringset->strings);
|
|
FREE(stringset);
|
|
return NULL;
|
|
}
|
|
int stringset_contains(const struct stringset *stringset, const char *string) {
|
|
size_t mask = stringset->limit -1;
|
|
assert((stringset->limit & mask) == 0);
|
|
size_t h = hash_string(string) & mask;
|
|
for (size_t count = 0; count < stringset->limit; count++) {
|
|
size_t hi = (h + count) & mask;
|
|
if (stringset->strings[hi] == NULL) return 0;
|
|
if (strcmp(stringset->strings[hi], string) == 0) return 1;
|
|
}
|
|
assert(0);
|
|
}
|
|
static void stringset_insert_internal(struct stringset *stringset, char *string) {
|
|
// Requires string is not in the list. String must have been
|
|
// malloc'd and now the stringset will own it.
|
|
size_t mask = stringset->limit -1;
|
|
assert((stringset->limit & mask) == 0);
|
|
size_t h = hash_string(string) & mask;
|
|
stringset->n++;
|
|
for (size_t count = 0; count < stringset->limit; count++) {
|
|
size_t hi = (h + count) & mask;
|
|
if (stringset->strings[hi] == NULL) {
|
|
stringset->strings[hi] = string;
|
|
return;
|
|
}
|
|
}
|
|
assert(0);
|
|
}
|
|
|
|
void stringset_insert(struct stringset *stringset, const char *string) {
|
|
if (stringset_contains(stringset, string)) {
|
|
return;
|
|
}
|
|
if (stringset->n * 2 >= stringset->limit) {
|
|
struct stringset old = *stringset;
|
|
const size_t new_limit = 2 * stringset->limit;
|
|
char **MALLOC_N(newstrings, new_limit);
|
|
for (size_t i = 0; i < new_limit; i++) {
|
|
newstrings[i] = NULL;
|
|
}
|
|
*stringset = (struct stringset){0, new_limit, newstrings};
|
|
for (size_t i = 0; i < old.limit; i++) {
|
|
if (old.strings[i]) {
|
|
stringset_insert_internal(stringset, old.strings[i]);;
|
|
}
|
|
}
|
|
FREE(old.strings);
|
|
}
|
|
stringset_insert_internal(stringset, strdup(string));
|
|
}
|