My Project  debian-1:4.1.1-p2+ds-4build3
Data Structures | Functions | Variables
sbuckets.cc File Reference
#include "omalloc/omalloc.h"
#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. More...
 
bool sIsEmpty (const sBucket_pt bucket)
 Test whether bucket is empty!? More...
 
sBucket_pt sBucketCopy (const sBucket_pt bucket)
 Copy sBucket non-intrusive!!! More...
 
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! More...
 
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! More...
 
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. More...
 
poly sBucketSortAdd (poly p, const ring r)
 Sorts p with bucketSort: p may have equal monomials. More...
 

Variables

static omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))
 

Data Structure Documentation

◆ sBucketPoly

class sBucketPoly

Definition at line 26 of file sbuckets.cc.

Data Fields
long length
poly p

◆ sBucket

class sBucket

Definition at line 33 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 176 of file sbuckets.cc.

177 {
178  assume(bucket != NULL);
179  assume(1 == pLength(p));
180 
181  int length = 1;
182 
183  int i = 0; //SI_LOG2(length);
184 
185  while (bucket->buckets[i].p != NULL)
186  {
187  int shorter;
188  p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p,
189  shorter, bucket->bucket_ring);
190  length+=bucket->buckets[i].length-shorter;
191  bucket->buckets[i].p = NULL;
192  bucket->buckets[i].length = 0;
193  if (p==NULL)
194  {
195  if (i > bucket->max_bucket) bucket->max_bucket = i;
196  return;
197  }
198  i = SI_LOG2(length);
199  }
200 
201  bucket->buckets[i].p = p;
202  bucket->buckets[i].length = length;
203  if (i > bucket->max_bucket) bucket->max_bucket = i;
204 }

◆ sBucket_Add_p()

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

adds poly p to bucket destroys p!

Definition at line 206 of file sbuckets.cc.

207 {
208  assume(bucket != NULL);
209  assume(length <= 0 || length == pLength(p));
210 
211  if (p == NULL) return;
212  if (length <= 0) length = pLength(p);
213 
214  int i = SI_LOG2(length);
215 
216  while (bucket->buckets[i].p != NULL)
217  {
218  int shorter;
219  p = bucket->bucket_ring->p_Procs->p_Add_q(p, bucket->buckets[i].p, shorter,
220  bucket->bucket_ring);
221  length+= bucket->buckets[i].length-shorter;
222  bucket->buckets[i].p = NULL;
223  bucket->buckets[i].length = 0;
224  if (p==NULL)
225  {
226  if (i > bucket->max_bucket) bucket->max_bucket = i;
227  return;
228  }
229  i = SI_LOG2(length);
230  }
231 
232  bucket->buckets[i].p = p;
233  bucket->buckets[i].length = length;
234  if (i > bucket->max_bucket) bucket->max_bucket = i;
235 }

◆ sBucket_Merge_m()

void sBucket_Merge_m ( sBucket_pt  bucket,
poly  p 
)

Definition at line 130 of file sbuckets.cc.

131 {
132  assume(p != NULL && pNext(p) == NULL);
133  int length = 1;
134  int i = 0;
135 
136  while (bucket->buckets[i].p != NULL)
137  {
138  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
139  length += bucket->buckets[i].length;
140  bucket->buckets[i].p = NULL;
141  bucket->buckets[i].length = 0;
142  i++;
143  assume(SI_LOG2(length) == i);
144  }
145 
146  bucket->buckets[i].p = p;
147  bucket->buckets[i].length = length;
148  if (i > bucket->max_bucket) bucket->max_bucket = i;
149 }

◆ 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 151 of file sbuckets.cc.

152 {
153  assume(bucket != NULL);
154  assume(length <= 0 || length == pLength(p));
155 
156  if (p == NULL) return;
157  if (length <= 0) length = pLength(p);
158 
159  int i = SI_LOG2(length);
160 
161  while (bucket->buckets[i].p != NULL)
162  {
163  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
164  length += bucket->buckets[i].length;
165  bucket->buckets[i].p = NULL;
166  bucket->buckets[i].length = 0;
167  i++;
168  assume(SI_LOG2(length) == i);
169  }
170 
171  bucket->buckets[i].p = p;
172  bucket->buckets[i].length = length;
173  if (i > bucket->max_bucket) bucket->max_bucket = i;
174 }

