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...
 
static int LOG2 (int i)
 
sBucket_pt sBucketCreate (const ring r)
 
void sBucketDestroy (sBucket_pt *bucket)
 
void sBucketDeleteAndDestroy (sBucket_pt *bucket_pt)
 
static 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_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 27 of file sbuckets.cc.

Data Fields
long length
poly p

§ sBucket

class sBucket

Definition at line 34 of file sbuckets.cc.

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

Function Documentation

§ LOG2()

static int LOG2 ( int  i)
inlinestatic

Definition at line 101 of file sbuckets.cc.

102 {
103  assume (i > 0);
104  int j = 0;
105 
106  do
107  {
108  i = i >> 1;
109  if (i == 0) return j;
110  j++;
111  }
112  while (1);
113 
114  return j;
115 }
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123

§ sBucket_Add_p()

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

adds poly p to bucket destroys p!

Definition at line 201 of file sbuckets.cc.

202 {
203  assume(bucket != NULL);
204  assume(length <= 0 || length == pLength(p));
205 
206  if (p == NULL) return;
207  if (length <= 0) length = pLength(p);
208 
209  int i = LOG2(length);
210 
211  while (bucket->buckets[i].p != NULL)
212  {
213  p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
214  bucket->bucket_ring);
215  bucket->buckets[i].p = NULL;
216  bucket->buckets[i].length = 0;
217  if (p==NULL)
218  {
219  if (i > bucket->max_bucket) bucket->max_bucket = i;
220  return;
221  }
222  i = LOG2(length);
223  }
224 
225  bucket->buckets[i].p = p;
226  bucket->buckets[i].length = length;
227  if (i > bucket->max_bucket) bucket->max_bucket = i;
228 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
static int LOG2(int i)
Definition: sbuckets.cc:101
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
ring bucket_ring
Definition: sbuckets.cc:37
#define NULL
Definition: omList.c:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877

§ sBucket_Merge_m()

static void sBucket_Merge_m ( sBucket_pt  bucket,
poly  p 
)
static

Definition at line 155 of file sbuckets.cc.

