Loading...
Searching...
No Matches
sbuckets.cc File Reference
`#include "misc/auxiliary.h"`
`#include "polys/sbuckets.h"`
`#include "polys/monomials/ring.h"`
`#include "polys/monomials/p_polys.h"`

Go to the source code of this file.

## Data Structures

class | sBucketPoly
class | sBucket

## Functions

ring | sBucketGetRing (const sBucket_pt bucket)
| Returns bucket ring.
bool | sIsEmpty (const sBucket_pt bucket)
| Test whether bucket is empty!?
sBucket_pt | sBucketCopy (const sBucket_pt bucket)
| Copy sBucket non-intrusive!!!
sBucket_pt | sBucketCreate (const ring r)
void | sBucketDestroy (sBucket_pt *bucket)
void | sBucketDeleteAndDestroy (sBucket_pt *bucket_pt)
void | sBucket_Merge_m (sBucket_pt bucket, poly p)
void | sBucket_Merge_p (sBucket_pt bucket, poly p, int length)
| Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!
void | sBucket_Add_m (sBucket_pt bucket, poly p)
void | sBucket_Add_p (sBucket_pt bucket, poly p, int length)
| adds poly p to bucket destroys p!
void | sBucketClearMerge (sBucket_pt bucket, poly *p, int *length)
void | sBucketClearAdd (sBucket_pt bucket, poly *p, int *length)
poly | sBucketSortMerge (poly p, const ring r)
| Sorts p with bucketSort: assumes all monomials of p are different.
poly | sBucketSortAdd (poly p, const ring r)
| Sorts p with bucketSort: p may have equal monomials.
void | sBucketCanonicalize (sBucket_pt bucket)
poly | sBucketPeek (sBucket_pt b)
char * | sBucketString (sBucket_pt bucket)
void | sBucketPrint (sBucket_pt bucket)

## Variables

STATIC_VAR omBin | sBucket_bin = omGetSpecBin(sizeof(sBucket))

## Data Structure Documentation

## sBucketPoly

class sBucketPoly

Definition at line 22 of file sbuckets.cc.

Data Fields
long | length |
poly | p |

## sBucket

class sBucket

Definition at line 29 of file sbuckets.cc.

Data Fields
ring | bucket_ring |
sBucketPoly | buckets[BIT_SIZEOF_LONG - 3] |
long | max_bucket |

## Function Documentation

## sBucket_Add_m()

void sBucket_Add_m | ( | sBucket_pt | bucket,
|  | poly | p )

Definition at line 173 of file sbuckets.cc.

{
assume(bucket != NULL);
assume(1 == pLength(p));
int length = 1;
int i = 0; //SI_LOG2(length);
while (bucket->buckets[i].p != NULL)
{
int shorter;
p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
shorter, bucket->bucket_ring);
length+=bucket->buckets[i].length-shorter;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
if (p==NULL)
{
if (i > bucket->max_bucket) bucket->max_bucket = i;
return;
}
i = SI_LOG2(length);
}
bucket->buckets[i].p = p;
bucket->buckets[i].length = length;
if (i > bucket->max_bucket) bucket->max_bucket = i;
}
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
assume
#define assume(x)
Definition mod2.h:389
NULL
#define NULL
Definition omList.c:12
pLength
static int pLength(poly a)
Definition p_polys.h:190
sBucketPoly::length
long length
Definition sbuckets.cc:26
sBucket::max_bucket
long max_bucket
Definition sbuckets.cc:33
sBucket::buckets
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition sbuckets.cc:34
sBucket::bucket_ring
ring bucket_ring
Definition sbuckets.cc:32
sBucketPoly::p
poly p
Definition sbuckets.cc:25
SI_LOG2
static int SI_LOG2(int v)
Definition si_log2.h:6

## sBucket_Add_p()

void sBucket_Add_p | ( | sBucket_pt | bucket,
|  | poly | p,
|  | int | length )

