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

class sBucketPoly

Definition at line 32 of file sbuckets.cc.

Data Fields
long length
poly p
class sBucket

Definition at line 39 of file sbuckets.cc.

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

Function Documentation

static int LOG2 ( int  i)
inlinestatic

Definition at line 106 of file sbuckets.cc.

107 {
108  assume (i > 0);
109  int j = 0;
110 
111  do
112  {
113  i = i >> 1;
114  if (i == 0) return j;
115  j++;
116  }
117  while (1);
118 
119  return j;
120 }
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:405
int i
Definition: cfEzgcd.cc:123
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 = LOG2(length);
215 
216  while (bucket->buckets[i].p != NULL)
217  {
218  p = p_Add_q(p, bucket->buckets[i].p, length, bucket->buckets[i].length,
219  bucket->bucket_ring);
220  bucket->buckets[i].p = NULL;
221  bucket->buckets[i].length = 0;
222  if (p==NULL)
223  {
224  if (i > bucket->max_bucket) bucket->max_bucket = i;
225  return;
226  }
227  i = LOG2(length);
228  }
229 
230  bucket->buckets[i].p = p;
231  bucket->buckets[i].length = length;
232  if (i > bucket->max_bucket) bucket->max_bucket = i;
233 }
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:43
long length
Definition: sbuckets.cc:36
static int pLength(poly a)
Definition: p_polys.h:189
static int LOG2(int i)
Definition: sbuckets.cc:106
#define assume(x)
Definition: mod2.h:405
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:42
#define NULL
Definition: omList.c:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:883
static void sBucket_Merge_m ( sBucket_pt  bucket,
poly  p 
)
static

Definition at line 160 of file sbuckets.cc.

161 {
162  assume(p != NULL && pNext(p) == NULL);
163  int length = 1;
164  int i = 0;
165 
166  while (bucket->buckets[i].p != NULL)
167  {
168  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
169  length += bucket->buckets[i].length;
170  bucket->buckets[i].p = NULL;
171  bucket->buckets[i].length = 0;
172  i++;
173  assume(LOG2(length) == i);
174  }
175 
176  bucket->buckets[i].p = p;
177  bucket->buckets[i].length = length;
178  if (i > bucket->max_bucket) bucket->max_bucket = i;
179 }
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:43
long length
Definition: sbuckets.cc:36
static int LOG2(int i)
Definition: sbuckets.cc:106
#define assume(x)
Definition: mod2.h:405
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:42
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1141
#define pNext(p)
Definition: monomials.h:43
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 181 of file sbuckets.cc.