◆ sBucketClearAdd()

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

Definition at line 277 of file sbuckets.cc.

278 {
279  poly pr = NULL;
280  int lr = 0;
281  int i = 0;
282 
283  while (bucket->buckets[i].p == NULL)
284  {
285  assume( bucket->buckets[i].length == 0 );
286  i++;
287  if (i > bucket->max_bucket) goto done;
288  }
289 
290  pr = bucket->buckets[i].p;
291  lr = bucket->buckets[i].length;
292 
293  assume( pr != NULL && (lr > 0) );
294 
295  bucket->buckets[i].p = NULL;
296  bucket->buckets[i].length = 0;
297  i++;
298 
299  while (i <= bucket->max_bucket)
300  {
301  if (bucket->buckets[i].p != NULL)
302  {
303  assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
304 
305  pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
306  bucket->bucket_ring);
307 
308  bucket->buckets[i].p = NULL;
309  bucket->buckets[i].length = 0;
310  }
311 
312  assume( bucket->buckets[i].p == NULL );
313  assume( bucket->buckets[i].length == 0 );
314  i++;
315  }
316 
317 done:
318 
319  *p = pr;
320  *length = lr;
321 
322  bucket->max_bucket = 0;
323 
324  assume( sIsEmpty(bucket) );
325 }

◆ sBucketClearMerge()

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

Definition at line 239 of file sbuckets.cc.

240 {
241  poly pr = NULL;
242  int lr = 0;
243  int i = 0;
244 
245  while (bucket->buckets[i].p == NULL)
246  {
247  i++;
248  if (i > bucket->max_bucket) goto done;
249  }
250 
251  pr = bucket->buckets[i].p;
252  lr = bucket->buckets[i].length;
253  bucket->buckets[i].p = NULL;
254  bucket->buckets[i].length = 0;
255  i++;
256 
257  while (i <= bucket->max_bucket)
258  {
259  if (bucket->buckets[i].p != NULL)
260  {
261  pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
262  lr += bucket->buckets[i].length;
263  bucket->buckets[i].p = NULL;
264  bucket->buckets[i].length = 0;
265  }
266  i++;
267  }
268 
269  done:
270  *p = pr;
271  *length = lr;
272  bucket->max_bucket = 0;
273 }

◆ sBucketCopy()

sBucket_pt sBucketCopy ( const sBucket_pt  bucket)

Copy sBucket non-intrusive!!!

Definition at line 74 of file sbuckets.cc.

75 {
76  const ring r = bucket->bucket_ring;
77 
78  sBucket_pt newbucket = sBucketCreate(r);
79 
80  newbucket->max_bucket = bucket->max_bucket;
81 
82  for(int i = 0; i <= bucket->max_bucket; i++)
83  {
84  assume( i < (BIT_SIZEOF_LONG - 3) );
85  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
86 
87  newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
88  newbucket->buckets[i].length = bucket->buckets[i].length;
89 
90  assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
91  }
92 
93  return newbucket;
94 }

◆ sBucketCreate()

sBucket_pt sBucketCreate ( const ring  r)

Definition at line 99 of file sbuckets.cc.

100 {
102  bucket->bucket_ring = r;
103  return bucket;
104 }

◆ sBucketDeleteAndDestroy()

void sBucketDeleteAndDestroy ( sBucket_pt bucket_pt)

Definition at line 113 of file sbuckets.cc.

114 {
115  sBucket_pt bucket = *bucket_pt;
116  int i;
117  for (i=0; i<= bucket->max_bucket; i++)
118  {
119  p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
120  }
121  omFreeBin(bucket, sBucket_bin);
122  *bucket_pt = NULL;
123 }

◆ sBucketDestroy()

void sBucketDestroy ( sBucket_pt bucket)

Definition at line 106 of file sbuckets.cc.

107 {
108  assume(bucket != NULL);
109  omFreeBin(*bucket, sBucket_bin);
110  *bucket = NULL;
111 }

