Re: [pdf-devel] Hash module API

[gerel]

 > Date: Tue, 08 Apr 2008 18:58:25 +0200
 > From: address@hidden
 > 
 > 
 > Sorry. The hash function I was thinking about is in the hash-pjw
 > module in the gnulib:
 > 
 > /* Compute a hash code for a NUL-terminated string starting at X,
 >    and return the hash code modulo TABLESIZE.
 >    The result is platform dependent: it depends on the size of the 'size_t'
 >    type and on the signedness of the 'char' type.  */
 > extern size_t hash_pjw (void const *x, size_t tablesize);
 > 

Perfect.

 > And it is inspired in a method described by Bruno Haible:
 > http://www.haible.de/bruno/hashfunc.html 
 > 
 > So if needed would not be hard to write our own version if to use
 > hash_pjw with gl_listelement_hashcode_fn proves to be problematic.

I think It won't be problematic.


Now, I'll send the patch for the final Hash Module API that I'm planing to
implement.
A question first. Regarding "pdf_hash_iterator_next()" that is supposed to
return each key of a hash table, do you think we should keep track of each
string key and free() them when "pdf_hash_iterator_free()" is called or leave
the user that job. It is a memory used over complexity trade-off.

Patch,

##

Index: doc/gnupdf.texi
===================================================================
RCS file: /sources/pdf/libgnupdf/doc/gnupdf.texi,v
retrieving revision 1.40
diff -u -r1.40 gnupdf.texi
--- doc/gnupdf.texi     8 Apr 2008 10:21:29 -0000       1.40
+++ doc/gnupdf.texi     9 Apr 2008 21:03:03 -0000
@@ -888,36 +888,351 @@
 @menu
 * Hash Table Types::
 * Creating and Destroying Hash Tables::
+* Hash Table properties::
+* Working with keys::
+* Adding and removing elements::
+* Searching elements::
+* Working with iterators::
 @end menu
 
 @node Hash Table Types
 @subsection Hash Table Types
 
address@hidden {Data Type} {enum pdf_hash_value_type_e}
-
-Enumeration of supported value types in a hash variable:
-
address@hidden @code
address@hidden PDF_HASH_VAL_BOOL
address@hidden PDF_HASH_VAL_U32
address@hidden PDF_HASH_VAL_I32
address@hidden PDF_HASH_VAL_REAL
address@hidden PDF_HASH_VAL_STR
address@hidden PDF_HASH_VAL_TEXT
address@hidden PDF_HASH_VAL_HASH
address@hidden PDF_HASH_VAL_LIST
address@hidden table
address@hidden deftp
-
 @deftp {Data Type} pdf_hash_t
 
 A Hash Table able to store key/value pairs. A key may be any
 NULL-terminated string.
 @end deftp
 
address@hidden {Data Type} pdf_hash_iterator_t
+
+An iterator over the keys of a Hash Table.
address@hidden deftp
+
+
 @node Creating and Destroying Hash Tables
 @subsection Creating and Destroying Hash Tables
 
