summaryrefslogtreecommitdiff
path: root/support/texlab/crates/bibutils_sys/src/intlist.c
diff options
context:
space:
mode:
Diffstat (limited to 'support/texlab/crates/bibutils_sys/src/intlist.c')
-rw-r--r--support/texlab/crates/bibutils_sys/src/intlist.c590
1 files changed, 590 insertions, 0 deletions
diff --git a/support/texlab/crates/bibutils_sys/src/intlist.c b/support/texlab/crates/bibutils_sys/src/intlist.c
new file mode 100644
index 0000000000..94ebc3d5da
--- /dev/null
+++ b/support/texlab/crates/bibutils_sys/src/intlist.c
@@ -0,0 +1,590 @@
+/*
+ * intlist.c
+ *
+ * Copyright (c) Chris Putnam 2007-2019
+ *
+ * Version 1/12/2017
+ *
+ * Source code released under the GPL version 2
+ *
+ * Implements a simple managed array of ints
+ *
+ */
+#include <stdlib.h>
+#include <assert.h>
+#include "intlist.h"
+
+#define INTLIST_MINALLOC (20)
+
+static int
+intlist_validn( intlist *il, int n )
+{
+ if ( n < 0 || n >= il->n ) return 0;
+ return 1;
+}
+
+int
+intlist_wasfound( intlist *il, int n )
+{
+ if ( n!=-1 ) return 1;
+ else return 0;
+}
+
+int
+intlist_wasnotfound( intlist *il, int n )
+{
+ if ( n==-1 ) return 1;
+ else return 0;
+}
+
+static int
+intlist_alloc( intlist *il, int alloc_size )
+{
+ il->data = ( int * ) calloc( alloc_size, sizeof( int ) );
+ if ( !(il->data) ) return INTLIST_MEMERR;
+ il->max = alloc_size;
+ il->n = 0;
+ return INTLIST_OK;
+}
+
+static int
+intlist_realloc( intlist *il, int alloc_size )
+{
+ int i, *more;
+
+ more = ( int * ) realloc( il->data, sizeof( int ) * alloc_size );
+ if ( !more ) return INTLIST_MEMERR;
+
+ il->data = more;
+ il->max = alloc_size;
+
+ for ( i=il->max; i<alloc_size; ++i )
+ il->data[i] = 0;
+
+ return INTLIST_OK;
+}
+
+static int
+intlist_ensure_space( intlist *il, int n )
+{
+ int alloc = n;
+
+ if ( il->max == 0 ) {
+ if ( alloc < INTLIST_MINALLOC ) alloc = INTLIST_MINALLOC;
+ return intlist_alloc( il, alloc );
+ }
+
+ else if ( il->max <= n ) {
+ if ( alloc < il->max * 2 ) alloc = il->max * 2;
+ return intlist_realloc( il, alloc );
+ }
+
+ return INTLIST_OK;
+}
+
+/* intlist_add()
+ *
+ * Returns INTLIST_OK/INTLIST_MEMERR
+ */
+int
+intlist_add( intlist *il, int value )
+{
+ int status;
+
+ assert( il );
+
+ status = intlist_ensure_space( il, il->n+1 );
+
+ if ( status == INTLIST_OK ) {
+ il->data[ il->n ] = value;
+ il->n++;
+ }
+
+ return status;
+}
+
+/* intlist_add_unique()
+ *
+ * Returns INTLIST_OK/INTLIST_MEMERR
+ */
+int
+intlist_add_unique( intlist *il, int value )
+{
+ int n;
+
+ assert( il );
+
+ n = intlist_find( il, value );
+ if ( intlist_wasnotfound( il, n ) )
+ return intlist_add( il, value );
+ else
+ return INTLIST_OK;
+}
+
+int
+intlist_find_or_add( intlist *il, int value )
+{
+ int n, status;
+
+ n = intlist_find( il, value );
+
+ if ( intlist_wasfound( il, n ) ) {
+ return n;
+ }
+
+ else {
+ status = intlist_add( il, value );
+ if ( status!=INTLIST_OK ) return -1;
+ else return il->n - 1;
+ }
+}
+
+/* intlist_find()
+ *
+ * Returns position of value in range [0,n), or -1 if
+ * value cannot be found
+ */
+int
+intlist_find( intlist *il, int value )
+{
+ int i;
+
+ assert( il );
+
+ for ( i=0; i<il->n; ++i )
+ if ( il->data[i]==value ) return i;
+
+ return -1;
+}
+
+static int
+intlist_remove_pos_core( intlist *il, int pos )
+{
+ int i;
+
+ assert( il );
+
+ for ( i=pos; i<il->n-1; ++i )
+ il->data[i] = il->data[i+1];
+ il->n -= 1;
+
+ return INTLIST_OK;
+}
+
+/* intlist_remove_pos()
+ *
+ * Returns INTLIST_OK on success.
+ */
+int
+intlist_remove_pos( intlist *il, int pos )
+{
+ assert( il );
+ assert( intlist_validn( il, pos ) );
+
+ return intlist_remove_pos_core( il, pos );
+}
+
+/* intlist_remove()
+ *
+ * Removes first instance of value from the intlist.
+ * Returns INTLIST_OK/INTLIST_VALUE_MISSING
+ */
+int
+intlist_remove( intlist *il, int value )
+{
+ int pos;
+
+ assert( il );
+
+ pos = intlist_find( il, value );
+ if ( pos==-1 ) return INTLIST_VALUE_MISSING;
+
+ return intlist_remove_pos_core( il, pos );
+}
+
+/* don't actually free space, just reset counter */
+void
+intlist_empty( intlist *il )
+{
+ assert( il );
+
+ il->n = 0;
+}
+
+void
+intlist_free( intlist *il )
+{
+ assert( il );
+
+ if ( il->data ) free( il->data );
+ intlist_init( il );
+}
+
+void
+intlist_delete( intlist *il )
+{
+ assert( il );
+
+ if ( il->data ) free( il->data );
+ free( il );
+}
+
+void
+intlist_init( intlist *il )
+{
+ assert( il );
+
+ il->data = NULL;
+ il->max = 0;
+ il->n = 0;
+}
+
+/* Returns INTLIST_OK/INTLIST_MEMERR
+ */
+int
+intlist_init_fill( intlist *il, int n, int v )
+{
+ intlist_init( il );
+ return intlist_fill( il, n, v );
+}
+
+/* intlist_init_range()
+ *
+ * Initializes intlist to values from [low,high) with step step.
+ * Returns INTLIST_OK/INTLIST_MEMERR.
+ */
+int
+intlist_init_range( intlist *il, int low, int high, int step )
+{
+ intlist_init( il );
+ return intlist_fill_range( il, low, high, step );
+}
+
+/* intlist_new()
+ *
+ * Allocates an empty intlist.
+ * Returns pointer to intlist on success, NULL on memory error.
+ */
+intlist *
+intlist_new( void )
+{
+ intlist *il;
+ il = ( intlist * ) malloc( sizeof( intlist ) );
+ if ( il ) intlist_init( il );
+ return il;
+}
+
+/* intlist_new_range()
+ *
+ * Allocates a intlist initialized to values from [low,high) in increments of step.
+ * Returns pointer to intlist on success, NULL on memory error.
+ */
+intlist *
+intlist_new_range( int low, int high, int step )
+{
+ intlist *il;
+ int status;
+
+ il = intlist_new();
+ if ( il ) {
+ status = intlist_fill_range( il, low, high, step );
+ if ( status==INTLIST_MEMERR ) {
+ intlist_free( il );
+ free( il );
+ il = NULL;
+ }
+ }
+ return il;
+}
+
+/* intlist_new_range()
+ *
+ * Allocates a intlist initialized to n elements with value v.
+ * Returns pointer to intlist on success, NULL on memory error.
+ */
+intlist *
+intlist_new_fill( int n, int v )
+{
+ intlist *il;
+ int status;
+
+ il = intlist_new();
+ if ( il ) {
+ status = intlist_fill( il, n, v );
+ if ( status==INTLIST_MEMERR ) {
+ intlist_free( il );
+ free( il );
+ il = NULL;
+ }
+ }
+ return il;
+}
+
+/* intlist_fill()
+ *
+ * Fill an intlist with n elements of value v.
+ *
+ * Returns INTLIST_OK or INTLIST_MEMERR.
+ */
+int
+intlist_fill( intlist *il, int n, int v )
+{
+ int i, status;
+
+ assert ( n > 0 );
+
+ status = intlist_ensure_space( il, n );
+
+ if ( status==INTLIST_OK ) {
+
+ for ( i=0; i<n; ++i )
+ il->data[i] = v;
+
+ il->n = n;
+
+ }
+
+ return status;
+}
+
+/* intlist_fill_range()
+ *
+ * Fill an intlist with the values [low,high) in increments of step
+ *
+ * Returns INTLIST_OK or INTLIST_MEMERR.
+ */
+int
+intlist_fill_range( intlist *il, int low, int high, int step )
+{
+ int i, n, status;
+
+ n = ( high - low ) / step + 1;
+
+ assert ( n > 0 );
+
+ status = intlist_ensure_space( il, n );
+
+ if ( status==INTLIST_OK ) {
+
+ il->n = 0;
+
+ /* ...fill intlist with range */
+ if ( step > 0 ) {
+ for ( i=low; i<high; i+=step ) {
+ il->data[il->n] = i;
+ il->n += 1;
+ }
+ }
+ else {
+ for ( i=low; i>high; i+=step ) {
+ il->data[il->n] = i;
+ il->n += 1;
+ }
+ }
+
+ }
+
+ return status;
+}
+
+static int
+intcomp( const void *v1, const void *v2 )
+{
+ int *i1 = ( int * ) v1;
+ int *i2 = ( int * ) v2;
+ if ( *i1 < *i2 ) return -1;
+ else if ( *i1 > *i2 ) return 1;
+ return 0;
+}
+
+void
+intlist_sort( intlist *il )
+{
+ assert( il );
+
+ qsort( il->data, il->n, sizeof( int ), intcomp );
+}
+
+/* Returns random integer in the range [floor,ceil) */
+static int
+randomint( int floor, int ceil )
+{
+ int len = ceil - floor;
+ return floor + rand() % len;
+}
+
+static void
+swap( int *a, int *b )
+{
+ int tmp;
+ tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+void
+intlist_randomize( intlist *il )
+{
+ int i, j;
+
+ assert( il );
+
+ if ( il->n < 2 ) return;
+ for ( i=0; i<il->n; ++i ) {
+ j = randomint( i, il->n );
+ if ( i==j ) continue;
+ swap( &(il->data[i]), &(il->data[j]) );
+ }
+}
+
+/* Returns INTLIST_OK/INTLIST_MEMERR */
+int
+intlist_copy( intlist *to, intlist *from )
+{
+ int i, status;
+
+ assert( to );
+ assert( from );
+
+ status = intlist_ensure_space( to, from->n );
+
+ if ( status==INTLIST_OK ) {
+
+ to->n = from->n;
+
+ for ( i=0; i<from->n; ++i )
+ to->data[i] = from->data[i];
+
+ }
+
+ return status;
+}
+
+/* Returns pointer on success, NULL on error */
+intlist *
+intlist_dup( intlist *il )
+{
+ intlist *l;
+ int status;
+
+ assert( il );
+
+ l = intlist_new();
+ if ( l ) {
+ status = intlist_copy( l, il );
+ if ( status==INTLIST_MEMERR ) {
+ intlist_delete( l );
+ l = NULL;
+ }
+ }
+
+ return l;
+}
+
+int
+intlist_append( intlist *to, intlist *from )
+{
+ int i, status;
+
+ assert( to );
+ assert( from );
+
+ status = intlist_ensure_space( to, to->n + from->n );
+
+ if ( status == INTLIST_OK ) {
+
+ for ( i=0; i<from->n; ++i )
+ to->data[ to->n + i ] = from->data[ i ];
+
+ to->n += from->n;
+ }
+
+ return status;
+}
+
+int
+intlist_append_unique( intlist *to, intlist *from )
+{
+ int i, nsave, status = INTLIST_OK;
+
+ assert( to );
+ assert( from );
+
+ nsave = to->n;
+ for ( i=0; i<from->n; ++i ) {
+ if ( intlist_find( to, from->data[i] )!=-1 ) continue;
+ status = intlist_add( to, from->data[i] );
+ if ( status==INTLIST_MEMERR ) {
+ to->n = nsave;
+ }
+ }
+ return status;
+}
+
+int
+intlist_get( intlist *il, int pos )
+{
+ assert( il );
+ assert( intlist_validn( il, pos ) );
+
+ return il->data[pos];
+}
+
+/* intlist_set()
+ *
+ * Returns INTLIST_OK
+ */
+int
+intlist_set( intlist *il, int pos, int value )
+{
+ assert( il );
+ assert( intlist_validn( il, pos ) );
+
+ il->data[pos] = value;
+ return INTLIST_OK;
+}
+
+float
+intlist_median( intlist *il )
+{
+ intlist *tmp;
+ float median;
+ int m1, m2;
+
+ assert( il );
+
+ if ( il->n==0 ) return 0.0;
+
+ tmp = intlist_dup( il );
+ if ( !tmp ) return 0.0;
+
+ intlist_sort( tmp );
+
+ if ( tmp->n % 2 == 1 ) {
+ median = intlist_get( tmp, tmp->n / 2 );
+ } else {
+ m1 = intlist_get( tmp, tmp->n / 2 );
+ m2 = intlist_get( tmp, tmp->n / 2 - 1);
+ median = ( m1 + m2 ) / 2.0;
+ }
+
+ intlist_delete( tmp );
+
+ return median;
+}
+
+float
+intlist_mean( intlist *il )
+{
+ float sum = 0.0;
+ int i;
+
+ assert( il );
+
+ if ( il->n==0 ) return 0.0;
+
+ for ( i=0; i<il->n; ++i )
+ sum += intlist_get( il, i );
+
+ return sum / il->n;
+}