util.c File Reference

Generic utilities library. More...

#include "config.h"
#include <stdio.h>
#include <stdlib.h>
#include <wchar.h>
#include <math.h>
#include <sys/time.h>
#include <stdarg.h>
#include <string.h>
#include <ctype.h>
#include <wctype.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <errno.h>
#include <assert.h>
#include "fallback.h"
#include "util.h"
#include "common.h"
#include "wutil.h"

This graph shows which files directly or indirectly include this file:

Defines
#define	MIN_SIZE   32
	Minimum allocated size for data structures.
#define	HASH_MIN_SIZE   7
	Minimum size for hash tables.
#define	SB_MAX_SIZE   32767
	Maximum number of characters that can be inserted using a single call to sb_printf.
#define	oom_handler(p)
#define	WORD_COUNT   16
	The number of words of input used in each lap by the sha-like string hashing algorithm.
Functions
void	util_die_on_oom (void *p)
void(*)(void *)	util_set_oom_handler (void(*h)(void *))
int	mini (int a, int b)
	Returns the smaller of two ints.
int	maxi (int a, int b)
	Returns the larger of two ints.
void	q_init (dyn_queue_t *q)
	Initialize the queue.
void	q_destroy (dyn_queue_t *q)
	Destroy the queue.
static int	q_realloc (dyn_queue_t *q)
	Reallocate the queue_t.
int	q_put (dyn_queue_t *q, void *e)
	Insert element into queue.
void *	q_get (dyn_queue_t *q)
	Remove and return next element from queue.
void *	q_peek (dyn_queue_t *q)
	Return next element from queue without removing it.
int	q_empty (dyn_queue_t *q)
	Returns 1 if the queue is empty, 0 otherwise.
void	hash_init2 (hash_table_t *h, int(*hash_func)(void *key), int(*compare_func)(void *key1, void *key2), size_t capacity)
	Initialize a hash table.
void	hash_init (hash_table_t *h, int(*hash_func)(void *key), int(*compare_func)(void *key1, void *key2))
	Initialize a hash table.
void	hash_destroy (hash_table_t *h)
	Destroy the hash table and free associated memory.
static int	hash_search (hash_table_t *h, void *key)
	Search for the specified hash key in the table.
static int	hash_realloc (hash_table_t *h, int sz)
	Reallocate the hash array.
int	hash_put (hash_table_t *h, const void *key, const void *data)
	Set the key/value pair for the hashtable.
void *	hash_get (hash_table_t *h, const void *key)
	Returns the data with the associated key, or 0 if no such key is in the hashtable.
void *	hash_get_key (hash_table_t *h, const void *key)
	Returns the hash tables version of the specified key.
int	hash_get_count (hash_table_t *h)
	Returns the number of key/data pairs in the table.
void	hash_remove (hash_table_t *h, const void *key, void **old_key, void **old_val)
	Remove the specified key from the hash table if it exists.
int	hash_contains (hash_table_t *h, const void *key)
	Checks whether the specified key is in the hash table.
static void	hash_put_data (void *key, void *data, void *al)
	Push hash value into array_list_t.
void	hash_get_data (hash_table_t *h, array_list_t *arr)
	Appends all data elements in the table to the specified list.
static void	hash_put_key (void *key, void *data, void *al)
	Push hash key into array_list_t.
void	hash_get_keys (hash_table_t *h, array_list_t *arr)
	Appends all keys in the table to the specified list.
void	hash_foreach (hash_table_t *h, void(*func)(void *, void *))
	Call the function func for each key/data pair in the table.
void	hash_foreach2 (hash_table_t *h, void(*func)(void *, void *, void *), void *aux)
	Same as hash_foreach, but the function func takes an additional argument, which is provided by the caller in the variable aux.
static unsigned int	rotl1 (unsigned int in)
	Helper function for hash_wcs_func.
static unsigned int	rotl5 (unsigned int in)
	Helper function for hash_wcs_func.
static unsigned int	rotl30 (unsigned int in)
	Helper function for hash_wcs_func.
int	hash_wcs_func (void *data)
	Hash function suitable for wide character strings.
int	hash_wcs_cmp (void *a, void *b)
	Hash comparison function suitable for wide character strings.
int	hash_str_cmp (void *a, void *b)
	Hash comparison function suitable for character strings.
int	hash_str_func (void *data)
	Hash function suitable for character strings.
int	hash_ptr_func (void *data)
	Hash function suitable for direct pointer comparison.
int	hash_ptr_cmp (void *a, void *b)
	Hash comparison function suitable for direct pointer comparison.
void	pq_init (priority_queue_t *q, int(*compare)(void *e1, void *e2))
	Initialize the priority queue.
int	pq_put (priority_queue_t *q, void *e)
	Add element to the queue.
static void	pq_heapify (priority_queue_t *q, int i)
	Make a valid head.
void *	pq_get (priority_queue_t *q)
	Removes and returns the last entry in the priority queue.
void *	pq_peek (priority_queue_t *q)
	Returns the last entry in the priority queue witout removing it.
int	pq_empty (priority_queue_t *q)
	Returns 1 if the priority queue is empty, 0 otherwise.