◆ sBucketGetRing()

ring sBucketGetRing ( const sBucket_pt  bucket)

Returns bucket ring.

Definition at line 50 of file sbuckets.cc.

51 { return bucket->bucket_ring; }

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

369 {
370 #ifndef SING_NDEBUG
371  int l_in = pLength(p);
372 #endif
373 
374  if (p == NULL || pNext(p) == NULL) return p;
375 
376  sBucket_pt bucket = sBucketCreate(r);
377  poly pn = pNext(p);
378 
379  do
380  {
381  pNext(p) = NULL;
382  sBucket_Add_m(bucket, p);
383  p = pn;
384  if (p == NULL) break;
385  pn = pNext(pn);
386  }
387  while (1);
388 
389  int l_dummy;
390  sBucketClearAdd(bucket, &pn, &l_dummy);
391  sBucketDestroy(&bucket);
392 
393  p_Test(pn, r);
394 #ifndef SING_NDEBUG
395  assume(l_dummy == pLength(pn));
396  assume(l_in >= l_dummy);
397 #endif
398  return pn;
399 }

◆ sBucketSortMerge()

poly sBucketSortMerge ( poly  p,
const ring  r 
)

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

Definition at line 334 of file sbuckets.cc.

335 {
336  if (p == NULL || pNext(p) == NULL) return p;
337 
338 #ifndef SING_NDEBUG
339  int l_in = pLength(p);
340 #endif
341  sBucket_pt bucket = sBucketCreate(r);
342  poly pn = pNext(p);
343 
344  do
345  {
346  pNext(p) = NULL;
347  sBucket_Merge_m(bucket, p);
348  p = pn;
349  if (p == NULL) break;
350  pn = pNext(pn);
351  }
352  while (1);
353 
354  int l_dummy;
355  sBucketClearMerge(bucket, &pn, &l_dummy);
356  sBucketDestroy(&bucket);
357 
358  p_Test(pn, r);
359  assume(l_dummy == pLength(pn));
360  assume(l_in == l_dummy);
361  return pn;
362 }

◆ sIsEmpty()

bool sIsEmpty ( const sBucket_pt  bucket)

Test whether bucket is empty!?

Definition at line 54 of file sbuckets.cc.

55 {
56  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
57  {
58  assume( i < (BIT_SIZEOF_LONG - 3) );
59  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
60 
61  if( bucket->buckets[i].p != NULL )
62  return false;
63 
64  if( bucket->buckets[i].length != 0 )
65  return false;
66  }
67 
68  return( bucket->max_bucket == 0 );
69 
70 }

Variable Documentation

◆ sBucket_bin

omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))
static

Definition at line 42 of file sbuckets.cc.

BIT_SIZEOF_LONG
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:78
sBucketClearMerge
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:239
p_Merge_q
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1158
sBucket_Add_m
void sBucket_Add_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:176
SI_LOG2
static int SI_LOG2(int v)
Definition: auxiliary.h:119
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
p_Test
#define p_Test(p, r)
Definition: p_polys.h:163
sBucket_bin
static omBin sBucket_bin
Definition: sbuckets.cc:42
omAlloc0Bin
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:192
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:812
i
int i
Definition: cfEzgcd.cc:125
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:99
sIsEmpty
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:54
sBucket_pt
sBucket * sBucket_pt
Definition: sbuckets.h:16
sBucket::bucket_ring
ring bucket_ring
Definition: sbuckets.cc:36
sBucket::max_bucket
long max_bucket
Definition: sbuckets.cc:37
sBucket
Definition: sbuckets.cc:34
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:857
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:892
sBucketPoly::length
long length
Definition: sbuckets.cc:38
sBucket_Merge_m
void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:130
sBucket::buckets
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:38
assume
#define assume(x)
Definition: mod2.h:390
NULL
#define NULL
Definition: omList.c:10
sBucketClearAdd
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:277
p
int p
Definition: cfModGcd.cc:4019
sBucketPoly::p
poly p
Definition: sbuckets.cc:37
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:106
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
pNext
#define pNext(p)
Definition: monomials.h:43