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   (128*1024*1024)
 Maximum number of characters that can be inserted using a single call to sb_printf.
#define oom_handler(p)
 Handle oom condition.
#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 *))
 Set the out-of-memory handler callback function.
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)
 Real implementation of all al_push_* versions.
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)
 Append element to list.
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)
 Insert the specified number of new empty positions at the specified position in the list.
static int al_set_generic (array_list_t *l, int pos, anything_t v)
 Real implementation of all al_set_* versions.
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 f)
 Sets the element at the specified index.
static anything_t al_get_generic (array_list_t *l, int pos)
 Real implementation of all al_get_* versions.
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)
 Real implementation of all al_pop_* versions.
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)
 Real implementation of all al_peek_* versions.
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.

Referenced by al_pop_generic(), al_push_generic(), b_append(), and sb_vprintf().

#define oom_handler (  ) 

Value:

{                                                                                       \
                if( oom_handler_internal == util_die_on_oom )   \
                {                                                                                               \
                        DIE_MEM();                                                                      \
                }                                                                                               \
                oom_handler_internal( p );                                              \
        }                                                                                                       \
Handle oom condition.

Default action is to print a stack trace and exit, but an alternative action can be specified.

Referenced by al_insert(), al_new(), al_push_generic(), b_append(), hash_init2(), hash_realloc(), pq_put(), q_init(), q_realloc(), sb_new(), and sb_vprintf().

#define SB_MAX_SIZE   (128*1024*1024)

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. We assume that any error is an out of memory-error and try again until we reach this size. After this size has been reached, it is instead assumed that something was wrong with the format string.

Referenced by sb_vprintf().


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

References al_get_generic(), and anything_t::ptr_val.

Referenced by al_contains_str(), al_push_all(), al_push_check(), autoload_names(), builtin_bind_erase(), builtin_bind_function_names(), builtin_bind_key_names(), builtin_bind_list(), builtin_builtin(), builtin_complete(), builtin_complete_add(), builtin_complete_add2(), builtin_complete_remove(), builtin_complete_remove3(), builtin_function(), builtin_functions(), builtin_help_get(), complete_cmd(), complete_cmd_desc(), complete_get_desc_suffix_internal(), complete_strings(), complete_variable(), contains_al(), env_export_arr(), erase_values(), event_copy(), event_fire_delayed(), event_fire_internal(), event_free_kills(), event_get(), event_is_killed(), event_remove(), exec_prompt(), expand_cmdsubst(), expand_escape_variable(), expand_one(), expand_string(), expand_test(), expand_variables(), function_add(), functions_def(), halloc_free(), handle_completions(), handle_token_history(), history_get(), history_is_used(), history_next_match(), history_prev_match(), history_save_mode(), input_mapping_add(), input_mapping_erase(), input_mapping_get(), input_mapping_get_names(), input_readch(), input_terminfo_get_name(), input_terminfo_get_names(), input_terminfo_get_sequence(), kill_check_x_buffer(), launch(), list_to_char_arr(), main(), my_env_set(), output_color_code(), parse_job(), parse_job_argument_list(), parse_util_autounload(), parse_util_load_internal(), parse_util_set_argv(), print_profile(), print_variables(), reader_write_title(), remove_duplicates(), run_pager(), s_desired_append_char(), s_update(), setup_path(), update_values(), and wildcard_expand().

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

References al_get_generic(), and anything_t::func_val.

Referenced by halloc_free().

static anything_t al_get_generic ( array_list_t l,
int  pos 
) [static]

Real implementation of all al_get_* versions.

Returns element from list.

References array_list::arr, and anything_t::ptr_val.

Referenced by al_get(), al_get_func(), and al_get_long().

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

References al_get_generic(), and anything_t::long_val.

Referenced by al_contains_long(), al_test(), builtin_set(), close_unused_internal_pipes(), exec_close(), expand_cmdsubst(), expand_variables(), history_is_used(), and update_values().

array_list_t* al_new (  ) 

Allocate heap memory for creating a new list and initialize it.

Equivalent to calling malloc and al_init.

References al_init(), and oom_handler.

Referenced by eval(), event_add_handler(), event_fire(), event_fire_delayed(), event_fire_internal(), event_remove(), parse_util_load(), and parser_init().

static anything_t al_peek_generic ( array_list_t l  )  [static]

Real implementation of all al_peek_* versions.

Peeks last element of list.

References array_list::arr, array_list::pos, and anything_t::ptr_val.

Referenced by al_peek(), al_peek_func(), and al_peek_long().

static anything_t al_pop_generic ( array_list_t l  )  [static]

Real implementation of all al_pop_* versions.

Pops arbitrary element from end of list.

References array_list::arr, MIN_SIZE, array_list::pos, and array_list::size.

Referenced by al_pop(), al_pop_func(), and al_pop_long().

int al_push ( array_list_t l,
const void *  o 
)

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

References al_get(), al_get_count(), and al_push().

Referenced by erase_values(), expand_variables(), and history_populate_from_mmap().

int al_push_func ( array_list_t l,
func_ptr_t  f 
)

Append element to list.

Parameters:
l The list
f The element
Returns:
1 if succesfull, 0 otherwise

References al_push_generic(), and anything_t::func_val.

Referenced by halloc(), and halloc_register_function().

static int al_push_generic ( array_list_t l,
anything_t  o 
) [static]

Real implementation of all al_push_* versions.

Pushes arbitrary element to end of list.

