The C Containers library

J

jacob navia

A new addition to the C Containers library: Value arrays (ValArrays)

Value arrays are a group of containers that store the basic types of the
language: short, int, long, long long, float, double, long double
and have some specialized operations that should be done in hardware
when the underlying CPU allows it. The objective here is to simplify the
vector interface replacing the void * with the concrete type that these
arrays hold.

This is a very rich interface with all operations necessary to
realize any general purpose computation fast and efficiently.

ValArrays implement also "Slices", patterned exactly like their
C++ counterparts but with a much easier interface:

You set a slice into the array with "SetSlice", and then all
operations will work ONLY in the selected slice obtaining the
same result as the C++

Array[Slice]

idiom.

Masks are also supported (but not yet fully implemented).

The implemented interface is already quite developed:

/***************************************************************
* ValArrays *
*****************************************************************/
typedef struct _ValArray ValArray;
typedef struct tagValArray {
size_t (*Size)(const ValArray *AL);
unsigned (*GetFlags)(const ValArray *AL);
unsigned (*SetFlags)(ValArray *AL,unsigned flags);
int (*Clear)(ValArray *AL);
int (*Contains)(ValArray *AL,ElementType data);
int (*Erase)(ValArray *AL,ElementType elem);
int (*Finalize)(ValArray *AL);
int (*Apply)(ValArray *AL,int (*Applyfn)(ElementType element,void *
arg),void *arg);
int (*Equal)(const ValArray *first, const ValArray *second);
ValArray *(*Copy)(ValArray *AL);
ErrorFunction (*SetErrorFunction)(ValArray *AL,ErrorFunction);
size_t (*Sizeof)(ValArray *AL);
Iterator *(*newIterator)(ValArray *AL);
int (*deleteIterator)(Iterator *);
int (*Save)(ValArray *AL,FILE *stream);
ValArray *(*Load)(FILE *stream);
size_t (*GetElementSize)(const ValArray *AL);

/* Sequential container specific fields */

int (*Add)(ValArray *AL,ElementType newval);
ElementType (*GetElement)(const ValArray *AL,size_t idx);
int (*PushBack)(ValArray *AL,ElementType data);
int (*PopBack)(ValArray *AL,ElementType *result);
int (*InsertAt)(ValArray *AL,size_t idx,ElementType newval);
int (*EraseAt)(ValArray *AL,size_t idx);
int (*ReplaceAt)(ValArray *AL,size_t idx,ElementType newval);
/* NO extra args */
int (*IndexOf)(ValArray *AL,ElementType data,size_t *result);

/* ValArray container specific fields */

int (*Insert)(ValArray *AL,ElementType);
int (*InsertIn)(ValArray *AL, size_t idx, ValArray *newData);
ValArray *(*IndexIn)(const ValArray *SC,const ValArraySize_t *AL);
size_t (*GetCapacity)(const ValArray *AL);
int (*SetCapacity)(ValArray *AL,size_t newCapacity);

CompareFunction (*SetCompareFunction)(ValArray *l,CompareFunction fn);
int (*Sort)(ValArray *AL);
ValArray *(*Create)(size_t startsize);
ValArray *(*CreateWithAllocator)(size_t startsize,
ContainerMemoryManager *allocator);
ValArray *(*Init)(ValArray *AL,size_t startsize);
int (*AddRange)(ValArray *AL,size_t n, const ElementType *newvalues);
ValArray *(*GetRange)(const ValArray *AL, size_t start, size_t end);
int (*CopyElement)(ValArray *AL,size_t idx,ElementType *outbuf);
ElementType *(*CopyTo)(ValArray *AL);
int (*Reverse)(ValArray *AL);
int (*Append)(ValArray *AL1, ValArray *AL2);
int (*Mismatch)(ValArray *a1, ValArray *a2,size_t *mismatch);
ContainerMemoryManager *(*GetAllocator)(ValArray *AL);
DestructorFunction (*SetDestructor)(ValArray *cb,DestructorFunction
fn);

/* ValArray specific functions */
ErrorFunction RaiseError; /* Error function */
int (*SumTo)(ValArray *left,const ValArray *right);
int (*SubtractFrom)(ValArray *left, const ValArray *right);
int (*MultiplyWith)(ValArray *left, const ValArray *right);
int (*DivideBy)(ValArray *left, const ValArray *right);
int (*SumScalarTo)(ValArray *left,ElementType right);
int (*SubtractScalarFrom)(ValArray *left, ElementType right);
int (*SubtractFromScalar)(ElementType left, ValArray *right);
int (*MultiplyWithScalar)(ValArray *left, ElementType right);
int (*DivideByScalar)(ValArray *left, ElementType right);
int (*DivideScalarBy)(ElementType left,ValArray *right);
Mask *(*CompareEqual)(const ValArray *left,const ValArray
*right,Mask *bytearray);
Mask *(*CompareEqualScalar)(const ValArray *left, const ElementType
right, Mask *bytearray);
char *(*Compare)(const ValArray *left, const ValArray *right,char
*bytearray);
char *(*CompareScalar)(const ValArray *left, const ElementType
right,char *bytearray);

ValArray *(*CreateSequence)(size_t n,ElementType start, ElementType
increment);
ValArray *(*InitializeWith)(size_t n, ElementType *data);
int (*Memset)(ValArray *dst,ElementType fillValue,size_t length);
int (*FillSequential)(ValArray *dst,size_t length,ElementType
start, ElementType increment);
int (*SetSlice)(ValArray *src,size_t start,size_t length,size_t
increment);
int (*ResetSlice)(ValArray *array);
int (*GetSlice)(ValArray *array,size_t *start,size_t *length,
size_t *increment);
ElementType (*Max)(const ValArray *src);
ElementType (*Min)(const ValArray *src);
int (*RotateLeft)(ValArray *AL, size_t n);
#ifdef __IS_UNSIGNED__
int (*Or)(ValArray *left, const ValArray *right);
int (*And)(ValArray *left, const ValArray *right);
int (*Xor)(ValArray *left, const ValArray *right);
int (*Not)(ValArray *left);
int (*BitLeftShift)(ValArray *data,int shift);
int (*BitRightShift)(ValArray *data, const int shift);
int (*OrScalar)(ValArray *left, const ElementType right);
int (*AndScalar)(ValArray *left, const ElementType right);
int (*XorScalar)(ValArray *left, const ElementType right);

#endif
#ifdef __IS_INTEGER__
int (*Mod)(ValArray *left,const ValArray *right);
int (*ModScalar)(ValArray *left,const ElementType right);
#else
char *(*FCompare)(const ValArray *left, const ValArray *right,char
*bytearray,ElementType tolerance);
int (*Inverse)(ValArray *src);
#endif
int (*ForEach)(ValArray *src,ElementType (*ApplyFn)(ElementType));
int (*Abs)(ValArray *src);
ElementType (*Accumulate)(ValArray *src);
ElementType (*Product)(ValArray *src);
} ValArrayInterface;


