[PATCH libdrm 2/9] tests/hash: extract test out of xf86drmHash.c
On Sun, 2015-03-22 at 22:03 +, Emil Velikov wrote:
> This way with follow up commits we can fix it and wire it up to
> make check
>
> Signed-off-by: Emil Velikov
> ---
> tests/Makefile.am | 3 +-
> tests/hash.c | 219
> ++
> xf86drmHash.c | 174 +++
> 3 files changed, 231 insertions(+), 165 deletions(-)
> create mode 100644 tests/hash.c
>
> diff --git a/tests/Makefile.am b/tests/Makefile.am
> index 10f54e3..ea826b5 100644
> --- a/tests/Makefile.am
> +++ b/tests/Makefile.am
> @@ -29,7 +29,8 @@ LDADD = $(top_builddir)/libdrm.la
>
> check_PROGRAMS = \
> dristat \
> - drmstat
> + drmstat \
> + hash
>
> if HAVE_NOUVEAU
> SUBDIRS += nouveau
> diff --git a/tests/hash.c b/tests/hash.c
> new file mode 100644
> index 000..d57d2dc
> --- /dev/null
> +++ b/tests/hash.c
> @@ -0,0 +1,219 @@
> +/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
> + * Created: Sun Apr 18 09:35:45 1999 by faith at precisioninsight.com
> + *
> + * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
> + * All Rights Reserved.
> + *
> + * 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
> + * PRECISION INSIGHT AND/OR ITS SUPPLIERS 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: Rickard E. (Rik) Faith
> + *
> + * DESCRIPTION
> + *
> + * This file contains a straightforward implementation of a fixed-sized
> + * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
> + * collision resolution. There are two potentially interesting things
> + * about this implementation:
> + *
> + * 1) The table is power-of-two sized. Prime sized tables are more
> + * traditional, but do not have a significant advantage over power-of-two
> + * sized table, especially when double hashing is not used for collision
> + * resolution.
> + *
> + * 2) The hash computation uses a table of random integers [Hanson97,
> + * pp. 39-41].
> + *
> + * FUTURE ENHANCEMENTS
> + *
> + * With a table size of 512, the current implementation is sufficient for a
> + * few hundred keys. Since this is well above the expected size of the
> + * tables for which this implementation was designed, the implementation of
> + * dynamic hash tables was postponed until the need arises. A common (and
> + * naive) approach to dynamic hash table implementation simply creates a
> + * new hash table when necessary, rehashes all the data into the new table,
> + * and destroys the old table. The approach in [Larson88] is superior in
> + * two ways: 1) only a portion of the table is expanded when needed,
> + * distributing the expansion cost over several insertions, and 2) portions
> + * of the table can be locked, enabling a scalable thread-safe
> + * implementation.
> + *
> + * REFERENCES
> + *
> + * [Hanson97] David R. Hanson. C Interfaces and Implementations:
> + * Techniques for Creating Reusable Software. Reading, Massachusetts:
> + * Addison-Wesley, 1997.
> + *
> + * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3:
> + * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973.
> + *
> + * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April
> + * 1988, pp. 446-457.
> + *
> + */
> +
> +#include
> +#include
> +
> +#include "xf86drm.h"
> +
> +#define HASH_SIZE 512 /* Good for about 100 entries */
> + /* If you change this value, you probably
> + have to change the HashHash hashing
> + function! */
> +
> +typedef struct HashBucket {
> +unsigned long key;
> +void *value;
> +struct HashBucket *next;
> +} HashBucket, *HashBucketPtr;
> +
> +typedef struct HashTable {
> +unsigned longmagic;
> +unsigned longentries;
> +unsigned longhits; /* At top of linked list */
> +
[PATCH libdrm 2/9] tests/hash: extract test out of xf86drmHash.c
This way with follow up commits we can fix it and wire it up to
make check
Signed-off-by: Emil Velikov
---
tests/Makefile.am | 3 +-
tests/hash.c | 219 ++
xf86drmHash.c | 174 +++
3 files changed, 231 insertions(+), 165 deletions(-)
create mode 100644 tests/hash.c
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 10f54e3..ea826b5 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -29,7 +29,8 @@ LDADD = $(top_builddir)/libdrm.la
check_PROGRAMS = \
dristat \
- drmstat
+ drmstat \
+ hash
if HAVE_NOUVEAU
SUBDIRS += nouveau
diff --git a/tests/hash.c b/tests/hash.c
new file mode 100644
index 000..d57d2dc
--- /dev/null
+++ b/tests/hash.c
@@ -0,0 +1,219 @@
+/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
+ * Created: Sun Apr 18 09:35:45 1999 by faith at precisioninsight.com
+ *
+ * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
+ * All Rights Reserved.
+ *
+ * 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
+ * PRECISION INSIGHT AND/OR ITS SUPPLIERS 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: Rickard E. (Rik) Faith
+ *
+ * DESCRIPTION
+ *
+ * This file contains a straightforward implementation of a fixed-sized
+ * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
+ * collision resolution. There are two potentially interesting things
+ * about this implementation:
+ *
+ * 1) The table is power-of-two sized. Prime sized tables are more
+ * traditional, but do not have a significant advantage over power-of-two
+ * sized table, especially when double hashing is not used for collision
+ * resolution.
+ *
+ * 2) The hash computation uses a table of random integers [Hanson97,
+ * pp. 39-41].
+ *
+ * FUTURE ENHANCEMENTS
+ *
+ * With a table size of 512, the current implementation is sufficient for a
+ * few hundred keys. Since this is well above the expected size of the
+ * tables for which this implementation was designed, the implementation of
+ * dynamic hash tables was postponed until the need arises. A common (and
+ * naive) approach to dynamic hash table implementation simply creates a
+ * new hash table when necessary, rehashes all the data into the new table,
+ * and destroys the old table. The approach in [Larson88] is superior in
+ * two ways: 1) only a portion of the table is expanded when needed,
+ * distributing the expansion cost over several insertions, and 2) portions
+ * of the table can be locked, enabling a scalable thread-safe
+ * implementation.
+ *
+ * REFERENCES
+ *
+ * [Hanson97] David R. Hanson. C Interfaces and Implementations:
+ * Techniques for Creating Reusable Software. Reading, Massachusetts:
+ * Addison-Wesley, 1997.
+ *
+ * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3:
+ * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973.
+ *
+ * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April
+ * 1988, pp. 446-457.
+ *
+ */
+
+#include
+#include
+
+#include "xf86drm.h"
+
+#define HASH_SIZE 512 /* Good for about 100 entries */
+ /* If you change this value, you probably
+ have to change the HashHash hashing
+ function! */
+
+typedef struct HashBucket {
+unsigned long key;
+void *value;
+struct HashBucket *next;
+} HashBucket, *HashBucketPtr;
+
+typedef struct HashTable {
+unsigned longmagic;
+unsigned longentries;
+unsigned longhits; /* At top of linked list */
+unsigned longpartials; /* Not at top of linked list */
+unsigned longmisses; /* Not in table */
+HashBucketPtrbuckets[HASH_SIZE];
+int p0;
+HashBucketPtrp1;
+} HashTable, *HashTablePtr;
+
+#define DIST_LIMIT 10
+static int dist[DIST_LIMIT];
+
+static void