156 {
157  assume(p != NULL && pNext(p) == NULL);
158  int length = 1;
159  int i = 0;
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(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 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
static int LOG2(int i)
Definition: sbuckets.cc:101
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:37
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135
#define pNext(p)
Definition: monomials.h:43

§ 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 176 of file sbuckets.cc.

177 {
178  assume(bucket != NULL);
179  assume(length <= 0 || length == pLength(p));
180 
181  if (p == NULL) return;
182  if (length <= 0) length = pLength(p);
183 
184  int i = LOG2(length);
185 
186  while (bucket->buckets[i].p != NULL)
187  {
188  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
189  length += bucket->buckets[i].length;
190  bucket->buckets[i].p = NULL;
191  bucket->buckets[i].length = 0;
192  i++;
193  assume(LOG2(length) == i);
194  }
195 
196  bucket->buckets[i].p = p;
197  bucket->buckets[i].length = length;
198  if (i > bucket->max_bucket) bucket->max_bucket = i;
199 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
static int LOG2(int i)
Definition: sbuckets.cc:101
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
ring bucket_ring
Definition: sbuckets.cc:37
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135

§ sBucketClearAdd()

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

Definition at line 270 of file sbuckets.cc.

271 {
272  poly pr = NULL;
273  int lr = 0;
274  int i = 0;
275 
276  while (bucket->buckets[i].p == NULL)
277  {
278  assume( bucket->buckets[i].length == 0 );
279  i++;
280  if (i > bucket->max_bucket) goto done;
281  }
282 
283  pr = bucket->buckets[i].p;
284  lr = bucket->buckets[i].length;
285 
286  assume( pr != NULL && (lr > 0) );
287 
288  bucket->buckets[i].p = NULL;
289  bucket->buckets[i].length = 0;
290  i++;
291 
292  while (i <= bucket->max_bucket)
293  {
294  if (bucket->buckets[i].p != NULL)
295  {
296  assume( bucket->buckets[i].length == pLength(bucket->buckets[i].p) );
297 
298  pr = p_Add_q(pr, bucket->buckets[i].p, lr, bucket->buckets[i].length,
299  bucket->bucket_ring);
300 
301  bucket->buckets[i].p = NULL;
302  bucket->buckets[i].length = 0;
303  }
304 
305  assume( bucket->buckets[i].p == NULL );
306  assume( bucket->buckets[i].length == 0 );
307  i++;
308  }
309 
310 done:
311 
312  *p = pr;
313  *length = lr;
314 
315  bucket->max_bucket = 0;
316 
317  assume( sIsEmpty(bucket) );
318 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
ring bucket_ring
Definition: sbuckets.cc:37
#define NULL
Definition: omList.c:10
bool sIsEmpty(const sBucket_pt bucket)
Test whether bucket is empty!?
Definition: sbuckets.cc:55
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877

§ sBucketClearMerge()

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

Definition at line 232 of file sbuckets.cc.

233 {
234  poly pr = NULL;
235  int lr = 0;
236  int i = 0;
237 
238  while (bucket->buckets[i].p == NULL)
239  {
240  i++;
241  if (i > bucket->max_bucket) goto done;
242  }
243 
244  pr = bucket->buckets[i].p;
245  lr = bucket->buckets[i].length;
246  bucket->buckets[i].p = NULL;
247  bucket->buckets[i].length = 0;
248  i++;
249 
250  while (i <= bucket->max_bucket)
251  {
252  if (bucket->buckets[i].p != NULL)
253  {
254  pr = p_Merge_q(pr, bucket->buckets[i].p,bucket->bucket_ring);
255  lr += bucket->buckets[i].length;
256  bucket->buckets[i].p = NULL;
257  bucket->buckets[i].length = 0;
258  }
259  i++;
260  }
261 
262  done:
263  *p = pr;
264  *length = lr;
265  bucket->max_bucket = 0;
266 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:37
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1135
polyrec * poly
Definition: hilb.h:10

§ sBucketCopy()

sBucket_pt sBucketCopy ( const sBucket_pt  bucket)

Copy sBucket non-intrusive!!!

Definition at line 75 of file sbuckets.cc.

76 {
77  const ring r = bucket->bucket_ring;
78 
79  sBucket_pt newbucket = sBucketCreate(r);
80 
81  newbucket->max_bucket = bucket->max_bucket;
82 
83  for(int i = 0; i <= bucket->max_bucket; i++)
84  {
85  assume( i < (BIT_SIZEOF_LONG - 3) );
86  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
87 
88  newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
89  newbucket->buckets[i].length = bucket->buckets[i].length;
90 
91  assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
92  }
93 
94  return newbucket;
95 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:403
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
ring bucket_ring
Definition: sbuckets.cc:37
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:79

§ sBucketCreate()

sBucket_pt sBucketCreate ( const ring  r)

Definition at line 120 of file sbuckets.cc.

121 {
123  bucket->bucket_ring = r;
124  return bucket;
125 }
const ring r
Definition: syzextra.cc:208
P bucket
Definition: myNF.cc:79
static omBin sBucket_bin
Definition: sbuckets.cc:43
ring bucket_ring
Definition: sbuckets.cc:37
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
sBucket * sBucket_pt
Definition: summator.h:15

§ sBucketDeleteAndDestroy()

void sBucketDeleteAndDestroy ( sBucket_pt bucket_pt)

Definition at line 134 of file sbuckets.cc.

135 {
136  sBucket_pt bucket = *bucket_pt;
137  int i;
138  for (i=0; i<= bucket->max_bucket; i++)
139  {
140 
141  if (bucket->buckets[i].p != NULL)
142  {
143  p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
144  }
145  }
146  omFreeBin(bucket, sBucket_bin);
147  *bucket_pt = NULL;
148 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
long max_bucket
Definition: sbuckets.cc:38
P bucket
Definition: myNF.cc:79
int i
Definition: cfEzgcd.cc:123
static omBin sBucket_bin
Definition: sbuckets.cc:43
ring bucket_ring
Definition: sbuckets.cc:37
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
#define NULL
Definition: omList.c:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259

§ sBucketDestroy()

void sBucketDestroy ( sBucket_pt bucket)

Definition at line 127 of file sbuckets.cc.

128 {
129  assume(bucket != NULL);
130  omFreeBin(*bucket, sBucket_bin);
131  *bucket = NULL;
132 }
#define assume(x)
Definition: mod2.h:403
static omBin sBucket_bin
Definition: sbuckets.cc:43
#define NULL
Definition: omList.c:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259

§ sBucketGetRing()

ring sBucketGetRing ( const sBucket_pt  bucket)

Returns bucket ring.

Definition at line 51 of file sbuckets.cc.

52 { return bucket->bucket_ring; }
ring bucket_ring
Definition: sbuckets.cc:37

§ sBucketSortAdd()

poly sBucketSortAdd ( poly  p,
const ring  r 
)

Sorts p with bucketSort: p may have equal monomials.

Definition at line 364 of file sbuckets.cc.

365 {
366 #ifdef HAVE_ASSUME
367  int l_in = pLength(p);
368 #endif
369 
370  if (p == NULL || pNext(p) == NULL) return p;
371 
373  poly pn = pNext(p);
374 
375  do
376  {
377  pNext(p) = NULL;
378  sBucket_Add_p(bucket, p, 1);
379  p = pn;
380  if (p == NULL) break;
381  pn = pNext(pn);
382  }
383  while (1);
384 
385  int l_dummy;
386  sBucketClearAdd(bucket, &pn, &l_dummy);
387  sBucketDestroy(&bucket);
388 
389  p_Test(pn, r);
390 #ifdef HAVE_ASSUME
391  assume(l_dummy == pLength(pn));
392  assume(l_in >= l_dummy);
393 #endif
394  return pn;
395 }
return P p
Definition: myNF.cc:203
void sBucket_Add_p(sBucket_pt bucket, poly p, int length)
adds poly p to bucket destroys p!
Definition: sbuckets.cc:201
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:403
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:127
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
P bucket
Definition: myNF.cc:79
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define p_Test(p, r)
Definition: p_polys.h:160
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
polyrec * poly
Definition: hilb.h:10
void sBucketClearAdd(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:270

§ sBucketSortMerge()

poly sBucketSortMerge ( poly  p,
const ring  r 
)

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

Definition at line 327 of file sbuckets.cc.

328 {
329 #ifdef HAVE_ASSUME
330  int l_in = pLength(p);
331 #endif
332 
333  if (p == NULL || pNext(p) == NULL) return p;
334 
336  poly pn = pNext(p);
337 
338  do
339  {
340  pNext(p) = NULL;
341  sBucket_Merge_m(bucket, p);
342  p = pn;
343  if (p == NULL) break;
344  pn = pNext(pn);
345  }
346  while (1);
347 
348  int l_dummy;
349  sBucketClearMerge(bucket, &pn, &l_dummy);
350  sBucketDestroy(&bucket);
351 
352  p_Test(pn, r);
353 #ifdef HAVE_ASSUME
354  assume(l_dummy == pLength(pn));
355  assume(l_in == l_dummy);
356 #endif
357  return pn;
358 }
return P p
Definition: myNF.cc:203
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:403
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:127
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:120
P bucket
Definition: myNF.cc:79
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:232
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define p_Test(p, r)
Definition: p_polys.h:160
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:43
polyrec * poly
Definition: hilb.h:10
static void sBucket_Merge_m(sBucket_pt bucket, poly p)
Definition: sbuckets.cc:155

§ sIsEmpty()

bool sIsEmpty ( const sBucket_pt  bucket)

Test whether bucket is empty!?

Definition at line 55 of file sbuckets.cc.

56 {
57  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
58  {
59  assume( i < (BIT_SIZEOF_LONG - 3) );
60  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
61 
62  if( bucket->buckets[i].p != NULL )
63  return false;
64 
65  if( bucket->buckets[i].length != 0 )
66  return false;
67  }
68 
69  return( bucket->max_bucket == 0 );
70 
71 }
sBucketPoly buckets[BIT_SIZEOF_LONG - 3]
Definition: sbuckets.cc:39
long max_bucket
Definition: sbuckets.cc:38
long length
Definition: sbuckets.cc:31
#define assume(x)
Definition: mod2.h:403
int i
Definition: cfEzgcd.cc:123
static unsigned pLength(poly a)
Definition: p_polys.h:189
#define NULL
Definition: omList.c:10
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:79

Variable Documentation

§ sBucket_bin

omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))
static

Definition at line 43 of file sbuckets.cc.