As you can see, some operations are implemented in some ValArrays,
others aren't. For instance the Inverse function doesn't make any sense
with integers, since for all integers bigger than one it will be zero.

The same with FCompare that compares using Knuth's proposal floating
point numbers using a fuzzy comparison that defines a range around each
number to allow for much finer precision in the comparison.

After more or less a year of work the project starts looking quite usable.

I have again posted this project in the French standardization
committee, and will start discussing it shortly.

jacob
 
B

Ben Bacarisse

As you can see, some operations are implemented in some ValArrays,
others aren't. For instance the Inverse function doesn't make any
sense with integers, since for all integers bigger than one it will be
zero.
Click to expand...

Multiplicative inverses exist for unsigned types in C. It may not make
any sense to implement them, but the concept is well defined.

<snip>
 
J

jacob navia

Le 23/04/11 13:56, Ben Bacarisse a écrit :
Multiplicative inverses exist for unsigned types in C. It may not make
any sense to implement them, but the concept is well defined.

<snip>
Click to expand...

Mmmm I do not understand at all. For all unsigned integers 0..N
where N == UNSIGNED_MAX

1/0 --> error division by zero
1/1 --> Trivial 1
1/(2...N) --> zero
 
B

Ben Bacarisse

jacob navia said:
Le 23/04/11 13:56, Ben Bacarisse a écrit :