adds poly p to bucket destroys p!

Definition at line 203 of file sbuckets.cc.

{
assume(bucket != NULL);
assume(length <= 0 || length == (int)pLength(p));
if (p == NULL) return;
p_Test(p,bucket->bucket_ring);
if (length <= 0) length = (int)pLength(p);
int i = SI_LOG2(length);
while (bucket->buckets[i].p != NULL)
{
int shorter;
p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
bucket->bucket_ring);
length+= bucket->buckets[i].length-shorter;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
if (p==NULL)
{
if (i > bucket->max_bucket) bucket->max_bucket = i;
return;
}
i = SI_LOG2(length);
}
bucket->buckets[i].p = p;
bucket->buckets[i].length = length;
if (i > bucket->max_bucket) bucket->max_bucket = i;
}
p_Test
#define p_Test(p, r)
Definition p_polys.h:161

## sBucket_Merge_m()

void sBucket_Merge_m | ( | sBucket_pt | bucket,
|  | poly | p )

Definition at line 127 of file sbuckets.cc.

{
assume(p != NULL && pNext(p) == NULL);
int length = 1;
int i = 0;
while (bucket->buckets[i].p != NULL)
{
p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
length += bucket->buckets[i].length;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
i++;
assume(SI_LOG2(length) == i);
}
bucket->buckets[i].p = p;
bucket->buckets[i].length = length;
if (i > bucket->max_bucket) bucket->max_bucket = i;
}
pNext
#define pNext(p)
Definition monomials.h:36
p_Merge_q
static poly p_Merge_q(poly p, poly q, const ring r)
Definition p_polys.h:1233

## sBucket_Merge_p()

void sBucket_Merge_p | ( | sBucket_pt | bucket,
|  | poly | p,
|  | int | length )

Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!

Definition at line 148 of file sbuckets.cc.

{
assume(bucket != NULL);
assume(length <= 0 || length == (int)pLength(p));
if (p == NULL) return;
if (length <= 0) length = pLength(p);
int i = SI_LOG2(length);
while (bucket->buckets[i].p != NULL)
{
p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
length += bucket->buckets[i].length;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
i++;
assume(SI_LOG2(length) == i);
}
bucket->buckets[i].p = p;
bucket->buckets[i].length = length;
if (i > bucket->max_bucket) bucket->max_bucket = i;
}

## sBucketCanonicalize()

void sBucketCanonicalize | ( | sBucket_pt | bucket | ) |

Definition at line 401 of file sbuckets.cc.

{
poly pr = NULL;
int lr = 0;
int i = 0;
while (bucket->buckets[i].p == NULL)
{
assume( bucket->buckets[i].length == 0 );
i++;
if (i > bucket->max_bucket) goto done;
}
pr = bucket->buckets[i].p;
lr = bucket->buckets[i].length;
assume( pr != NULL && (lr > 0) );
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
i++;
while (i <= bucket->max_bucket)
{
if (bucket->buckets[i].p != NULL)
{
p_Test(pr,bucket->bucket_ring);
assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
p_Test(bucket->buckets[i].p,bucket->bucket_ring);
//pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
// bucket->bucket_ring);
pr = p_Add_q(pr, bucket->buckets[i].p, bucket->bucket_ring);
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
}
assume( bucket->buckets[i].p == NULL );
assume( bucket->buckets[i].length == 0 );
i++;
}
done:
lr=pLength(pr);
if (pr!=NULL)
{
i = SI_LOG2(lr);
bucket->buckets[i].p = pr;
bucket->buckets[i].length = lr;
bucket->max_bucket = i;
}
}
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938

## sBucketClearAdd()

void sBucketClearAdd | ( | sBucket_pt | bucket,
|  | poly * | p,
|  | int * | length )

Definition at line 275 of file sbuckets.cc.

