--- /dev/null
+#ifndef JSW_H
+#define JSW_H
+
+/*
+ Andersson tree library
+
+ > Created (Julienne Walker): September 10, 2005
+
+ AVL balanced tree library
+
+ > Created (Julienne Walker): June 17, 2003
+ > Modified (Julienne Walker): September 24, 2005
+
+ Hash table library using separate chaining
+
+ > Created (Julienne Walker): August 7, 2005
+ > Modified (Julienne Walker): August 11, 2005
+
+ Red Black balanced tree library
+
+ > Created (Julienne Walker): August 23, 2003
+ > Modified (Julienne Walker): March 14, 2008
+
+ This code is in the public domain. Anyone may
+ use it or change it in any way that they see
+ fit. The author assumes no responsibility for
+ damages incurred through use of the original
+ code or any variations thereof.
+
+ It is requested, but not required, that due
+ credit is given to the original author and
+ anyone who has modified the code through
+ a header comment, such as this one.
+*/
+
+/* code modified for inclusion in zpm */
+
+#include <stddef.h>
+
+/* User-defined item handling */
+typedef int (*cmp_f) ( const void *p1, const void *p2 );
+typedef void *(*dup_f) ( void *p );
+typedef void (*rel_f) ( void *p );
+
+/*
+ * Andersson tree
+ */
+
+/* Opaque types */
+typedef struct jsw_atree jsw_atree_t;
+typedef struct jsw_atrav jsw_atrav_t;
+
+/* Andersson tree functions */
+jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel );
+void jsw_adelete ( jsw_atree_t *tree );
+void *jsw_afind ( jsw_atree_t *tree, void *data );
+int jsw_ainsert ( jsw_atree_t *tree, void *data );
+int jsw_aerase ( jsw_atree_t *tree, void *data );
+size_t jsw_asize ( jsw_atree_t *tree );
+
+/* Traversal functions */
+jsw_atrav_t *jsw_atnew ( void );
+void jsw_atdelete ( jsw_atrav_t *trav );
+void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree );
+void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree );
+void *jsw_atnext ( jsw_atrav_t *trav );
+void *jsw_atprev ( jsw_atrav_t *trav );
+
+/*
+ * AVL tree
+ */
+
+/* Opaque types */
+typedef struct jsw_avltree jsw_avltree_t;
+typedef struct jsw_avltrav jsw_avltrav_t;
+
+/* AVL tree functions */
+jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel );
+void jsw_avldelete ( jsw_avltree_t *tree );
+void *jsw_avlfind ( jsw_avltree_t *tree, void *data );
+int jsw_avlinsert ( jsw_avltree_t *tree, void *data );
+int jsw_avlerase ( jsw_avltree_t *tree, void *data );
+size_t jsw_avlsize ( jsw_avltree_t *tree );
+
+/* Traversal functions */
+jsw_avltrav_t *jsw_avltnew ( void );
+void jsw_avltdelete ( jsw_avltrav_t *trav );
+void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
+void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree );
+void *jsw_avltnext ( jsw_avltrav_t *trav );
+void *jsw_avltprev ( jsw_avltrav_t *trav );
+
+/*
+ * hash table
+ */
+
+typedef struct jsw_hash jsw_hash_t;
+
+/* Application specific hash function */
+typedef unsigned (*hash_f) ( const void *key );
+
+/* Application specific key copying function */
+typedef void *(*keydup_f) ( const void *key );
+
+/* Application specific data copying function */
+typedef void *(*itemdup_f) ( const void *item );
+
+/* Application specific key deletion function */
+typedef void (*keyrel_f) ( void *key );
+
+/* Application specific data deletion function */
+typedef void (*itemrel_f) ( void *item );
+
+typedef struct jsw_hstat {
+ double load; /* Table load factor: (M chains)/(table size) */
+ double achain; /* Average chain length */
+ size_t lchain; /* Longest chain */
+ size_t schain; /* Shortest non-empty chain */
+} jsw_hstat_t;
+
+/*
+ Create a new hash table with a capacity of size, and
+ user defined functions for handling keys and items.
+
+ Returns: An empty hash table, or NULL on failure.
+*/
+jsw_hash_t *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
+ keydup_f keydup, itemdup_f itemdup,
+ keyrel_f keyrel, itemrel_f itemrel );
+
+/* Release all memory used by the hash table */
+void jsw_hdelete ( jsw_hash_t *htab );
+
+/*
+ Find an item with the selected key
+
+ Returns: The item, or NULL if not found
+*/
+void *jsw_hfind ( jsw_hash_t *htab, void *key );
+
+/*
+ Insert an item with the selected key
+
+ Returns: non-zero for success, zero for failure
+*/
+int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item );
+
+/*
+ Remove an item with the selected key
+
+ Returns: non-zero for success, zero for failure
+*/
+int jsw_herase ( jsw_hash_t *htab, void *key );
+
+/*
+ Grow or shrink the table, this is a slow operation
+
+ Returns: non-zero for success, zero for failure
+*/
+int jsw_hresize ( jsw_hash_t *htab, size_t new_size );
+
+/* Reset the traversal markers to the beginning */
+void jsw_hreset ( jsw_hash_t *htab );
+
+/* Traverse forward by one key */
+int jsw_hnext ( jsw_hash_t *htab );
+
+/* Get the current key */
+const void *jsw_hkey ( jsw_hash_t *htab );
+
+/* Get the current item */
+void *jsw_hitem ( jsw_hash_t *htab );
+
+/* Current number of items in the table */
+size_t jsw_hsize ( jsw_hash_t *htab );
+
+/* Total allowable number of items without resizing */
+size_t jsw_hcapacity ( jsw_hash_t *htab );
+
+/* Get statistics for the hash table */
+jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab );
+
+/*
+ * red black tree
+ */
+
+/* Opaque types */
+typedef struct jsw_rbtree jsw_rbtree_t;
+typedef struct jsw_rbtrav jsw_rbtrav_t;
+
+/* Red Black tree functions */
+jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel );
+void jsw_rbdelete ( jsw_rbtree_t *tree );
+void *jsw_rbfind ( jsw_rbtree_t *tree, void *data );
+int jsw_rbinsert ( jsw_rbtree_t *tree, void *data );
+int jsw_rberase ( jsw_rbtree_t *tree, void *data );
+size_t jsw_rbsize ( jsw_rbtree_t *tree );
+
+/* Traversal functions */
+jsw_rbtrav_t *jsw_rbtnew ( void );
+void jsw_rbtdelete ( jsw_rbtrav_t *trav );
+void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
+void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree );
+void *jsw_rbtnext ( jsw_rbtrav_t *trav );
+void *jsw_rbtprev ( jsw_rbtrav_t *trav );
+
+#endif
projects / zpackage / commitdiff