Mmmm I do not understand at all. For all unsigned integers 0..N
where N == UNSIGNED_MAX

1/0 --> error division by zero
1/1 --> Trivial 1
1/(2...N) --> zero
Click to expand...

That's because integer division is not the inverse of integer
multiplication. The multiplicative inverse of an unsigned int u is an
unsigned int i such that u * i == 1. (For a type T that promotes, the
test would be (T)(u * i) == 1 otherwise multiplication is not closed.)
 
J

jacob navia

Le 23/04/11 14:49, Ben Bacarisse a écrit :
That's because integer division is not the inverse of integer
multiplication. The multiplicative inverse of an unsigned int u is an
unsigned int i such that u * i == 1. (For a type T that promotes, the
test would be (T)(u * i) == 1 otherwise multiplication is not closed.)
Click to expand...

Interesting.

So you mean if we have an integer n with

1 <= n <= UINT_MAX

There will be always an integer n' so that

n * n' == 1

??

After your message I researched a bit the algorithms for calculating it
and most say that "this algorithm will return the multiplicative inverse
if it exists"...

Should I implement that for ValArrayUINT/ValARrayULLong ? It looks quite
interesting, and the applications are mostly in cryptography. Maybe that
should go into a special crypto package.

I did find algorithms with an arbitrary base, but maybe you know of an
adaptation for base pow(2,32) / pow(2,64) ?

Thanks for your remark. Very interesting.

jacob
 
I

Ike Naar

That's because integer division is not the inverse of integer
multiplication. The multiplicative inverse of an unsigned int u is an
unsigned int i such that u * i == 1. (For a type T that promotes, the
test would be (T)(u * i) == 1 otherwise multiplication is not closed.)
Click to expand...

u has an inverse only if u and the modulus (UINT_MAX+1) are coprime.
For the typical case where UINT_MAX+1 is a power of two, an even number
has no inverse.
 
J

jacob navia

Le 23/04/11 20:08, Ike Naar a écrit :
u has an inverse only if u and the modulus (UINT_MAX+1) are coprime.
For the typical case where UINT_MAX+1 is a power of two, an even number
has no inverse.
Click to expand...

Do you know of a reference to code calculating that inverse?

jacob
 
K

Kai-Uwe Bux

jacob said:
Le 23/04/11 20:08, Ike Naar a écrit :

Do you know of a reference to code calculating that inverse?
Click to expand...

Google "extended Euclidean algorithm". The idea is that in computing the gcd
of two numbers n and m, you can simultaneously find two numbers x and y
satisfying

gcd = x*n + y*m

Now, if m = 2^N and n is odd, then gcd = 1 = x*n + y*2^N. Hence x is a
multiplicative inverse of n mod 2^N.


Best,

Kai-Uwe Bux
 
M

Michael Press

Ben Bacarisse said:
Multiplicative inverses exist for unsigned types in C. It may not make
any sense to implement them, but the concept is well defined.
Click to expand...

If the largest unsigned int is 3, what is the
multiplication table? The usual one has no inverse for 2.

0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
 
B

Ben Bacarisse

Michael Press said:
If the largest unsigned int is 3, what is the
multiplication table? The usual one has no inverse for 2.

0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
Click to expand...

Yes, only 1 and 3 have an inverse in this ring. As Ike has pointed out,
since all unsigned types will have size 2^n, no even number will have an
inverse in any unsigned C type.
 
B

Ben Bacarisse

jacob navia said:
Le 23/04/11 14:49, Ben Bacarisse a écrit :

Interesting.

So you mean if we have an integer n with

1 <= n <= UINT_MAX

There will be always an integer n' so that

n * n' == 1

??
Click to expand...