address@hidden pdf_status_t pdf_hash_create (pdf_hash_dispose_fn_t 
@var{dispose_fn}, pdf_hash_t @var{*table})
+
+Create a new empty hash table. When some element is removed @var{dispose_fn} 
is called. Can be NULL.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden dispose_fn
+A pointer to a hash table dispose function.
address@hidden table
+A pointer to a hash table.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_ENOMEM
+Not enough memory.
address@hidden PDF_EBADDATA
+Invalid @var{table} pointer.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden pdf_status_t pdf_hash_destroy (pdf_hash_t @var{table})
+
+Destroy a hash table. The elements of the table are disposed first.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
+
+
address@hidden Hash Table properties
address@hidden Hash Table properties
+
address@hidden pdf_size_t pdf_hash_size (pdf_hash_t @var{table})
+
+Returns the number of entries in @var{table}.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden table
address@hidden Returns
+The number of entries.
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden Working with keys
address@hidden Working with keys
+
address@hidden pdf_bool_t pdf_hash_key_p (pdf_hash_t @var{table}, const char 
address@hidden)
+
+Returns a boolean value indicating whether an element with key @var{key} 
exists in @var{table}.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden key
+A valid key string.
address@hidden table
address@hidden Returns
+A pdf boolean value:
address@hidden @code
address@hidden PDF_TRUE
+An element associated with @var{key} exists.
address@hidden PDF_FALSE
+There is no element associated with @var{key}.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden pdf_status_t pdf_hash_rename (pdf_hash_t @var{table}, const char 
@var{*key}, const char @var{*new_key})
+
+Renames the key @var{key} to @var{new_key} in @var{table}.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden key
+A valid key string.
address@hidden new_key
+A valid key string.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeded.
address@hidden PDF_ENOMEM
+Not enough memory.
address@hidden PDF_ERROR
+The @var{key} is not associated with any element in @var{table}.
address@hidden PDF_EBADDATA
+Either @var{table} or a key string is invalid or NULL.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden Adding and removing elements
address@hidden Adding and removing elements
+
address@hidden pdf_status_t pdf_hash_add (pdf_hash_t @var{table}, const char 
@var{*key}, void @var{*element}) 
+
+Adds the element @var{element} with the associated key @var{key} to 
@var{table}. If @var{key} already exists nothing is done.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden key
+A valid key string.
address@hidden element
+A pointer to the element being added.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_ENOMEM
+Not enough memory.
address@hidden PDF_EBADDATA
+Either @var{table}, @var{key} or @var{element} is invalid.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden pdf_status_t pdf_hash_remove (pdf_hash_t @var{table}, const char 
@var{*key})
+
+Removes the element associated with @var{key} from @var{table}. The element is 
disposed first.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden key
+A valid key string.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_EBADDATA
+Invalid @var{table} or @var{key}.
address@hidden PDF_ERROR
+The @var{key} wasn't found.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden Searching elements
address@hidden Searching elements
+
address@hidden pdf_status_t pdf_hash_search (pdf_hash_t @var{table}, const char 
@var{*key}, void address@hidden)
+
+Searches for the element associated with the given @var{key} in @var{table} 
and store it in @var{elem_pointer}.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden key
+A valid null-terminated string key.
address@hidden elem_pointer
+A pointer where to store the element.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_EBADDATA
+Either @var{elem_pointer} is NULL, @var{key} or the @var{table} is invalid.
address@hidden PDF_ERROR
+The @var{key} wasn't found.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden Working with iterators
address@hidden Working with iterators
+
address@hidden pdf_status_t pdf_hash_iterator (pdf_hash_t @var{table}, 
pdf_hash_iterator_t @var{*iterator})
+
+Creates an iterator over the keys of @var{table} and saves it in 
@var{iterator}. Keys composed only by numbers are returned first followed by 
keys in the order imposed by the ``strcmp()'' function.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A hash table.
address@hidden iterator
+A pointer to an iterator.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_EBADDATA
+Either @var{iterator} is NULL or @var{table} is invalid.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden pdf_status_t pdf_hash_iterator_next (pdf_hash_iterator_t 
@var{iterator}, const char address@hidden)
+
+Retrieves the next key from @var{iterator}.
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden iterator
+A Hash Table iterator.
address@hidden key
+A pointer where to save the key.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden PDF_EBADDATA
+Either @var{iterator} is invalid or @var{key} is NULL.
address@hidden PDF_ERROR
+There are no more keys to traverse over.
address@hidden PDF_ENOMEM
+Not enough memory.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
address@hidden pdf_status_t pdf_hash_iterator_free (pdf_hash_iterator_t 
@var{iterator})
+
+Free all resources used by @var{iterator}. 
+
address@hidden @strong
address@hidden Parameters
address@hidden @var
address@hidden table
+A Hash Table iterator.
address@hidden table
address@hidden Returns
+A pdf status value:
address@hidden @code
address@hidden PDF_OK
+The operation succeeded.
address@hidden table
address@hidden Usage example
address@hidden
+XXX
address@hidden example
address@hidden table
address@hidden deftypefun
+
 
 @node Lists
 @section Lists


###


cheers

-gerel