From b9ecd6e5e5b87fe1c4dab960e92246772002dd6a Mon Sep 17 00:00:00 2001 From: Stef Walter Date: Mon, 9 Jun 2008 17:22:43 +0000 Subject: Merge the two dns plugins --- common/strset.c | 276 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 276 insertions(+) create mode 100644 common/strset.c (limited to 'common/strset.c') diff --git a/common/strset.c b/common/strset.c new file mode 100644 index 0000000..801a358 --- /dev/null +++ b/common/strset.c @@ -0,0 +1,276 @@ +/* + * Copyright (c) 2008, Stefan Walter + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * * Redistributions in binary form must reproduce the + * above copyright notice, this list of conditions and + * the following disclaimer in the documentation and/or + * other materials provided with the distribution. + * * The names of contributors to this software may not be + * used to endorse or promote products derived from this + * software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +/* + * Originally from apache 2.0 + */ + +/* Copyright 2000-2004 The Apache Software Foundation + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +#include + +#include "strset.h" + +typedef struct _entry { + struct _entry* next; + unsigned int hash; + char *value; +} entry; + +struct _strset { + entry **array; + unsigned int count; + unsigned int max; +}; + +#define INITIAL_MAX 15 /* tunable == 2^n - 1 */ + +static entry** +alloc_array (unsigned int max) +{ + void *ret; + size_t len; + + assert (max); + + len = sizeof (entry*) * (max + 1); + ret = strset_malloc (len); + if (ret) + memset (ret, 0, len); + + return ret; +} + +strset* +strset_create (void) +{ + strset *set = strset_malloc (sizeof (strset)); + if (set) { + memset (set, 0, sizeof (strset)); + set->max = INITIAL_MAX; + set->array = alloc_array (set->max); + if (!set->array) { + strset_free (set); + set = NULL; + } + } + + return set; +} + +void +strset_destroy (strset *set) +{ + unsigned int i; + entry *ent, *next; + + if (!set) + return; + + /* Free all the entries */ + for (i = 0; i < set->max; ++i) { + next = NULL; + for (ent = set->array[i]; ent; ent = next) { + next = ent->next; + + assert (ent->value); + strset_free (ent); + } + } + + /* Free the set itself */ + strset_free (set->array); + strset_free (set); +} + +static int +expand_array (strset* set) +{ + entry** new_array; + entry* ent, *next; + unsigned int new_max, n, i; + + assert (set); + assert (set->max); + assert (set->array); + + new_max = set->max * 2 + 1; + new_array = alloc_array (new_max); + + if(!new_array) + return 0; + + /* Go through all the entries */ + for (i = 0; i < set->max; ++i) { + next = NULL; + for (ent = set->array[i]; ent; ent = next) { + next = ent->next; + + n = ent->hash & new_max; + ent->next = new_array[n]; + new_array[n] = ent; + } + } + + strset_free (set->array); + set->array = new_array; + set->max = new_max; + + return 1; +} + +static entry** +find_entry (strset* set, const char *value, int add) +{ + entry **ep, *e; + const char* p; + unsigned int hash; + size_t len; + + assert (set); + assert (set->max); + assert (set->array); + assert (value); + + hash = 0; + + for(p = value; *p; p++) + hash = hash * 33 + *p; + + /* scan linked list */ + for (ep = &set->array[hash & set->max], e = *ep; + e; ep = &e->next, e = *ep) + { + if (e->hash == hash && strcmp (e->value, value) == 0) + break; + } + + if (e || !add) + return ep; + + /* Add an entry */ + len = strlen (value); + e = strset_malloc (sizeof (entry) + len + 1); + if (e) { + /* Value data points past end of entry */ + e->value = ((char*)e) + sizeof (entry); + memcpy (e->value, value, len + 1); + + e->next = NULL; + e->hash = hash; + + *ep = e; + ++set->count; + } + + return ep; +} + +int +strset_has (strset *set, const char *value) +{ + entry **ep; + + assert (set); + + if (!value) + return 0; + + ep = find_entry (set, value, 0); + return ep && *ep ? 1 : 0; +} + +int +strset_add (strset *set, const char *value) +{ + entry **ep; + + assert (set); + + if (!value) + return -1; + + ep = find_entry (set, value, 1); + if (!ep || !*ep) + return -1; + + if (set->count > set->max) + if (!expand_array (set)) + return -1; + + return 0; +} + +int +strset_remove (strset *set, const char* value) +{ + entry **ep, *old; + + assert (set); + + if (!value) + return -1; + + ep = find_entry (set, value, 0); + if (!ep || !*ep) + return -1; + + old = *ep; + *ep = (*ep)->next; + --set->count; + strset_free (old); + return 0; +} + +unsigned int +strset_size (strset *set) +{ + assert (set); + return set->count; +} -- cgit v1.2.3