int	pq_get_count (priority_queue_t *q)
	Returns the number of elements in the priority queue.
void	pq_destroy (priority_queue_t *q)
	Destroy the priority queue and free memory used by it.
array_list_t *	al_new ()
	Allocate heap memory for creating a new list and initialize it.
void	al_init (array_list_t *l)
	Initialize the list.
void	al_destroy (array_list_t *l)
	Destroy the list and free memory used by it.
static int	al_push_generic (array_list_t *l, anything_t o)
int	al_push (array_list_t *l, const void *o)
	Append element to list.
int	al_push_long (array_list_t *l, long val)
	Append element to list.
int	al_push_func (array_list_t *l, func_ptr_t f)
int	al_push_all (array_list_t *a, array_list_t *b)
	Append all elements of a list to another.
int	al_insert (array_list_t *a, int pos, int count)
static int	al_set_generic (array_list_t *l, int pos, anything_t v)
int	al_set (array_list_t *l, int pos, const void *o)
	Sets the element at the specified index.
int	al_set_long (array_list_t *l, int pos, long o)
	Sets the element at the specified index.
int	al_set_func (array_list_t *l, int pos, func_ptr_t o)
static anything_t	al_get_generic (array_list_t *l, int pos)
void *	al_get (array_list_t *l, int pos)
	Returns the element at the specified index.
long	al_get_long (array_list_t *l, int pos)
	Returns the element at the specified index.
func_ptr_t	al_get_func (array_list_t *l, int pos)
	Returns the element at the specified index.
void	al_truncate (array_list_t *l, int new_sz)
	Truncates the list to new_sz items.
static anything_t	al_pop_generic (array_list_t *l)
void *	al_pop (array_list_t *l)
	Removes and returns the last entry in the list.
long	al_pop_long (array_list_t *l)
	Removes and returns the last entry in the list.
func_ptr_t	al_pop_func (array_list_t *l)
	Removes and returns the last entry in the list.
static anything_t	al_peek_generic (array_list_t *l)
void *	al_peek (array_list_t *l)
	Returns the last entry in the list witout removing it.
long	al_peek_long (array_list_t *l)
	Returns the last entry in the list witout removing it.
func_ptr_t	al_peek_func (array_list_t *l)
	Returns the last entry in the list witout removing it.
int	al_empty (array_list_t *l)
	Returns 1 if the list is empty, 0 otherwise.
int	al_get_count (array_list_t *l)
	Returns the number of elements in the list.
void	al_foreach (array_list_t *l, void(*func)(void *))
	Call the function func for each entry in the list.
void	al_foreach2 (array_list_t *l, void(*func)(void *, void *), void *aux)
	Same as al_foreach, but the function func takes an additional argument, which is provided by the caller in the variable aux.
int	wcsfilecmp (const wchar_t *a, const wchar_t *b)
	Compares two wide character strings with an (arguably) intuitive ordering.
void	sb_init (string_buffer_t *b)
	Initialize the specified string_buffer.
string_buffer_t *	sb_new ()
	Allocate memory for storing a stringbuffer and init it.
void	sb_append_substring (string_buffer_t *b, const wchar_t *s, size_t l)
	Append a part of a string to the buffer.
void	sb_append_char (string_buffer_t *b, wchar_t c)
	Append a character to the buffer.
void	sb_append_internal (string_buffer_t *b,...)
	Append a null terminated list of strings to the buffer.
int	sb_printf (string_buffer_t *buffer, const wchar_t *format,...)
	Append formated string data to the buffer.
int	sb_vprintf (string_buffer_t *buffer, const wchar_t *format, va_list va_orig)
	Vararg version of sb_printf.
void	sb_destroy (string_buffer_t *b)
	Destroy the buffer and free it's memory.
void	sb_clear (string_buffer_t *b)
	Completely truncate the buffer.
void	sb_truncate (string_buffer_t *b, int chars_left)
	Truncate the string to the specified number of characters.
ssize_t	sb_length (string_buffer_t *b)
	Return the number of characters in the string.
void	b_init (buffer_t *b)
	Initialize the specified buffer_t.
void	b_destroy (buffer_t *b)
	Destroy the specified buffer_t.
int	b_append (buffer_t *b, const void *d, ssize_t len)
	Add data of the specified length to the specified buffer_t.
long long	get_time ()
	Get the current time in microseconds since Jan 1, 1970.
Variables
void(*	oom_handler_internal )(void *) = &util_die_on_oom

---

Detailed Description

Generic utilities library.

Contains datastructures such as hash tables, automatically growing array lists, priority queues, etc.

---

Define Documentation

#define MIN_SIZE   32

Minimum allocated size for data structures. Used to avoid excessive memory allocations for lists, hash tables, etc, which are nearly empty.

#define oom_handler (  p   )

Value: { \ if( oom_handler_internal == util_die_on_oom ) \ { \ DIE_MEM(); \ } \ oom_handler_internal( p ); \ } \

#define SB_MAX_SIZE   32767

Maximum number of characters that can be inserted using a single call to sb_printf. This is needed since vswprintf doesn't tell us what went wrong. We don't know if we ran out of space or something else went wrong. Therefore we assume that any error is an out of memory-error and try again until we reach this size.

