sbuckets.h File Reference

Go to the source code of this file.

Typedefs
typedef sBucket *	sBucket_pt
typedef polyrec *	poly

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

Typedef Documentation

typedef polyrec* poly

Definition at line 17 of file sbuckets.h.

typedef sBucket* sBucket_pt

Definition at line 16 of file sbuckets.h.

Function Documentation

void sBucket_Add_p	(	sBucket_pt	bucket,
		poly	p,
		int	lp
	)

adds poly p to bucket destroys p!

Definition at line 206 of file sbuckets.cc.

{
  assume(bucket != NULL);
  assume(length <= 0 || length == pLength(p));

  if (p == NULL) return;
  if (length <= 0) length = pLength(p);

  int i = LOG2(length);

  while (bucket->buckets[i].p != NULL)
  {
    p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
                bucket->bucket_ring);
    bucket->buckets[i].p = NULL;
    bucket->buckets[i].length = 0;
    if (p==NULL)
    {
      if (i > bucket->max_bucket) bucket->max_bucket = i;
      return;
    }
    i = LOG2(length);
  }

  bucket->buckets[i].p = p;
  bucket->buckets[i].length = length;
  if (i > bucket->max_bucket) bucket->max_bucket = i;
}

void sBucket_Merge_p	(	sBucket_pt	bucket,
		poly	p,
		int	lp
	)

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

Definition at line 181 of file sbuckets.cc.

{
  assume(bucket != NULL);
  assume(length <= 0 || length == pLength(p));

  if (p == NULL) return;
  if (length <= 0) length = pLength(p);

  int i = 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(LOG2(length) == i);
  }

  bucket->buckets[i].p = p;
  bucket->buckets[i].length = length;
  if (i > bucket->max_bucket) bucket->max_bucket = i;
}

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) );
}

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

sBucket_pt sBucketCopy

(

const sBucket_pt

bucket

)

Copy sBucket non-intrusive!!!

Definition at line 80 of file sbuckets.cc.

{
  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;
}

sBucket_pt sBucketCreate

(

ring

r

)

Definition at line 125 of file sbuckets.cc.

{
  sBucket_pt bucket = (sBucket_pt) omAlloc0Bin(sBucket_bin);
  bucket->bucket_ring = r;
  return bucket;
}

void sBucketDeleteAndDestroy

(

sBucket_pt *

bucket_pt

)

Definition at line 139 of file sbuckets.cc.

{
  sBucket_pt bucket = *bucket_pt;
  int i;
  for (i=0; i<= bucket->max_bucket; i++)
  {

    if (bucket->buckets[i].p != NULL)
    {
      p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
    }
  }
  omFreeBin(bucket, sBucket_bin);
  *bucket_pt = NULL;
}

void sBucketDestroy

(

sBucket_pt *

bucket

)

Definition at line 132 of file sbuckets.cc.

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

void sBucketDestroyAdd ( sBucket_pt  bucket, poly *  p, int *  length  )

inline

Definition at line 72 of file sbuckets.h.

{
  sBucketClearAdd(bucket, p, length);
  sBucketDestroy(&bucket);
}

void sBucketDestroyMerge ( sBucket_pt  bucket, poly *  p, int *  length  )

inline

Definition at line 65 of file sbuckets.h.

{
  sBucketClearMerge(bucket, p, length);
  sBucketDestroy(&bucket);
}

ring sBucketGetRing

(

const sBucket_pt

bucket

)

Returns bucket ring.

Definition at line 56 of file sbuckets.cc.

{ return bucket->bucket_ring; }

poly sBucketSortAdd	(	poly	p,
		ring	r
	)

Sorts p with bucketSort: p may have equal monomials.

Definition at line 369 of file sbuckets.cc.

{
#ifdef HAVE_ASSUME
  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_p(bucket, p, 1);
    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);
#ifdef HAVE_ASSUME
  assume(l_dummy == pLength(pn));
  assume(l_in >= l_dummy);
#endif
  return pn;
}

poly sBucketSortMerge	(	poly	p,
		ring	r
	)

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

Definition at line 332 of file sbuckets.cc.

{
#ifdef HAVE_ASSUME
  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_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);
#ifdef HAVE_ASSUME
  assume(l_dummy == pLength(pn));
  assume(l_in == l_dummy);
#endif
  return pn;
}

bool sIsEmpty

(

const sBucket_pt

bucket

)

Test whether bucket is empty!?

Definition at line 60 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 );

}