diff options
author | Carl Worth <cworth@cworth.org> | 2013-10-24 15:02:53 -0700 |
---|---|---|
committer | Eric Anholt <eric@anholt.net> | 2013-10-25 15:17:59 -0700 |
commit | f9d22af764336897158a3477ab648a5bdaa26cf2 (patch) | |
tree | 5ef8e1fccfb0a46d50faa5933c209b14c9fdf4e2 | |
parent | dd09488648767bcda8d75f417baca1f7b7940ff1 (diff) |
Add a new int-set structure for a set of integers
Much like the motivation for the original set.c, this int-set.c code
is not difficult, but it makes sense to do this up-front in the
original hash_table module (with testing) rather than expecting users
to repeat this work.
-rw-r--r-- | Makefile.am | 5 | ||||
-rw-r--r-- | configure.ac | 1 | ||||
-rw-r--r-- | int-set.c | 316 | ||||
-rw-r--r-- | int-set.h | 75 | ||||
-rw-r--r-- | tests/Makefile.am | 2 | ||||
-rw-r--r-- | tests/int-set/.gitignore | 11 | ||||
-rw-r--r-- | tests/int-set/Makefile.am | 36 | ||||
-rw-r--r-- | tests/int-set/delete_and_lookup.c | 69 | ||||
-rw-r--r-- | tests/int-set/delete_management.c | 74 | ||||
-rw-r--r-- | tests/int-set/insert_and_lookup.c | 56 | ||||
-rw-r--r-- | tests/int-set/insert_many.c | 58 | ||||
-rw-r--r-- | tests/int-set/null_destroy.c | 38 | ||||
-rw-r--r-- | tests/int-set/null_remove.c | 46 | ||||
-rw-r--r-- | tests/int-set/random_entry.c | 74 | ||||
-rw-r--r-- | tests/int-set/replacement.c | 58 |
15 files changed, 918 insertions, 1 deletions
diff --git a/Makefile.am b/Makefile.am index 3b0348b..8447583 100644 --- a/Makefile.am +++ b/Makefile.am @@ -27,6 +27,7 @@ AM_CFLAGS = $(WARN_CFLAGS) noinst_LTLIBRARIES = \ libhash_table.la \ + libint-set.la \ libset.la libhash_table_la_SOURCES = \ @@ -35,6 +36,10 @@ libhash_table_la_SOURCES = \ hash_table.c \ hash_table.h +libint_set_la_SOURCES = \ + int-set.c \ + int-set.h + libset_la_SOURCES = \ fnv_hash.c \ fnv_hash.h \ diff --git a/configure.ac b/configure.ac index de6ee3d..82a19b5 100644 --- a/configure.ac +++ b/configure.ac @@ -51,4 +51,5 @@ AC_OUTPUT([ Makefile tests/Makefile tests/set/Makefile + tests/int-set/Makefile ]) diff --git a/int-set.c b/int-set.c new file mode 100644 index 0000000..9e03243 --- /dev/null +++ b/int-set.c @@ -0,0 +1,316 @@ +/* + * Copyright © 2009,2013 Intel Corporation + * Copyright © 1988-2004 Keith Packard and Bart Massey. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Except as contained in this notice, the names of the authors + * or their institutions shall not be used in advertising or + * otherwise to promote the sale, use or other dealings in this + * Software without prior written authorization from the + * authors. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * Keith Packard <keithp@keithp.com> + * Carl Worth <cworth@cworth.org> + */ + +#include <stdlib.h> + +#include "int-set.h" + +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) + +/* + * From Knuth -- a good choice for hash/rehash values is p, p-2 where + * p and p-2 are both prime. These tables are sized to have an extra 10% + * free to avoid exponential performance degradation as the hash table fills + */ + +static const struct { + uint32_t max_entries, size, rehash; +} hash_sizes[] = { + { 2, 5, 3 }, + { 4, 7, 5 }, + { 8, 13, 11 }, + { 16, 19, 17 }, + { 32, 43, 41 }, + { 64, 73, 71 }, + { 128, 151, 149 }, + { 256, 283, 281 }, + { 512, 571, 569 }, + { 1024, 1153, 1151 }, + { 2048, 2269, 2267 }, + { 4096, 4519, 4517 }, + { 8192, 9013, 9011 }, + { 16384, 18043, 18041 }, + { 32768, 36109, 36107 }, + { 65536, 72091, 72089 }, + { 131072, 144409, 144407 }, + { 262144, 288361, 288359 }, + { 524288, 576883, 576881 }, + { 1048576, 1153459, 1153457 }, + { 2097152, 2307163, 2307161 }, + { 4194304, 4613893, 4613891 }, + { 8388608, 9227641, 9227639 }, + { 16777216, 18455029, 18455027 }, + { 33554432, 36911011, 36911009 }, + { 67108864, 73819861, 73819859 }, + { 134217728, 147639589, 147639587 }, + { 268435456, 295279081, 295279079 }, + { 536870912, 590559793, 590559791 }, + { 1073741824, 1181116273, 1181116271}, + { 2147483648ul, 2362232233ul, 2362232231ul} +}; + +static int +entry_is_free(struct int_set_entry *entry) +{ + return ! entry->occupied; +} + +static int +entry_is_deleted(struct int_set_entry *entry) +{ + return entry->deleted; +} + +static int +entry_is_present(struct int_set_entry *entry) +{ + return entry->occupied && ! entry->deleted; +} + +struct int_set * +int_set_create(void) +{ + struct int_set *set; + + set = malloc(sizeof(*set)); + if (set == NULL) + return NULL; + + set->size_index = 0; + set->size = hash_sizes[set->size_index].size; + set->rehash = hash_sizes[set->size_index].rehash; + set->max_entries = hash_sizes[set->size_index].max_entries; + set->table = calloc(set->size, sizeof(*set->table)); + set->entries = 0; + set->deleted_entries = 0; + + if (set->table == NULL) { + free(set); + return NULL; + } + + return set; +} + +/** + * Frees the given set. + */ +void +int_set_destroy(struct int_set *set) +{ + if (!set) + return; + + free(set->table); + free(set); +} + +/** + * Finds a set entry with the given value + * + * Returns NULL if no entry is found. + */ +struct int_set_entry * +int_set_search(struct int_set *set, uint32_t value) +{ + uint32_t hash_address; + + hash_address = value % set->size; + do { + uint32_t double_hash; + + struct int_set_entry *entry = set->table + hash_address; + + if (entry_is_free(entry)) { + return NULL; + } else if (entry_is_present(entry) && entry->value == value) { + return entry; + } + + double_hash = 1 + value % set->rehash; + + hash_address = (hash_address + double_hash) % set->size; + } while (hash_address != value % set->size); + + return NULL; +} + +static void +int_set_rehash(struct int_set *set, int new_size_index) +{ + struct int_set old_set; + struct int_set_entry *table, *entry; + + if (new_size_index >= ARRAY_SIZE(hash_sizes)) + return; + + table = calloc(hash_sizes[new_size_index].size, sizeof(*set->table)); + if (table == NULL) + return; + + old_set = *set; + + set->table = table; + set->size_index = new_size_index; + set->size = hash_sizes[set->size_index].size; + set->rehash = hash_sizes[set->size_index].rehash; + set->max_entries = hash_sizes[set->size_index].max_entries; + set->entries = 0; + set->deleted_entries = 0; + + for (entry = old_set.table; + entry != old_set.table + old_set.size; + entry++) { + if (entry_is_present(entry)) { + int_set_add(set, entry->value); + } + } + + free(old_set.table); +} + +/** + * Inserts the given value into the set. + * + * Note that insertion may rearrange the table on a resize or rehash, + * so previously found int_set_entry pointers are no longer valid + * after this function. + */ +struct int_set_entry * +int_set_add(struct int_set *set, uint32_t value) +{ + uint32_t hash_address; + + if (set->entries >= set->max_entries) { + int_set_rehash(set, set->size_index + 1); + } else if (set->deleted_entries + set->entries >= set->max_entries) { + int_set_rehash(set, set->size_index); + } + + hash_address = value % set->size; + do { + struct int_set_entry *entry = set->table + hash_address; + uint32_t double_hash; + + if (!entry_is_present(entry)) { + if (entry_is_deleted(entry)) + set->deleted_entries--; + entry->value = value; + entry->occupied = 1; + set->entries++; + return entry; + } + + if (entry->value == value) { + return entry; + } + + double_hash = 1 + value % set->rehash; + + hash_address = (hash_address + double_hash) % set->size; + } while (hash_address != value % set->size); + + /* We could hit here if a required resize failed. An unchecked-malloc + * application could ignore this result. + */ + return NULL; +} + +/** + * This function deletes the given set entry. + * + * Note that deletion doesn't otherwise modify the table, so an iteration over + * the table deleting entries is safe. + */ +void +int_set_remove(struct int_set *set, struct int_set_entry *entry) +{ + if (!entry) + return; + + entry->deleted = 1; + set->entries--; + set->deleted_entries++; +} + +/** + * This function is an iterator over the set. + * + * Pass in NULL for the first entry, as in the start of a for loop. Note that + * an iteration over the table is O(table_size) not O(entries). + */ +struct int_set_entry * +int_set_next_entry(struct int_set *set, struct int_set_entry *entry) +{ + if (entry == NULL) + entry = set->table; + else + entry = entry + 1; + + for (; entry != set->table + set->size; entry++) { + if (entry_is_present(entry)) { + return entry; + } + } + + return NULL; +} + +struct int_set_entry * +int_set_random_entry(struct int_set *set, + int (*predicate)(struct int_set_entry *entry)) +{ + struct int_set_entry *entry; + uint32_t i = random() % set->size; + + if (set->entries == 0) + return NULL; + + for (entry = set->table + i; entry != set->table + set->size; entry++) { + if (entry_is_present(entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + for (entry = set->table; entry != set->table + i; entry++) { + if (entry_is_present(entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + return NULL; +} diff --git a/int-set.h b/int-set.h new file mode 100644 index 0000000..62b6740 --- /dev/null +++ b/int-set.h @@ -0,0 +1,75 @@ +/* + * Copyright © 2009,2013 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * + */ + +#ifndef SET_H +#define SET_H + +#include <inttypes.h> + +struct int_set_entry { + uint32_t value; + unsigned int occupied : 1; + unsigned int deleted : 1; +}; + +struct int_set { + struct int_set_entry *table; + uint32_t size; + uint32_t rehash; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +struct int_set * +int_set_create(void); + +void +int_set_destroy(struct int_set *set); + +struct int_set_entry * +int_set_add(struct int_set *set, uint32_t value); + +struct int_set_entry * +int_set_search(struct int_set *set, uint32_t value); + +void +int_set_remove(struct int_set *set, struct int_set_entry *entry); + +struct int_set_entry * +int_set_next_entry(struct int_set *set, struct int_set_entry *entry); + +/* Return a random entry in the set that satisfies predicate. + * + * The 'predicate' function pointer may be NULL in which any random + * entry will be returned. */ +struct int_set_entry * +int_set_random_entry(struct int_set *set, + int (*predicate)(struct int_set_entry *entry)); + +#endif diff --git a/tests/Makefile.am b/tests/Makefile.am index edffe40..f280ee3 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -19,7 +19,7 @@ # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS # IN THE SOFTWARE. -SUBDIRS = set +SUBDIRS = set int-set AM_CFLAGS = $(WARN_CFLAGS) -I.. LDADD = ../libhash_table.la diff --git a/tests/int-set/.gitignore b/tests/int-set/.gitignore new file mode 100644 index 0000000..2aeb095 --- /dev/null +++ b/tests/int-set/.gitignore @@ -0,0 +1,11 @@ +*.log +*.trs +delete_and_lookup +delete_management +destroy_callback +insert_and_lookup +insert_many +null_destroy +null_remove +random_entry +replacement diff --git a/tests/int-set/Makefile.am b/tests/int-set/Makefile.am new file mode 100644 index 0000000..23c1e5b --- /dev/null +++ b/tests/int-set/Makefile.am @@ -0,0 +1,36 @@ +# Copyright © 2009 Intel Corporation +# +# Permission is hereby granted, free of charge, to any person obtaining a +# copy of this software and associated documentation files (the "Software"), +# to deal in the Software without restriction, including without limitation +# the rights to use, copy, modify, merge, publish, distribute, sublicense, +# and/or sell copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice (including the next +# paragraph) shall be included in all copies or substantial portions of the +# Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +# IN THE SOFTWARE. + +AM_CFLAGS = $(WARN_CFLAGS) -I../.. +LDADD = ../../libint-set.la + +TESTS = \ + delete_and_lookup \ + delete_management \ + insert_and_lookup \ + insert_many \ + null_destroy \ + null_remove \ + random_entry \ + replacement \ + $() + +EXTRA_PROGRAMS = $(TESTS) diff --git a/tests/int-set/delete_and_lookup.c b/tests/int-set/delete_and_lookup.c new file mode 100644 index 0000000..8810b5a --- /dev/null +++ b/tests/int-set/delete_and_lookup.c @@ -0,0 +1,69 @@ +/* + * Copyright © 2009,2013 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * Carl Worth <cworth@cworth.org> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + + /* Use two values with the lowest bits in common so they will + * hash to the same initial entry, so we can test the deletion + * behavior for chained objects. */ + uint32_t value1 = 0x00000123; + uint32_t value2 = 0x10000123; + struct int_set_entry *entry; + + set = int_set_create(); + + int_set_add(set, value1); + int_set_add(set, value2); + + entry = int_set_search(set, value1); + assert(entry->value == value1); + + entry = int_set_search(set, value2); + assert(entry->value == value2); + + int_set_remove(set, entry); + + entry = int_set_search(set, value2); + assert(entry == NULL); + + entry = int_set_search(set, value1); + assert(entry->value == value1); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/delete_management.c b/tests/int-set/delete_management.c new file mode 100644 index 0000000..cc0ea9d --- /dev/null +++ b/tests/int-set/delete_management.c @@ -0,0 +1,74 @@ +/* + * Copyright © 2009 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + struct int_set_entry *entry; + int size = 10000; + uint32_t keys[size]; + uint32_t i; + + set = int_set_create(); + + for (i = 0; i < size; i++) { + int_set_add(set, i); + + if (i >= 100) { + uint32_t delete_value = i - 100; + entry = int_set_search(set, delete_value); + int_set_remove(set, entry); + } + } + + /* Make sure that all our entries were present at the end. */ + for (i = size - 100; i < size; i++) { + entry = int_set_search(set, i); + assert(entry); + assert(entry->value == i); + } + + /* Make sure that no extra entries got in */ + for (entry = int_set_next_entry(set, NULL); + entry != NULL; + entry = int_set_next_entry(set, entry)) { + assert(entry->value >= size - 100 && + entry->value < size); + } + assert(set->entries == 100); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/insert_and_lookup.c b/tests/int-set/insert_and_lookup.c new file mode 100644 index 0000000..575aac7 --- /dev/null +++ b/tests/int-set/insert_and_lookup.c @@ -0,0 +1,56 @@ +/* + * Copyright © 2009 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + uint32_t value1 = 0x14b5fbc8; + uint32_t value2 = 0x5303d1ff; + struct int_set_entry *entry; + + set = int_set_create(); + + int_set_add(set, value1); + int_set_add(set, value2); + + entry = int_set_search(set, value1); + assert(entry->value == value1); + + entry = int_set_search(set, value2); + assert(entry->value == value2); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/insert_many.c b/tests/int-set/insert_many.c new file mode 100644 index 0000000..99ad9ea --- /dev/null +++ b/tests/int-set/insert_many.c @@ -0,0 +1,58 @@ +/* + * Copyright © 2009 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + struct int_set_entry *entry; + int size = 1; + uint32_t i; + + set = int_set_create(); + + for (i = 0; i < size; i++) { + int_set_add(set, i); + } + + for (i = 0; i < size; i++) { + entry = int_set_search(set, i); + assert(entry); + assert(entry->value == i); + } + assert(set->entries == size); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/null_destroy.c b/tests/int-set/null_destroy.c new file mode 100644 index 0000000..09e1aea --- /dev/null +++ b/tests/int-set/null_destroy.c @@ -0,0 +1,38 @@ +/* + * Copyright © 2009 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + int_set_destroy(NULL); + + return 0; +} diff --git a/tests/int-set/null_remove.c b/tests/int-set/null_remove.c new file mode 100644 index 0000000..318c570 --- /dev/null +++ b/tests/int-set/null_remove.c @@ -0,0 +1,46 @@ +/* + * Copyright © 2011 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + + set = int_set_create(); + + int_set_remove(set, NULL); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/random_entry.c b/tests/int-set/random_entry.c new file mode 100644 index 0000000..204595e --- /dev/null +++ b/tests/int-set/random_entry.c @@ -0,0 +1,74 @@ +/* + * Copyrigset © 2009 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rigsets to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyrigset notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGSET HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +static int +uint32_t_key_is_even(struct int_set_entry *entry) +{ + return (entry->value & 1) == 0; +} + +int +main(int argc, char **argv) +{ + struct int_set *set; + struct int_set_entry *entry; + int size = 10000; + uint32_t i, random_value = 0; + + set = int_set_create(); + + for (i = 0; i < size; i++) { + int_set_add(set, i); + } + + /* Test the no-predicate case. */ + entry = int_set_random_entry(set, NULL); + assert(entry); + + /* Check that we're getting different entries and that the predicate + * works. + */ + for (i = 0; i < 100; i++) { + entry = int_set_random_entry(set, uint32_t_key_is_even); + assert(entry); + assert((entry->value & 1)== 0); + if (i == 0 || entry->value != random_value) + break; + random_value = entry->value; + } + assert(i != 100); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/int-set/replacement.c b/tests/int-set/replacement.c new file mode 100644 index 0000000..71436bb --- /dev/null +++ b/tests/int-set/replacement.c @@ -0,0 +1,58 @@ +/* + * Copyright © 2011 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +#include "int-set.h" + +int +main(int argc, char **argv) +{ + struct int_set *set; + uint32_t value = 0x11f9feca; + struct int_set_entry *entry; + + set = int_set_create(); + + int_set_add(set, value); + int_set_add(set, value); + + entry = int_set_search(set, value); + assert(entry); + assert(entry->value == value); + + int_set_remove(set, entry); + + entry = int_set_search(set, value); + assert(!entry); + + int_set_destroy(set); + + return 0; +} |