182 {
183  assume(bucket != NULL);
184  assume(length <= 0 || length == pLength(p));
185 
186  if (p == NULL) return;
187  if (length <= 0) length = pLength(p);
188 
189  int i = LOG2(length);
190 
191  while (bucket->buckets[i].p != NULL)
192  {
193  p = p_Merge_q(p, bucket->buckets[i].p, bucket->bucket_ring);
194  length += bucket->buckets[i].length;
195  bucket->buckets[i].p = NULL;
196  bucket->buckets[i].length = 0;
197  i++;
198  assume(LOG2(length) == i);
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 }
return P p
Definition: myNF.cc:203
long max_bucket
Definition: sbuckets.cc:43
long length
Definition: sbuckets.cc:36
static int pLength(poly a)
Definition: p_polys.h:189
static int LOG2(int i)
Definition: sbuckets.cc:106
#define assume(x)
Definition: mod2.h:405
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:42
#define NULL
Definition: omList.c:10
static poly p_Merge_q(poly p, poly q, const ring r)
Definition: p_polys.h:1141
void sBucketClearAdd ( sBucket_pt  bucket,
poly p,
int *  length 
)

Definition at line 275 of file sbuckets.cc.

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

Definition at line 237 of file sbuckets.cc.

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

Copy sBucket non-intrusive!!!

Definition at line 80 of file sbuckets.cc.

81 {
82  const ring r = bucket->bucket_ring;
83 
84  sBucket_pt newbucket = sBucketCreate(r);
85 
86  newbucket->max_bucket = bucket->max_bucket;
87 
88  for(int i = 0; i <= bucket->max_bucket; i++)
89  {
90  assume( i < (BIT_SIZEOF_LONG - 3) );
91  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
92 
93  newbucket->buckets[i].p = p_Copy(bucket->buckets[i].p, r);
94  newbucket->buckets[i].length = bucket->buckets[i].length;
95 
96  assume( pLength(newbucket->buckets[i].p) == newbucket->buckets[i].length );
97  }
98 
99  return newbucket;
100 }
long max_bucket
Definition: sbuckets.cc:43
long length
Definition: sbuckets.cc:36
static int pLength(poly a)
Definition: p_polys.h:189
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:810
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:405
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:125
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
int i
Definition: cfEzgcd.cc:123
ring bucket_ring
Definition: sbuckets.cc:42
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:124
sBucket_pt sBucketCreate ( const ring  r)

Definition at line 125 of file sbuckets.cc.

126 {
128  bucket->bucket_ring = r;
129  return bucket;
130 }
const ring r
Definition: syzextra.cc:208
P bucket
Definition: myNF.cc:79
static omBin sBucket_bin
Definition: sbuckets.cc:48
ring bucket_ring
Definition: sbuckets.cc:42
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
sBucket * sBucket_pt
Definition: summator.h:15
void sBucketDeleteAndDestroy ( sBucket_pt bucket_pt)

Definition at line 139 of file sbuckets.cc.

140 {
141  sBucket_pt bucket = *bucket_pt;
142  int i;
143  for (i=0; i<= bucket->max_bucket; i++)
144  {
145 
146  if (bucket->buckets[i].p != NULL)
147  {
148  p_Delete(&(bucket->buckets[i].p), bucket->bucket_ring);
149  }
150  }
151  omFreeBin(bucket, sBucket_bin);
152  *bucket_pt = NULL;
153 }
long max_bucket
Definition: sbuckets.cc:43
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
P bucket
Definition: myNF.cc:79
int i
Definition: cfEzgcd.cc:123
static omBin sBucket_bin
Definition: sbuckets.cc:48
ring bucket_ring
Definition: sbuckets.cc:42
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
#define NULL
Definition: omList.c:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
void sBucketDestroy ( sBucket_pt bucket)

Definition at line 132 of file sbuckets.cc.

133 {
134  assume(bucket != NULL);
135  omFreeBin(*bucket, sBucket_bin);
136  *bucket = NULL;
137 }
#define assume(x)
Definition: mod2.h:405
static omBin sBucket_bin
Definition: sbuckets.cc:48
#define NULL
Definition: omList.c:10
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
ring sBucketGetRing ( const sBucket_pt  bucket)

Returns bucket ring.

Definition at line 56 of file sbuckets.cc.

57 { return bucket->bucket_ring; }
ring bucket_ring
Definition: sbuckets.cc:42
poly sBucketSortAdd ( poly  p,
const ring  r 
)

Sorts p with bucketSort: p may have equal monomials.

Definition at line 369 of file sbuckets.cc.

370 {
371 #ifdef HAVE_ASSUME
372  int l_in = pLength(p);
373 #endif
374 
375  if (p == NULL || pNext(p) == NULL) return p;
376 
378  poly pn = pNext(p);
379 
380  do
381  {
382  pNext(p) = NULL;
383  sBucket_Add_p(bucket, p, 1);
384  p = pn;
385  if (p == NULL) break;
386  pn = pNext(pn);
387  }
388  while (1);
389 
390  int l_dummy;
391  sBucketClearAdd(bucket, &pn, &l_dummy);
392  sBucketDestroy(&bucket);
393 
394  p_Test(pn, r);
395 #ifdef HAVE_ASSUME
396  assume(l_dummy == pLength(pn));
397  assume(l_in >= l_dummy);
398 #endif
399  return pn;
400 }
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:206
static int pLength(poly a)
Definition: p_polys.h:189
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:405
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:132
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:125
P bucket
Definition: myNF.cc:79
#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:275
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.

333 {
334 #ifdef HAVE_ASSUME
335  int l_in = pLength(p);
336 #endif
337 
338  if (p == NULL || pNext(p) == NULL) return p;
339 
341  poly pn = pNext(p);
342 
343  do
344  {
345  pNext(p) = NULL;
346  sBucket_Merge_m(bucket, p);
347  p = pn;
348  if (p == NULL) break;
349  pn = pNext(pn);
350  }
351  while (1);
352 
353  int l_dummy;
354  sBucketClearMerge(bucket, &pn, &l_dummy);
355  sBucketDestroy(&bucket);
356 
357  p_Test(pn, r);
358 #ifdef HAVE_ASSUME
359  assume(l_dummy == pLength(pn));
360  assume(l_in == l_dummy);
361 #endif
362  return pn;
363 }
return P p
Definition: myNF.cc:203
static int pLength(poly a)
Definition: p_polys.h:189
const ring r
Definition: syzextra.cc:208
#define assume(x)
Definition: mod2.h:405
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:132
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:125
P bucket
Definition: myNF.cc:79
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:237
#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:160
bool sIsEmpty ( const sBucket_pt  bucket)

Test whether bucket is empty!?

Definition at line 60 of file sbuckets.cc.

61 {
62  for(int i = 0; i < (BIT_SIZEOF_LONG - 3); i++)
63  {
64  assume( i < (BIT_SIZEOF_LONG - 3) );
65  assume( pLength(bucket->buckets[i].p) == bucket->buckets[i].length );
66 
67  if( bucket->buckets[i].p != NULL )
68  return false;
69 
70  if( bucket->buckets[i].length != 0 )
71  return false;
72  }
73 
74  return( bucket->max_bucket == 0 );
75 
76 }
long max_bucket
Definition: sbuckets.cc:43
long length
Definition: sbuckets.cc:36
static int pLength(poly a)
Definition: p_polys.h:189
#define assume(x)
Definition: mod2.h:405
sBucketPoly buckets[BIT_SIZEOF_LONG-3]
Definition: sbuckets.cc:44
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
#define BIT_SIZEOF_LONG
Definition: auxiliary.h:124

Variable Documentation

omBin sBucket_bin = omGetSpecBin(sizeof(sBucket))
static

Definition at line 48 of file sbuckets.cc.