Main Page | Data Structures | File List | Data Fields | Globals | Related Pages

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_tal_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_tsb_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  ) 
 

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.


Generated on Sun Jan 13 02:53:15 2008 for fish by  doxygen 1.4.4