aboutsummaryrefslogtreecommitdiffhomepage
path: root/util.c
diff options
context:
space:
mode:
Diffstat (limited to 'util.c')
-rw-r--r--util.c986
1 files changed, 986 insertions, 0 deletions
diff --git a/util.c b/util.c
new file mode 100644
index 00000000..3ea19ea4
--- /dev/null
+++ b/util.c
@@ -0,0 +1,986 @@
+/** \file util.c
+ Generic utilities library.
+
+ Contains datastructures such as hash tables, automatically growing array lists, priority queues, etc.
+*/
+
+#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 "util.h"
+#include "common.h"
+#include "wutil.h"
+
+/**
+ Minimum allocated size for data structures. Used to avoid excessive
+ memory allocations for lists, hash tables, etc, which are nearly
+ empty.
+*/
+#define MIN_SIZE 128
+
+/**
+ 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.
+*/
+#define SB_MAX_SIZE 32767
+
+float minf( float a,
+ float b )
+{
+ return a<b?a:b;
+}
+
+
+float maxf( float a,
+ float b )
+{
+ return a>b?a:b;
+}
+
+int mini( int a,
+ int b )
+{
+ return a<b?a:b;
+}
+
+
+int maxi( int a,
+ int b )
+{
+ return a>b?a:b;
+}
+
+
+/* Queue functions */
+
+
+void q_init( queue_t *q )
+{
+ q->start = (void **)malloc( sizeof(void*)*1 );
+ q->stop = &q->start[1];
+ q->put_pos = q->get_pos = q->start;
+}
+
+void q_destroy( queue_t *q )
+{
+ free( q->start );
+}
+
+/*
+ static q_print( queue_t *q )
+ {
+ int i;
+ int size = (q->stop-q->start);
+
+ printf( "Storlek: %d\n", size );
+ for( i=0; i< size; i++ )
+ {
+ printf( " %c%c %d: %d\n",
+ &q->start[i]==q->get_pos?'g':' ',
+ &q->start[i]==q->put_pos?'p':' ',
+ i,
+ q->start[i] );
+ }
+ }
+
+*/
+
+/**
+ Reallocate the queue_t
+*/
+static int q_realloc( queue_t *q )
+{
+ void **old_start = q->start;
+ void **old_stop = q->stop;
+ int diff;
+ int new_size;
+
+ new_size = 2*(q->stop-q->start);
+
+ q->start=(void**)realloc( q->start, sizeof(void*)*new_size );
+ if( q->start == 0 )
+ {
+ q->start = old_start;
+ return 0;
+ }
+
+ diff = q->start - old_start;
+ q->get_pos += diff;
+ q->stop = &q->start[new_size];
+ memcpy( old_stop + diff, q->start, sizeof(void*)*(q->get_pos-q->start));
+ q->put_pos = old_stop + diff + (q->get_pos-q->start);
+
+ return 1;
+}
+
+int q_put( queue_t *q, void *e )
+{
+ *q->put_pos = e;
+
+// fprintf( stderr, "Put element %d to queue %d\n", e, q );
+
+ if( ++q->put_pos == q->stop )
+ q->put_pos = q->start;
+ if( q->put_pos == q->get_pos )
+ return q_realloc( q );
+ return 1;
+}
+
+void *q_get( queue_t *q)
+{
+ void *e = *q->get_pos;
+ if( ++q->get_pos == q->stop )
+ q->get_pos = q->start;
+ return e;
+}
+
+void *q_peek( queue_t *q )
+{
+ return *q->get_pos;
+}
+
+int q_empty( queue_t *q )
+{
+// fprintf( stderr, "Queue %d is %s\n", q, (q->put_pos == q->get_pos)?"empty":"non-empty" );
+ return q->put_pos == q->get_pos;
+}
+
+/* Stack functions */
+
+
+
+
+/* Hash table functions */
+
+void hash_init2( hash_table_t *h,
+ int (*hash_func)(const void *key),
+ int (*compare_func)(const void *key1, const void *key2),
+ size_t capacity)
+{
+ int i;
+ size_t sz = capacity*4/3+1;
+
+ h->arr = malloc( sizeof(hash_struct_t)*sz );
+ h->size = sz;
+ for( i=0; i< sz; i++ )
+ h->arr[i].key = 0;
+ h->count=0;
+ h->hash_func = hash_func;
+ h->compare_func = compare_func;
+}
+
+void hash_init( hash_table_t *h,
+ int (*hash_func)(const void *key),
+ int (*compare_func)(const void *key1, const void *key2) )
+{
+ hash_init2( h, hash_func, compare_func, 31 );
+}
+
+
+void hash_destroy( hash_table_t *h )
+{
+ free( h->arr );
+}
+
+/**
+ Search for the specified hash key in the table
+ \return index in the table, or to the first free index if the key is not in the table
+*/
+static int hash_search( hash_table_t *h,
+ const void *key )
+{
+ int hv = h->hash_func( key );
+ int pos = abs(hv) % h->size;
+ while(1)
+ {
+ if( (h->arr[pos].key == 0 ) ||
+ ( h->compare_func( h->arr[pos].key, key ) ) )
+ {
+ return pos;
+ }
+ pos++;
+ pos %= h->size;
+ }
+}
+
+/**
+ Reallocate the hash array. This is quite expensive, as every single entry has to be rehashed and moved.
+*/
+static int hash_realloc( hash_table_t *h,
+ int sz )
+{
+
+ /* Avoid reallocating when using pathetically small tables */
+ if( ( sz < h->size ) && (h->size < MIN_SIZE))
+ return 1;
+ sz = maxi( sz, MIN_SIZE );
+
+ hash_struct_t *old_arr = h->arr;
+ int old_size = h->size;
+
+ int i;
+
+ h->arr = malloc( sizeof( hash_struct_t) * sz );
+ if( h->arr == 0 )
+ {
+ h->arr = old_arr;
+ return 0;
+ }
+
+ memset( h->arr,
+ 0,
+ sizeof( hash_struct_t) * sz );
+ h->size = sz;
+
+ for( i=0; i<old_size; i++ )
+ {
+ if( old_arr[i].key != 0 )
+ {
+ int pos = hash_search( h, old_arr[i].key );
+ h->arr[pos].key = old_arr[i].key;
+ h->arr[pos].data = old_arr[i].data;
+ }
+ }
+ free( old_arr );
+
+ return 1;
+}
+
+
+int hash_put( hash_table_t *h,
+ const void *key,
+ const void *data )
+{
+ int pos;
+
+ if( (float)(h->count+1)/h->size > 0.75f )
+ {
+ if( !hash_realloc( h, (h->size+1) * 2 -1 ) )
+ {
+ return 0;
+ }
+ }
+
+ pos = hash_search( h, key );
+
+ if( h->arr[pos].key == 0 )
+ {
+ h->count++;
+ }
+
+ h->arr[pos].key = key;
+ h->arr[pos].data = data;
+ return 1;
+}
+
+const void *hash_get( hash_table_t *h,
+ const void *key )
+{
+ int pos = hash_search( h, key );
+ if( h->arr[pos].key == 0 )
+ return 0;
+ else
+ return h->arr[pos].data;
+}
+
+const void *hash_get_key( hash_table_t *h,
+ const void *key )
+{
+ int pos = hash_search( h, key );
+ if( h->arr[pos].key == 0 )
+ return 0;
+ else
+ return h->arr[pos].key;
+}
+
+int hash_get_count( hash_table_t *h)
+{
+ return h->count;
+}
+
+void hash_remove( hash_table_t *h,
+ const void *key,
+ const void **old_key,
+ const void **old_val )
+{
+ int pos = hash_search( h, key );
+ int next_pos;
+
+ if( h->arr[pos].key == 0 )
+ {
+
+ if( old_key != 0 )
+ *old_key = 0;
+ if( old_val != 0 )
+ *old_val = 0;
+ return;
+ }
+
+ h->count--;
+
+ if( old_key != 0 )
+ *old_key = h->arr[pos].key;
+ if( old_val != 0 )
+ *old_val = h->arr[pos].data;
+
+ h->arr[pos].key = 0;
+
+ next_pos = pos+1;
+ next_pos %= h->size;
+
+ while( h->arr[next_pos].key != 0 )
+ {
+
+ int hv = h->hash_func( h->arr[next_pos].key );
+ int ideal_pos = abs( hv ) % h->size;
+ int dist_old = (next_pos - ideal_pos + h->size)%h->size;
+ int dist_new = (pos - ideal_pos + h->size)%h->size;
+ if ( dist_new < dist_old )
+ {
+ h->arr[pos].key = h->arr[next_pos].key;
+ h->arr[pos].data = h->arr[next_pos].data;
+ h->arr[next_pos].key = 0;
+ pos = next_pos;
+ }
+ next_pos++;
+
+ next_pos %= h->size;
+
+ }
+
+ if( (float)(h->count+1)/h->size < 0.2f && h->count < 63 )
+ {
+ hash_realloc( h, (h->size+1) / 2 -1 );
+ }
+
+ return;
+}
+
+int hash_contains( hash_table_t *h,
+ const void *key )
+{
+ int pos = hash_search( h, key );
+ return h->arr[pos].key != 0;
+}
+
+/**
+ Push hash value into array_list_t
+*/
+static void hash_put_data( const void *key,
+ const void *data,
+ void *al )
+{
+ al_push( (array_list_t *)al,
+ data );
+}
+
+
+void hash_get_data( hash_table_t *h,
+ array_list_t *arr )
+{
+ hash_foreach2( h, &hash_put_data, arr );
+}
+
+/**
+ Push hash key into array_list_t
+*/
+static void hash_put_key( const void *key, const void *data, void *al )
+{
+ al_push( (array_list_t *)al, key );
+}
+
+
+void hash_get_keys( hash_table_t *h,
+ array_list_t *arr )
+{
+ hash_foreach2( h, &hash_put_key, arr );
+}
+
+void hash_foreach( hash_table_t *h,
+ void (*func)(const void *, const void *) )
+{
+ int i;
+ for( i=0; i<h->size; i++ )
+ {
+ if( h->arr[i].key != 0 )
+ {
+ func( h->arr[i].key, h->arr[i].data );
+ }
+ }
+}
+
+void hash_foreach2( hash_table_t *h,
+ void (*func)( const void *, const void *, void * ),
+ void *aux )
+{
+ int i;
+ for( i=0; i<h->size; i++ )
+ {
+ if( h->arr[i].key != 0 )
+ {
+ func( h->arr[i].key, h->arr[i].data, aux );
+ }
+ }
+}
+
+
+int hash_str_cmp( const void *a, const void *b )
+{
+ return strcmp((char *)a,(char *)b) == 0;
+}
+
+/**
+ Helper function for hash_wcs_func
+*/
+static uint rotl5( uint in )
+{
+ return (in<<5|in>>27);
+}
+
+
+int hash_str_func( const void *data )
+{
+ int res = 0x67452301u;
+ const char *str = data;
+
+ while( *str )
+ res = (18499*rotl5(res)) ^ *str++;
+
+ return res;
+}
+
+int hash_wcs_func( const void *data )
+{
+ int res = 0x67452301u;
+ const wchar_t *str = data;
+
+ while( *str )
+ res = (18499*rotl5(res)) ^ *str++;
+
+ return res;
+}
+
+
+int hash_wcs_cmp( const void *a, const void *b )
+{
+ return wcscmp((wchar_t *)a,(wchar_t *)b) == 0;
+}
+
+void pq_init( priority_queue_t *q,
+ int (*compare)(void *e1, void *e2) )
+{
+ q->arr=0;
+ q->size=0;
+ q->count=0;
+ q->compare = compare;
+}
+
+/**
+ Check that the priority queue is in a valid state
+*/
+/*
+ static void pq_check( priority_queue_t *q, int i )
+ {
+ int l,r;
+ if( q->count <= i )
+ return;
+
+ l=i*2+1;
+ r=i*2+2;
+
+
+ if( (q->count > l) && (q->compare(q->arr[i], q->arr[l]) < 0) )
+ {
+ printf( "ERROR: Place %d less than %d\n", i, l );
+ }
+ if( (q->count > r) && (q->compare(q->arr[i], q->arr[r]) < 0) )
+ {
+ printf( "ERROR: Place %d less than %d\n", i, r );
+ }
+ pq_check( q, l );
+ pq_check( q, r );
+ }
+*/
+
+int pq_put( priority_queue_t *q,
+ void *e )
+{
+ int i;
+
+ if( q->size == q->count )
+ {
+ void **old_arr = q->arr;
+ int old_size = q->size;
+ q->size = maxi( 4, 2*q->size );
+ q->arr = (void **)realloc( q->arr, sizeof(void*)*q->size );
+ if( q->arr == 0 )
+ {
+ q->arr = old_arr;
+ q->size = old_size;
+ return 0;
+ }
+ }
+
+ i = q->count;
+ while( (i>0) && (q->compare( q->arr[(i-1)/2], e )<0 ) )
+ {
+ q->arr[i] = q->arr[(i-1)/2];
+ i = (i-1)/2;
+ }
+ q->arr[i]=e;
+
+ q->count++;
+
+ return 1;
+
+}
+
+/**
+ Make a valid head
+*/
+static void pq_heapify( priority_queue_t *q, int i )
+{
+ int l, r, largest;
+ l = 2*(i)+1;
+ r = 2*(i)+2;
+ if( (l < q->count) && (q->compare(q->arr[l],q->arr[i])>0) )
+ {
+ largest = l;
+ }
+ else
+ {
+ largest = i;
+ }
+ if( (r < q->count) && (q->compare( q->arr[r],q->arr[largest])>0) )
+ {
+ largest = r;
+ }
+
+ if( largest != i )
+ {
+ void *tmp = q->arr[largest];
+ q->arr[largest]=q->arr[i];
+ q->arr[i]=tmp;
+ pq_heapify( q, largest );
+ }
+}
+
+void *pq_get( priority_queue_t *q )
+{
+ void *result = q->arr[0];
+ q->arr[0] = q->arr[--q->count];
+ pq_heapify( q, 0 );
+
+/* pq_check(q, 0 ); */
+/* pq_print( q ); */
+
+ return result;
+}
+
+void *pq_peek( priority_queue_t *q )
+{
+ return q->arr[0];
+}
+
+int pq_empty( priority_queue_t *q )
+{
+ return q->count == 0;
+}
+
+int pq_get_count( priority_queue_t *q )
+{
+ return q->count;
+}
+
+void pq_destroy( priority_queue_t *q )
+{
+ free( q->arr );
+}
+
+
+void al_init( array_list_t *l )
+{
+ memset( l, 0, sizeof( array_list_t ) );
+}
+
+void al_destroy( array_list_t *l )
+{
+ free( l->arr );
+}
+
+int al_push( array_list_t *l, const void *o )
+{
+ if( l->pos >= l->size )
+ {
+ int new_size = l->pos == 0 ? MIN_SIZE : 2 * l->pos;
+ void *tmp = realloc( l->arr, sizeof( void *)*new_size );
+ if( tmp == 0 )
+ return 0;
+ l->arr = tmp;
+ l->size = new_size;
+ }
+ l->arr[l->pos++] = o;
+ return 1;
+}
+
+int al_push_all( array_list_t *a, array_list_t *b )
+{
+ int k;
+ for( k=0; k<al_get_count( b ); k++ )
+ {
+ if( !al_push( a, al_get( b, k ) ) )
+ return 0;
+ }
+ return 1;
+}
+
+
+int al_set( array_list_t *l, int pos, const void *o )
+{
+ int old_pos;
+
+ if( pos < 0 )
+ return 0;
+ if( pos < l->pos )
+ {
+ l->arr[pos] = o;
+ return 1;
+ }
+ old_pos=l->pos;
+
+ l->pos = pos;
+ if( al_push( l, o ) )
+ {
+/* fwprintf( stderr, L"Clearing from index %d to index %d\n",
+ old_pos, pos );
+*/
+ memset( &l->arr[old_pos],
+ 0,
+ sizeof(void *) * (pos - old_pos) );
+ return 1;
+ }
+ return 0;
+}
+
+const void *al_get( array_list_t *l, int pos )
+{
+ if( pos < 0 )
+ return 0;
+ if( pos >= l->pos )
+ return 0;
+ return l->arr[pos];
+}
+
+void al_truncate( array_list_t *l, int new_sz )
+{
+ l->pos = new_sz;
+}
+
+const void *al_pop( array_list_t *l )
+{
+ const void *e = l->arr[--l->pos];
+ if( (l->pos*3 < l->size) && (l->size < MIN_SIZE) )
+ {
+ const void ** old_arr = l->arr;
+ int old_size = l->size;
+ l->size = l->size/2;
+ l->arr = realloc( l->arr, sizeof(void*)*l->size );
+ if( l->arr == 0 )
+ {
+ l->arr = old_arr;
+ l->size = old_size;
+ }
+ }
+ return e;
+}
+
+const void *al_peek( array_list_t *l )
+{
+
+ return l->pos>0?l->arr[l->pos-1]:0;
+}
+
+int al_empty( array_list_t *l )
+{
+ return l->pos == 0;
+}
+
+int al_get_count( array_list_t *l )
+
+{
+ return l->pos;
+}
+
+void al_foreach( array_list_t *l, void (*func)( const void * ))
+{
+ int i;
+ for( i=0; i<l->pos; i++ )
+ func( l->arr[i] );
+}
+
+void al_foreach2( array_list_t *l, void (*func)( const void *, void *), void *aux)
+{
+ int i;
+ for( i=0; i<l->pos; i++ )
+ func( l->arr[i], aux );
+}
+
+int wcsfilecmp( const wchar_t *a, const wchar_t *b )
+{
+ if( *a==0 )
+ {
+ if( *b==0)
+ return 0;
+ return -1;
+ }
+ if( *b==0 )
+ {
+ return 1;
+ }
+ int secondary_diff=0;
+ if( iswdigit( *a ) && iswdigit( *b ) )
+ {
+ wchar_t *aend, *bend;
+ long al = wcstol( a, &aend, 10 );
+ long bl = wcstol( b, &bend, 10 );
+ int diff = al - bl;
+ if( diff )
+ return diff>0?2:-2;
+
+ secondary_diff = (aend-a) - (bend-b);
+
+ a=aend-1;
+ b=bend-1;
+ }
+ else
+ {
+ int diff = towlower(*a) - towlower(*b);
+ if( diff != 0 )
+ return (diff>0)?2:-2;
+
+ secondary_diff = *a-*b;
+ }
+
+ int res = wcsfilecmp( a+1, b+1 );
+ switch( abs(res) )
+ {
+ case 2:
+ return res;
+ default:
+ if( secondary_diff )
+ return secondary_diff>0?1:-1;
+ }
+ return 0;
+
+}
+
+void sb_init( string_buffer_t * b)
+{
+ wchar_t c=0;
+ memset( b, 0, sizeof(string_buffer_t) );
+ b_append( b, &c, sizeof( wchar_t));
+ b->used -= sizeof(wchar_t);
+}
+
+void sb_append( string_buffer_t *b, const wchar_t * s)
+{
+// fwprintf( stderr, L"Append string \'%ls\'\n", s );
+
+ if( !s )
+ return;
+
+
+ b_append( b, s, sizeof(wchar_t)*(wcslen(s)+1) );
+ b->used -= sizeof(wchar_t);
+}
+
+void sb_append_substring( string_buffer_t *b, const wchar_t *s, size_t l )
+{
+ wchar_t tmp=0;
+
+ if( !s )
+ return;
+
+ b_append( b, s, sizeof(wchar_t)*l );
+ b_append( b, &tmp, sizeof(wchar_t) );
+ b->used -= sizeof(wchar_t);
+}
+
+
+void sb_append_char( string_buffer_t *b, wchar_t c )
+{
+ wchar_t buff[2]=
+ {
+ c, 0
+ }
+ ;
+ sb_append( b, buff );
+
+}
+
+void sb_append2( string_buffer_t *b, ... )
+{
+ va_list va;
+ wchar_t *arg;
+
+ va_start( va, b );
+ while( (arg=va_arg(va, wchar_t *) )!= 0 )
+ {
+ sb_append( b, arg );
+ }
+ va_end( va );
+}
+
+int sb_printf( string_buffer_t *buffer, const wchar_t *format, ... )
+{
+ va_list va;
+ int res;
+
+ if( !buffer->length )
+ {
+ buffer->length = MIN_SIZE;
+ buffer->buff = malloc( MIN_SIZE );
+ if( !buffer->buff )
+ die_mem();
+ }
+
+
+ while( 1 )
+ {
+
+ va_start( va, format );
+ res = vswprintf( (wchar_t *)((char *)buffer->buff+buffer->used),
+ (buffer->length-buffer->used)/sizeof(wchar_t),
+ format,
+ va );
+
+ if( res >= 0 )
+ {
+ buffer->used+= res*sizeof(wchar_t);
+ break;
+ }
+
+ /*
+ As far as I know, there is no way to check if a
+ vswprintf-call failed because of a badly formated string
+ option or because the supplied destination string was to
+ small. In GLIBC, errno seems to be set to EINVAL either way.
+
+ Because of this, sb_printf will on failiure try to
+ increase the buffer size until the free space is larger than
+ SB_MAX_SIZE, at which point it will conclude that the error
+ was probably due to a badly formated string option, and
+ return an error.
+ */
+
+ if( buffer->length - buffer->used > SB_MAX_SIZE )
+ break;
+
+ buffer->buff = realloc( buffer->buff, 2*buffer->length );
+ if( !buffer->buff )
+ die_mem();
+ buffer->length *= 2;
+ }
+ va_end( va );
+ return res;
+}
+
+
+
+
+void sb_destroy( string_buffer_t * b )
+{
+ free( b->buff );
+}
+
+void sb_clear( string_buffer_t * b )
+{
+ free( b->buff );
+ sb_init( b );
+}
+
+
+void b_init( buffer_t *b)
+{
+ memset( b,0,sizeof(buffer_t));
+}
+
+
+
+void b_destroy( buffer_t *b )
+{
+ free( b->buff );
+}
+
+
+void b_append( buffer_t *b, const void *d, ssize_t len )
+{
+ if( len<=0 )
+ return;
+
+ if( !b )
+ {
+ debug( 2, L"Copy to null buffer" );
+ return;
+ }
+
+ if( !d )
+ {
+ debug( 2, L"Copy from null pointer" );
+ return;
+ }
+
+ if( len < 0 )
+ {
+ debug( 2, L"Negative number of characters to be copied" );
+ return;
+ }
+
+
+ if( b->length <= (b->used + len) )
+ {
+ size_t l = maxi( b->length*2,
+ maxi( b->used+len+MIN_SIZE,MIN_SIZE));
+
+ void *d = realloc( b->buff, l );
+ if( !d )
+ {
+ die_mem();
+
+ }
+ b->buff=d;
+ b->length = l;
+ }
+ memcpy( ((char*)b->buff)+b->used,
+ d,
+ len );
+
+// fwprintf( stderr, L"Copy %s, new value %s\n", d, b->buff );
+ b->used+=len;
+}
+
+long long get_time()
+{
+ struct timeval time_struct;
+ gettimeofday( &time_struct, 0 );
+ return 1000000ll*time_struct.tv_sec+time_struct.tv_usec;
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-20 09:36:26 +0000