As pointed out by Ike, only for odd n.
After your message I researched a bit the algorithms for calculating it
and most say that "this algorithm will return the multiplicative inverse
if it exists"...

Should I implement that for ValArrayUINT/ValARrayULLong ? It looks quite
interesting, and the applications are mostly in cryptography. Maybe that
should go into a special crypto package.
Click to expand...

I doubt that it is worthwhile. I can't think of any other uses and the
cryptographic uses will typically use number systems larger than C's
built-in types and which will usually be a finite field (in which every
non-zero element has an inverse).
 
M

Michael Press

Ben Bacarisse said:
As pointed out by Ike, only for odd n.
Click to expand...

It is more complicated.
Z/nZ is the ring of integers modulo n.
(Z/nZ)^* is the group of units modulo n;
units being the elements with a multiplicative inverse.

If p is prime then (Z/pZ)^* = Z/pZ - {0}.
|(Z/nZ)^*| = phi(n) = number of integers a <= n and gcd(a,n) = 1.

If n = 15, (Z/nZ)^* = {1, 2, 4, 7, 8, 11, 13, 14}.
7 * 13 = 1. 3 * 10 = 0.
 
I

Ike Naar

It is more complicated.
Z/nZ is the ring of integers modulo n.
(Z/nZ)^* is the group of units modulo n;
units being the elements with a multiplicative inverse.

If p is prime then (Z/pZ)^* = Z/pZ - {0}.
|(Z/nZ)^*| = phi(n) = number of integers a <= n and gcd(a,n) = 1.

If n = 15, (Z/nZ)^* = {1, 2, 4, 7, 8, 11, 13, 14}.
7 * 13 = 1. 3 * 10 = 0.
Click to expand...

I think Ben was referring to the situation where UNIT_MAX+1
is a power of two (which is typical for most C implementations).
 
B

Ben Bacarisse

Ike Naar said:
I think Ben was referring to the situation where UNIT_MAX+1
is a power of two (which is typical for most C implementations).
Click to expand...

Yes, I was answering Jacob's question about 1 <= n <= UINT_MAX. The
fact that UINT_MAX+1 is a power of two is more than typical. I don't
think it can be otherwise on a conforming C implementation.
 
S

Seebs

Google "extended Euclidean algorithm". The idea is that in computing the gcd
of two numbers n and m, you can simultaneously find two numbers x and y
satisfying

gcd = x*n + y*m

Now, if m = 2^N and n is odd, then gcd = 1 = x*n + y*2^N. Hence x is a
multiplicative inverse of n mod 2^N.
Click to expand...

Once upon a time, I had the idea of trying to write a GNU-style gcd utility.
Among the features were to be:
* calculation of greatest common divisors (obviously)
* calculation of least common multiples
* calculation of least common divisors
* calculation of greatest common multiples
* network support allowing a client/server setup
* the option of specifying more than one port, in which
case the network port used would be their greatest common
divisor
* a mail reader, because every GNU utility needs one

-s
 
J

jacob navia

Le 24/04/11 13:30, Seebs a écrit :
Once upon a time, I had the idea of trying to write a GNU-style gcd utility.
Among the features were to be:
* calculation of greatest common divisors (obviously)
* calculation of least common multiples
* calculation of least common divisors
* calculation of greatest common multiples
* network support allowing a client/server setup
* the option of specifying more than one port, in which
case the network port used would be their greatest common
divisor
* a mail reader, because every GNU utility needs one

-s
Click to expand...

That was the WHOLE contribution of Seebs to this discussion.

It shows his great intellectual capacity and the level at which the
"regulars" move...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

The container abstraction and parallel programming 38
A container library in C Part 4. The arraylist container 10
Engineering a list container. Part 1. 71
A container library in C. Part 1: Header file 14
arraylist.c 3
containers.h 0
A container library in C: Part 3. List container implementation 5
How to use PDF-lib and how to center each line of texts on the page? 1

Members online

No members online now.
Total: 26 (members: 0, guests: 26)
Robots: 309

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,007
Latest member
obedient dusk

Latest Threads

Top