{
poly pr = NULL;
int lr = 0;
int i = 0;
while (bucket->buckets[i].p == NULL)
{
assume( bucket->buckets[i].length == 0 );
i++;
if (i > bucket->max_bucket) goto done;
}
pr = bucket->buckets[i].p;
lr = bucket->buckets[i].length;
assume( pr != NULL && (lr > 0) );
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
i++;
while (i <= bucket->max_bucket)
{
if (bucket->buckets[i].p != NULL)
{
assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
bucket->bucket_ring);
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
}
assume( bucket->buckets[i].p == NULL );
assume( bucket->buckets[i].length == 0 );
i++;
}
done:
*p = pr;
*length = lr;
bucket->max_bucket = 0;
assume( sIsEmpty(bucket) );
}
sIsEmpty
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition sbuckets.cc:50

## sBucketClearMerge()

void sBucketClearMerge | ( | sBucket_pt | bucket,
|  | poly * | p,
|  | int * | length )

Definition at line 237 of file sbuckets.cc.

{
poly pr = NULL;
int lr = 0;
int i = 0;
while (bucket->buckets[i].p == NULL)
{
i++;
if (i > bucket->max_bucket) goto done;
}
pr = bucket->buckets[i].p;
lr = bucket->buckets[i].length;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
i++;
while (i <= bucket->max_bucket)
{
if (bucket->buckets[i].p != NULL)
{
pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
lr += bucket->buckets[i].length;
bucket->buckets[i].p = NULL;
bucket->buckets[i].length = 0;
}
i++;
}
done:
*p = pr;
*length = lr;
bucket->max_bucket = 0;
}

## sBucketCopy()

sBucket_pt sBucketCopy | ( | const sBucket_pt | bucket | ) |

Copy sBucket non-intrusive!!!

Definition at line 70 of file sbuckets.cc.

{
sBucketCanonicalize(bucket);
const ring r = bucket->bucket_ring;
sBucket_pt newbucket = sBucketCreate(r);
newbucket->max_bucket = bucket->max_bucket;
for(int i = 0; i <= bucket->max_bucket; i++)
{
assume( i < (BIT_SIZEOF_LONG - 3) );
assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
newbucket->buckets[i].length = bucket->buckets[i].length;
assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
}
return newbucket;
}
BIT_SIZEOF_LONG
#define BIT_SIZEOF_LONG
Definition auxiliary.h:80
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848
sBucketCanonicalize
void sBucketCanonicalize(sBucket_pt bucket)
Definition sbuckets.cc:401
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition sbuckets.cc:96
sBucket_pt
sBucket * sBucket_pt
Definition sbuckets.h:16

## sBucketCreate()

sBucket_pt sBucketCreate | ( | const ring | r | ) |

Definition at line 96 of file sbuckets.cc.

{
sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
bucket->bucket_ring = r;
return bucket;
}
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition omAllocDecl.h:206
sBucket_bin
STATIC_VAR omBin sBucket_bin
Definition sbuckets.cc:38

## sBucketDeleteAndDestroy()

void sBucketDeleteAndDestroy | ( | sBucket_pt * | bucket_pt | ) |

Definition at line 110 of file sbuckets.cc.

{
sBucket_pt bucket = *bucket_pt;
int i;
for (i=0; i<= bucket->max_bucket; i++)
{
p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
}
omFreeBin(bucket, sBucket_bin);
*bucket_pt = NULL;
}
omFreeBin
#define omFreeBin(addr, bin)
Definition omAllocDecl.h:259
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903

## sBucketDestroy()

void sBucketDestroy | ( | sBucket_pt * | bucket | ) |

Definition at line 103 of file sbuckets.cc.

{
assume(bucket != NULL);
omFreeBin(*bucket, sBucket_bin);
*bucket = NULL;
}

## sBucketGetRing()

ring sBucketGetRing | ( | const sBucket_pt | bucket | ) |

Returns bucket ring.

Definition at line 46 of file sbuckets.cc.

