Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > The C Containers library

Reply
Thread Tools

The C Containers library

 
 
jacob navia
Guest
Posts: n/a
 
      04-23-2011
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
 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      04-23-2011
Sorry forgot to give the URL

https://code.google.com/p/ccl/
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-23-2011
jacob navia <(E-Mail Removed)> writes:

<snip>
> 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.


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

<snip>
--
Ben.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      04-23-2011
Le 23/04/11 13:56, Ben Bacarisse a écrit :
> jacob navia<(E-Mail Removed)> writes:
>
> <snip>
>> 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.

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


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

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-23-2011
jacob navia <(E-Mail Removed)> writes:

> Le 23/04/11 13:56, Ben Bacarisse a écrit :
>> jacob navia<(E-Mail Removed)> writes:
>>
>> <snip>
>>> 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.

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

>
> 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


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.)

--
Ben.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      04-23-2011
Le 23/04/11 14:49, Ben Bacarisse a écrit :
> jacob navia<(E-Mail Removed)> writes:
>
>> Le 23/04/11 13:56, Ben Bacarisse a écrit :
>>> jacob navia<(E-Mail Removed)> writes:
>>>
>>> <snip>
>>>> 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.
>>>
>>> Multiplicative inverses exist for unsigned types in C. It may not make
>>> any sense to implement them, but the concept is well defined.
>>>
>>> <snip>

>>
>> 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

>
> 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.)
>


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
 
Reply With Quote
 
Ike Naar
Guest
Posts: n/a
 
      04-23-2011
On 2011-04-23, Ben Bacarisse <(E-Mail Removed)> wrote:
> 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.)


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.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      04-23-2011
Le 23/04/11 20:08, Ike Naar a écrit :
> On 2011-04-23, Ben Bacarisse<(E-Mail Removed)> wrote:
>> 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.)

>
> 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.


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

jacob
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-23-2011
jacob navia wrote:

> Le 23/04/11 20:08, Ike Naar a écrit :
>> On 2011-04-23, Ben Bacarisse<(E-Mail Removed)> wrote:
>>> 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.)

>>
>> 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.

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


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
 
Reply With Quote
 
Ike Naar
Guest
Posts: n/a
 
      04-23-2011
On 2011-04-23, jacob navia <(E-Mail Removed)> wrote:
> Do you know of a reference to code calculating that inverse?


http://en.wikipedia.org/wiki/Extende...dean_algorithm
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Are sequence containers not a subset of general containers? Sebastian Mach C++ 5 10-06-2012 07:54 PM
C library containing implementations of associative containers. Morten C Programming 3 05-07-2008 02:24 PM
Containers of iterators vs. containers of references clark.coleman@att.net C++ 7 01-25-2008 01:37 PM
Library exposing STL containers Bob C++ 2 07-26-2006 02:04 AM
Questions about destructors on std library containers Ross Boylan C++ 12 02-13-2004 03:03 AM



Advertisments