---

Function Documentation

void* al_get (  array_list_t *  l, int  pos )

Returns the element at the specified index. Parameters: l  The array_list_t pos  The index Returns: The element

func_ptr_t al_get_func (  array_list_t *  l, int  pos )

Returns the element at the specified index. Parameters: l  The array_list_t pos  The index Returns: The element

long al_get_long (  array_list_t *  l, int  pos )

Returns the element at the specified index. Parameters: l  The array_list_t pos  The index Returns: The element

array_list_t* al_new (   )

Allocate heap memory for creating a new list and initialize it. Equivalent to calling malloc and al_init.

int al_push (  array_list_t *  l, const void *  o )

Append element to list. Parameters: l  The list o  The element Returns: 1 if succesfull, 0 otherwise

int al_push_all (  array_list_t *  a, array_list_t *  b )

Append all elements of a list to another. Parameters: a  The destination list b  The source list Returns: 1 if succesfull, 0 otherwise

int al_push_long (  array_list_t *  l, long  o )

Append element to list. Parameters: l  The list o  The element Returns: 1 if succesfull, 0 otherwise

int al_set (  array_list_t *  l, int  pos, const void *  o )

Sets the element at the specified index. Parameters: l  The array_list_t pos  The index o  The element

int al_set_long (  array_list_t *  l, int  pos, long  v )

Sets the element at the specified index. Parameters: l  The array_list_t pos  The index o  The element

int b_append (  buffer_t *  b, const void *  d, ssize_t  len )

Add data of the specified length to the specified buffer_t. Returns: 0 on error, non-zero otherwise

void hash_init (  hash_table_t *  h, int(*)(void *key)  hash_func, int(*)(void *key1, void *key2)  compare_func )

Initialize a hash table. The hash function must never return the value 0.

void hash_init2 (  hash_table_t *  h, int(*)(void *key)  hash_func, int(*)(void *key1, void *key2)  compare_func, size_t  capacity )

Initialize a hash table. The hash function must never return the value 0.

static int hash_realloc (  hash_table_t *  h, int  sz )  [static]

Reallocate the hash array. This is quite expensive, as every single entry has to be rehashed and moved.

void hash_remove (  hash_table_t *  h, const void *  key, void **  old_key, void **  old_data )

Remove the specified key from the hash table if it exists. Do nothing if it does not exist. Parameters: h  The hashtable key  The key old_key  If not 0, a pointer to the old key will be stored at the specified address old_data  If not 0, a pointer to the data will be stored at the specified address

static int hash_search (  hash_table_t *  h, void *  key )  [static]

Search for the specified hash key in the table. Returns: index in the table, or to the first free index if the key is not in the table

int hash_wcs_func (  void *  data  )

Hash function suitable for wide character strings. Uses a version of the sha cryptographic function which is simplified in order to returns a 32-bit number.

void pq_init (  priority_queue_t *  q, int(*)(void *e1, void *e2)  compare )

Initialize the priority queue. Parameters: q  the queue to initialize compare  a comparison function that can compare two entries in the queue

int pq_put (  priority_queue_t *  q, void *  e )

Add element to the queue. Parameters: q  the queue e  the new element

void q_init (  dyn_queue_t *  q  )

Initialize the queue. A queue is a FIFO buffer, i.e. the first element to be inserted into the buffer is the first element to be returned.

void sb_append_internal (  string_buffer_t *  ,   ... )

Append a null terminated list of strings to the buffer. Example: sb_append2( my_buff, L"foo", L"bar", (void *)0 ); Do not forget to cast the last 0 to (void *), or you might encounter errors on 64-bit platforms!

void sb_clear (  string_buffer_t *   )

Completely truncate the buffer. This will not deallocate the memory used, it will only set the contents of the string to L"\0".

int sb_printf (  string_buffer_t *  buffer, const wchar_t *  format,   ... )

Append formated string data to the buffer. This function internally relies on vswprintf, so any filter options supported by that function is also supported by this function.

void sb_truncate (  string_buffer_t *  , int  chars_left )

Truncate the string to the specified number of characters. This will not deallocate the memory used.

int wcsfilecmp (  const wchar_t *  a, const wchar_t *  b )

Compares two wide character strings with an (arguably) intuitive ordering. This function tries to order strings in a way which is intuitive to humans with regards to sorting strings containing numbers. Most sorting functions would sort the strings 'file1.txt' 'file5.txt' and 'file12.txt' as: file1.txt file12.txt file5.txt This function regards any sequence of digits as a single entity when performing comparisons, so the output is instead: file1.txt file5.txt file12.txt Which most people would find more intuitive. This won't return the optimum results for numbers in bases higher than ten, such as hexadecimal, but at least a stable sort order will result. This function performs a two-tiered sort, where difference in case and in number of leading zeroes in numbers only have effect if no other differences between strings are found. This way, a 'file1' and 'File1' will not be considered identical, and hence their internal sort order is not arbitrary, but the names 'file1', 'File2' and 'file3' will still be sorted in the order given above.

---