{ return bucket->bucket_ring; }

## sBucketPeek()

poly sBucketPeek | ( | sBucket_pt | b | ) |

Definition at line 455 of file sbuckets.cc.

{
sBucketCanonicalize(b);
return b->buckets[b->max_bucket].p;
}
b
CanonicalForm b
Definition cfModGcd.cc:4111

## sBucketPrint()

void sBucketPrint | ( | sBucket_pt | bucket | ) |

Definition at line 466 of file sbuckets.cc.

{
p_Write0(sBucketPeek(bucket),sBucketGetRing(bucket));
}
p_Write0
void p_Write0(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:332
sBucketPeek
poly sBucketPeek(sBucket_pt b)
Definition sbuckets.cc:455
sBucketGetRing
ring sBucketGetRing(const sBucket_pt bucket)
Returns bucket ring.
Definition sbuckets.cc:46

## sBucketSortAdd()

poly sBucketSortAdd | ( | poly | p,
|  | const ring | r )

Sorts p with bucketSort: p may have equal monomials.

Definition at line 368 of file sbuckets.cc.

{
#ifndef SING_NDEBUG
int l_in = pLength(p);
#endif
if (p == NULL || pNext(p) == NULL) return p;
sBucket_pt bucket = sBucketCreate(r);
poly pn = pNext(p);
do
{
pNext(p) = NULL;
sBucket_Add_m(bucket, p);
p = pn;
if (p == NULL) break;
pn = pNext(pn);
}
while (1);
int l_dummy;
sBucketClearAdd(bucket, &pn, &l_dummy);
sBucketDestroy(&bucket);
p_Test(pn, r);
#ifndef SING_NDEBUG
assume(l_dummy == (int)pLength(pn));
assume(l_in >= l_dummy);
#endif
return pn;
}
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition sbuckets.cc:103
sBucket_Add_m
void sBucket_Add_m(sBucket_pt bucket, poly p)
Definition sbuckets.cc:173
sBucketClearAdd
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition sbuckets.cc:275

## sBucketSortMerge()

poly sBucketSortMerge | ( | poly | p,
|  | const ring | r )

Sorts p with bucketSort: assumes all monomials of p are different.

Definition at line 332 of file sbuckets.cc.

{
if (p == NULL || pNext(p) == NULL) return p;
#ifndef SING_NDEBUG
int l_in = pLength(p);
#endif
sBucket_pt bucket = sBucketCreate(r);
poly pn = pNext(p);
do
{
pNext(p) = NULL;
sBucket_Merge_m(bucket, p);
p = pn;
if (p == NULL) break;
pn = pNext(pn);
}
while (1);
int l_dummy;
sBucketClearMerge(bucket, &pn, &l_dummy);
sBucketDestroy(&bucket);
p_Test(pn, r);
assume(l_dummy == (int)pLength(pn));
#ifndef SING_NDEBUG
assume(l_in == l_dummy);
#endif
return pn;
}
sBucketClearMerge
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition sbuckets.cc:237
sBucket_Merge_m
void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition sbuckets.cc:127

## sBucketString()

char * sBucketString | ( | sBucket_pt | bucket | ) |

Definition at line 461 of file sbuckets.cc.

{
return (p_String(sBucketPeek(bucket),sBucketGetRing(bucket)));
}
p_String
char * p_String(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:322

## sIsEmpty()

bool sIsEmpty | ( | const sBucket_pt | bucket | ) |

Test whether bucket is empty!?

Definition at line 50 of file sbuckets.cc.

{
for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
{
assume( i < (BIT_SIZEOF_LONG - 3) );
assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
if( bucket->buckets[i].p != NULL )
return false;
if( bucket->buckets[i].length != 0 )
return false;
}
return( bucket->max_bucket == 0 );
}

## Variable Documentation

## sBucket_bin

STATIC_VAR omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))

Definition at line 38 of file sbuckets.cc.