root/software/fss-parallel-tools/stringset.c @ b1d8e8c9
| 7e8045d8 | David Sorber | /**
|
|
* 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));
|
|||
}
|