References array_list::arr, MIN_SIZE, oom_handler, array_list::pos, array_list::size, and tmp.

Referenced by al_push(), al_push_func(), al_push_long(), and al_set_generic().

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

References al_push_generic(), and anything_t::long_val.

Referenced by builtin_push_io(), exec_pipe(), highlight_universal_internal(), history_prev_match(), parse_index(), parse_slice(), proc_push_interactive(), and stack_test().

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

References al_set_generic(), and anything_t::ptr_val.

Referenced by event_fire_delayed(), expand_cmdsubst(), expand_one(), expand_variables(), input_mapping_erase(), parse_job(), remove_duplicates(), and update_values().

int al_set_func ( array_list_t l,
int  pos,
func_ptr_t  f 
)

Sets the element at the specified index.

Parameters:
l The array_list_t
pos The index
f The element to insert

References al_set_generic(), and anything_t::func_val.

static int al_set_generic ( array_list_t l,
int  pos,
anything_t  v 
) [static]

Real implementation of all al_set_* versions.

Sets arbitrary element of list.

References al_push_generic(), array_list::arr, and array_list::pos.

Referenced by al_set(), al_set_func(), and al_set_long().

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
v The element to set

References al_set_generic(), and anything_t::long_val.

Referenced by al_test(), exec_close(), s_desired_append_char(), and s_update().

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

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

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.

References hash_table::arr, hash_table::cache, compare_func(), hash_table::compare_func, hash_table::count, hash_func(), hash_table::hash_func, hash_struct_t::key, oom_handler, and hash_table::size.

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.

References hash_table::arr, hash_table::cache, hash_struct_t::data, HASH_MIN_SIZE, hash_search(), hash_struct_t::key, maxi(), oom_handler, and hash_table::size.

Referenced by hash_put(), and hash_remove().

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

References hash_table::arr, hash_table::count, hash_struct_t::data, hash_table::hash_func, hash_realloc(), hash_search(), hash_struct_t::key, and hash_table::size.

Referenced by env_set(), env_universal_common_remove(), export_func1(), function_remove(), hash_test(), parse_util_load(), parse_util_load_reset(), parse_util_unload(), and try_remove().

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

References hash_table::arr, hash_table::cache, hash_table::compare_func, hash_table::hash_func, hash_struct_t::key, and hash_table::size.

Referenced by hash_contains(), hash_get(), hash_get_key(), hash_put(), hash_realloc(), and hash_remove().

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.

References rotl1(), rotl30(), rotl5(), and WORD_COUNT.

Referenced by builtin_get_desc(), builtin_init(), complete_cmd_desc(), complete_get_desc_suffix(), complete_is_valid_option(), condition_test(), env_export_arr(), env_get_names(), env_init(), env_push(), env_universal_common_init(), function_init(), hash_item_func(), history_set_mode(), intern(), intern_static(), and parse_util_load().

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

References priority_queue::arr, priority_queue::compare, priority_queue::count, and priority_queue::size.

Referenced by pq_test().

int pq_put ( priority_queue_t q,
void *  e 
)

Add element to the queue.

Parameters:
q the queue
e the new element

References priority_queue::arr, priority_queue::compare, priority_queue::count, maxi(), oom_handler, and priority_queue::size.

Referenced by pq_test().

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.

References dyn_queue::get_pos, oom_handler, dyn_queue::put_pos, dyn_queue::start, and dyn_queue::stop.

Referenced by connection_init().

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!

References b_append(), CHECK, and buffer::used.

void sb_clear ( string_buffer_t  ) 

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.

References CHECK, and sb_vprintf().

Referenced by append_switch(), builtin_bg(), builtin_bind(), builtin_bind_add(), builtin_bind_function_names(), builtin_bind_key_names(), builtin_bind_list(), builtin_block(), builtin_break_continue(), builtin_builtin(), builtin_case(), builtin_cd(), builtin_commandline(), builtin_complete(), builtin_contains(), builtin_count(), builtin_else(), builtin_emit(), builtin_end(), builtin_exit(), builtin_fg(), builtin_for(), builtin_function(), builtin_functions(), builtin_generic(), builtin_help_get(), builtin_jobs(), builtin_jobs_print(), builtin_missing_argument(), builtin_print_help(), builtin_random(), builtin_read(), builtin_return(), builtin_set(), builtin_source(), builtin_status(), builtin_switch(), builtin_ulimit(), builtin_unknown_option(), complete_param(), complete_print(), complete_variable(), debug(), env_get(), event_get_desc(), find_process(), full_escape(), functions_def(), indent(), input_terminfo_get_name(), input_terminfo_get_sequence(), my_env_set(), parse_index(), parser_current_line(), parser_stack_trace(), parser_test(), print(), print_all(), print_errors(), proc_fire_event(), read_init(), run_pager(), sb_format_size(), sb_test(), send_to_bg(), set(), start_fishd(), try_complete_user(), wbasename(), wdirname(), wgetenv(), wgettext(), wildcard_expand(), write_screen(), and wsetlocale().

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.

References buffer::buff, CHECK, and buffer::used.

Referenced by sb_clear().

void(*)(void *) util_set_oom_handler ( void(*)(void *)  h  ) 

Set the out-of-memory handler callback function.

If a memory allocation fails, this function will be called.

References util_die_on_oom().

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.

References CHECK, and wcsfilecmp().

Referenced by completion_cmp(), str_cmp(), and wcsfilecmp().


Generated on Sun Mar 8 15:46:55 2009 for fish by  doxygen 1.5.6