commit/MOAB: iulian07: reformat the gs.cpp and TupleList.cpp files
1 new commit in MOAB: https://bitbucket.org/fathomteam/moab/commits/b1a44624eb2c/ Changeset: b1a44624eb2c Branch: master User: iulian07 Date: 2013-11-27 18:27:17 Summary: reformat the gs.cpp and TupleList.cpp files format the files according to moab suggestions, tabs are replaced with 2 spaces, and avoid using the comma separator between instructions, to make it easier to read (for me :) nothing should change in the logic, and all tests pass in parallel Affected #: 2 files diff --git a/src/parallel/TupleList.cpp b/src/parallel/TupleList.cpp index ad5b055..bf08946 100644 --- a/src/parallel/TupleList.cpp +++ b/src/parallel/TupleList.cpp @@ -9,496 +9,574 @@ namespace moab { - void fail(const char *fmt, ...) - { - va_list ap; - va_start(ap, fmt); - vfprintf(stderr, fmt, ap); - va_end(ap); - exit(1); - } +void fail(const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); + exit(1); +} - TupleList::buffer::buffer(size_t sz) - { - ptr = NULL; - buffSize=0; - this->buffer_init_(sz, __FILE__); - } +TupleList::buffer::buffer(size_t sz) +{ + ptr = NULL; + buffSize = 0; + this->buffer_init_(sz, __FILE__); +} - TupleList::buffer::buffer() - { - buffSize=0; - ptr = NULL; - } +TupleList::buffer::buffer() +{ + buffSize = 0; + ptr = NULL; +} - void TupleList::buffer::buffer_init_(size_t sizeIn, const char *file) +void TupleList::buffer::buffer_init_(size_t sizeIn, const char *file) +{ + this->buffSize = sizeIn; + void *res = malloc(this->buffSize); + if (!res && buffSize > 0) + fail("%s: allocation of %d bytes failed\n", file, (int) buffSize); + ptr = (char*) res; +} + +void TupleList::buffer::buffer_reserve_(size_t min, const char *file) +{ + if (this->buffSize < min) { - this->buffSize = sizeIn; - void *res = malloc(this->buffSize); - if (!res && buffSize > 0) - fail("%s: allocation of %d bytes failed\n",file,(int)buffSize); + size_t newSize = this->buffSize; + newSize += newSize / 2 + 1; + if (newSize < min) + newSize = min; + void *res = realloc(ptr, newSize); + if (!res && newSize > 0) + fail("%s: allocation of %d bytes failed\n", file, (int) this->buffSize); ptr = (char*) res; + this->buffSize = newSize; } +} - void TupleList::buffer::buffer_reserve_(size_t min, const char *file) - { - if(this->buffSize < min) { - size_t newSize = this->buffSize; - newSize += newSize/2 + 1; - if (newSize < min) newSize = min; - void *res = realloc (ptr, newSize); - if (!res && newSize > 0) - fail("%s: allocation of %d bytes failed\n",file,(int)this->buffSize); - ptr = (char*) res; - this->buffSize = newSize; - } - } +void TupleList::buffer::reset() +{ + free(ptr); + ptr = NULL; + buffSize = 0; +} - void TupleList::buffer::reset () - { - free(ptr); - ptr = NULL; - buffSize = 0; - } +TupleList::TupleList(uint p_mi, uint p_ml, uint p_mul, uint p_mr, uint p_max) +{ + vi = NULL; + vl = NULL; + vul = NULL; + vr = NULL; + initialize(p_mi, p_ml, p_mul, p_mr, p_max); +} - TupleList::TupleList(uint p_mi, uint p_ml, - uint p_mul, uint p_mr, uint p_max) - { - vi = NULL; - vl = NULL; - vul = NULL; - vr = NULL; - initialize (p_mi, p_ml, p_mul, p_mr, p_max); - } +TupleList::TupleList() +{ + vi = NULL; + vl = NULL; + vul = NULL; + vr = NULL; + disableWriteAccess(); +} - TupleList::TupleList() +// Allocates space for the tuple list in memory according to parameters +void TupleList::initialize(uint p_mi, uint p_ml, uint p_mul, uint p_mr, + uint p_max) +{ + this->n = 0; + this->max = p_max; + this->mi = p_mi; + this->ml = p_ml; + this->mul = p_mul; + this->mr = p_mr; + size_t sz; + + if (max * mi > 0) { + sz = max * mi * sizeof(sint); + void *resi = malloc(sz); + if (!resi && max * mi > 0) + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + vi = (sint*) resi; + } + else vi = NULL; + if (max * ml > 0) + { + sz = max * ml * sizeof(slong); + void *resl = malloc(sz); + if (!resl && max * ml > 0) + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + vl = (slong*) resl; + } + else vl = NULL; + if (max * mul > 0) + { + sz = max * mul * sizeof(ulong); + void *resu = malloc(sz); + if (!resu && max * mul > 0) + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + vul = (ulong*) resu; + } + else vul = NULL; - vr = NULL; - disableWriteAccess(); + if (max * mr > 0) + { + sz = max * mr * sizeof(realType); + void *resr = malloc(sz); + if (!resr && max * ml > 0) + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + vr = (realType*) resr; } + else + vr = NULL; - // Allocates space for the tuple list in memory according to parameters - void TupleList::initialize (uint p_mi, uint p_ml, - uint p_mul, uint p_mr, uint p_max) - { - this->n = 0; - this->max = p_max; - this->mi = p_mi; - this->ml = p_ml; - this->mul = p_mul; - this->mr = p_mr; - size_t sz; - - if (max*mi > 0) { - sz = max*mi*sizeof(sint); - void *resi = malloc(sz); - if(!resi && max*mi > 0) - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - vi = (sint*) resi; - } else - vi = NULL; - if (max*ml > 0) { - sz = max*ml*sizeof(slong); - void *resl = malloc(sz); - if(!resl && max*ml > 0) - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - vl = (slong*) resl; - } else - vl = NULL; - if (max*mul > 0) { - sz = max*mul*sizeof(ulong); - void *resu = malloc(sz); - if(!resu && max*mul > 0) - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - vul = (ulong*) resu; - } else - vul = NULL; - if (max*mr > 0) { - sz = max*mr*sizeof(realType); - void *resr = malloc(sz); - if(!resr && max*ml > 0) - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - vr=(realType*) resr; - } else - vr = NULL; - - //Begin with write access disabled - this->disableWriteAccess(); - - //Set read variables - vi_rd = vi; vl_rd = vl; vul_rd = vul; vr_rd = vr; - } + //Begin with write access disabled + this->disableWriteAccess(); - // Resizes a tuplelist to the given uint max - ErrorCode TupleList::resize(uint maxIn) - { - this->max = maxIn; - size_t sz; + //Set read variables + vi_rd = vi; + vl_rd = vl; + vul_rd = vul; + vr_rd = vr; +} - if (vi || (max*mi > 0)){ - sz = max*mi*sizeof(sint); - void *resi = realloc(vi, sz); - if(!resi && max*mi > 0){ - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - return moab::MB_MEMORY_ALLOCATION_FAILED; - } - vi = (sint*) resi; - } - if (vl || (max*ml > 0)){ - sz = max*ml*sizeof(slong); - void *resl = realloc(vl, sz); - if(!resl && max*ml > 0){ - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - return moab::MB_MEMORY_ALLOCATION_FAILED; - } - vl = (slong*) resl; - } - if (vul || (max*mul > 0)){ - sz = max*mul*sizeof(ulong); - void *resu = realloc(vul, sz); - if(!resu && max*mul > 0){ - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - return moab::MB_MEMORY_ALLOCATION_FAILED; - } - vul = (ulong*) resu; +// Resizes a tuplelist to the given uint max +ErrorCode TupleList::resize(uint maxIn) +{ + this->max = maxIn; + size_t sz; + + if (vi || (max * mi > 0)) + { + sz = max * mi * sizeof(sint); + void *resi = realloc(vi, sz); + if (!resi && max * mi > 0) + { + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + return moab::MB_MEMORY_ALLOCATION_FAILED; } - if (vr || (max*mr > 0)){ - sz = max*mr*sizeof(realType); - void *resr = realloc(vr, sz); - if(!resr && max*mr > 0){ - fail("%s: allocation of %d bytes failed\n",__FILE__,(int)sz); - return moab::MB_MEMORY_ALLOCATION_FAILED; - } - vr = (realType*) resr; + vi = (sint*) resi; + } + if (vl || (max * ml > 0)) + { + sz = max * ml * sizeof(slong); + void *resl = realloc(vl, sz); + if (!resl && max * ml > 0) + { + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + return moab::MB_MEMORY_ALLOCATION_FAILED; } - - //Set read variables - vi_rd = vi; vl_rd = vl; vul_rd = vul; vr_rd = vr; - - //Set the write variables if necessary - if(writeEnabled){ - vi_wr = vi; vl_wr = vl; vul_wr = vul; vr_wr = vr; + vl = (slong*) resl; + } + if (vul || (max * mul > 0)) + { + sz = max * mul * sizeof(ulong); + void *resu = realloc(vul, sz); + if (!resu && max * mul > 0) + { + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + return moab::MB_MEMORY_ALLOCATION_FAILED; } - return moab::MB_SUCCESS; + vul = (ulong*) resu; } - - // Frees the memory used by the tuplelist - void TupleList::reset() + if (vr || (max * mr > 0)) { - //free up the pointers - free(vi); - free(vl); - free(vul); - free(vr); - //Set them all to null - vr = NULL; - vi = NULL; - vul = NULL; - vl = NULL; - //Set the read and write pointers to null - disableWriteAccess(); - vi_rd = NULL; vl_rd = NULL; - vul_rd = NULL; vr_rd = NULL; + sz = max * mr * sizeof(realType); + void *resr = realloc(vr, sz); + if (!resr && max * mr > 0) + { + fail("%s: allocation of %d bytes failed\n", __FILE__, (int) sz); + return moab::MB_MEMORY_ALLOCATION_FAILED; + } + vr = (realType*) resr; } - // Increments n; if n>max, increase the size of the tuplelist - void TupleList::reserve() + //Set read variables + vi_rd = vi; + vl_rd = vl; + vul_rd = vul; + vr_rd = vr; + + //Set the write variables if necessary + if (writeEnabled) { - n++; - while (n>max) - resize((max ? max+max/2+1 : 2)); - last_sorted = -1; + vi_wr = vi; + vl_wr = vl; + vul_wr = vul; + vr_wr = vr; } + return moab::MB_SUCCESS; +} - // Given the value and the position in the field, finds the index of the tuple - // to which the value belongs - int TupleList::find(unsigned int key_num, sint value) - { - ulong uvalue = (ulong) value; - if (!(key_num>mi)) { - // Binary search: only if the tuple_list is sorted - if (last_sorted==(int)key_num) { - int lb=0, ub=n, index; // lb=lower bound, ub=upper bound, index=mid - for (;lb<=ub;) { - index = (lb+ub)/2; - if (vi[index*mi+key_num] == (long)uvalue) - return index; - else if (vi[index*mi+key_num] > (long)uvalue) - ub = index-1; - else if (vi[index*mi+key_num] < (long)uvalue) - lb = index+1; - } - } - else { - // Sequential search: if tuple_list is not sorted - for (long index = 0; index<n; index++) { - if (vi[index*mi+key_num] == (long)uvalue) - return index; - } - } - } - return -1; // If the value wasn't present or an invalid key was given - } +// Frees the memory used by the tuplelist +void TupleList::reset() +{ + //free up the pointers + free(vi); + free(vl); + free(vul); + free(vr); + //Set them all to null + vr = NULL; + vi = NULL; + vul = NULL; + vl = NULL; + //Set the read and write pointers to null + disableWriteAccess(); + vi_rd = NULL; + vl_rd = NULL; + vul_rd = NULL; + vr_rd = NULL; +} - int TupleList::find(unsigned int key_num, slong value) - { - ulong uvalue = (ulong) value; - if (!(key_num>ml)) { - if (last_sorted-mi==key_num) { - int lb=0, ub=n, index; // lb=lower bound, ub=upper bound, index=mid - for (;lb<=ub;) { - index = (lb+ub)/2; - if(vl[index*ml+key_num] == (long)uvalue) - return index; - else if (vl[index*ml+key_num] > (long)uvalue) - ub = index-1; - else if (vl[index*ml+key_num] < (long)uvalue) - lb = index+1; - } +// Increments n; if n>max, increase the size of the tuplelist +void TupleList::reserve() +{ + n++; + while (n > max) + resize((max ? max + max / 2 + 1 : 2)); + last_sorted = -1; +} + +// Given the value and the position in the field, finds the index of the tuple +// to which the value belongs +int TupleList::find(unsigned int key_num, sint value) +{ + ulong uvalue = (ulong) value; + if (!(key_num > mi)) + { + // Binary search: only if the tuple_list is sorted + if (last_sorted == (int) key_num) + { + int lb = 0, ub = n, index; // lb=lower bound, ub=upper bound, index=mid + for (; lb <= ub;) + { + index = (lb + ub) / 2; + if (vi[index * mi + key_num] == (long) uvalue) + return index; + else if (vi[index * mi + key_num] > (long) uvalue) + ub = index - 1; + else if (vi[index * mi + key_num] < (long) uvalue) + lb = index + 1; } - else { - // Sequential search: if tuple_list is not sorted - for (uint index = 0; index<n; index++) { - if (vl[index*ml+key_num] == (long)uvalue) - return index; - } + } + else + { + // Sequential search: if tuple_list is not sorted + for (long index = 0; index < n; index++) + { + if (vi[index * mi + key_num] == (long) uvalue) + return index; } } - return -1; // If the value wasn't present or an invalid key was given } + return -1; // If the value wasn't present or an invalid key was given +} - int TupleList::find(unsigned int key_num, ulong value) - { - if (!(key_num>mul)) { - if (last_sorted-mi-ml==key_num) { - int lb=0, ub=n-1, index; // lb=lower bound, ub=upper bound, index=mid - for (;lb<=ub;) { - index = (lb+ub)/2; - if (vul[index*mul+key_num] == value) - return index; - else if (vul[index*mul+key_num] > value) - ub=index-1; - else if (vul[index*mul+key_num] < value) - lb=index+1; - } +int TupleList::find(unsigned int key_num, slong value) +{ + ulong uvalue = (ulong) value; + if (!(key_num > ml)) + { + if (last_sorted - mi == key_num) + { + int lb = 0, ub = n, index; // lb=lower bound, ub=upper bound, index=mid + for (; lb <= ub;) + { + index = (lb + ub) / 2; + if (vl[index * ml + key_num] == (long) uvalue) + return index; + else if (vl[index * ml + key_num] > (long) uvalue) + ub = index - 1; + else if (vl[index * ml + key_num] < (long) uvalue) + lb = index + 1; } - else { - // Sequential search: if tuple_list is not sorted - for (uint index = 0; index<n; index++) { - if (vul[index*mul+key_num] == value) - return index; - } + } + else + { + // Sequential search: if tuple_list is not sorted + for (uint index = 0; index < n; index++) + { + if (vl[index * ml + key_num] == (long) uvalue) + return index; } } - return -1; // If the value wasn't present or an invalid key was given } + return -1; // If the value wasn't present or an invalid key was given +} - int TupleList::find(unsigned int key_num, realType value) +int TupleList::find(unsigned int key_num, ulong value) +{ + if (!(key_num > mul)) { - if (!key_num>mr) { - // Sequential search: TupleList cannot be sorted by reals - for (uint index = 0; index<n; index++) { - if (vr[index*mr+key_num] == value) + if (last_sorted - mi - ml == key_num) + { + int lb = 0, ub = n - 1, index; // lb=lower bound, ub=upper bound, index=mid + for (; lb <= ub;) + { + index = (lb + ub) / 2; + if (vul[index * mul + key_num] == value) + return index; + else if (vul[index * mul + key_num] > value) + ub = index - 1; + else if (vul[index * mul + key_num] < value) + lb = index + 1; + } + } + else + { + // Sequential search: if tuple_list is not sorted + for (uint index = 0; index < n; index++) + { + if (vul[index * mul + key_num] == value) return index; } } - return -1; // If the value wasn't present or an invalid key was given } + return -1; // If the value wasn't present or an invalid key was given +} - sint TupleList::get_sint(unsigned int index, unsigned int m) +int TupleList::find(unsigned int key_num, realType value) +{ + if (!key_num > mr) { - if (mi>m && n>index) - return vi[index*mi+m]; - return 0; + // Sequential search: TupleList cannot be sorted by reals + for (uint index = 0; index < n; index++) + { + if (vr[index * mr + key_num] == value) + return index; + } } + return -1; // If the value wasn't present or an invalid key was given +} - slong TupleList::get_int(unsigned int index, unsigned int m) - { - if (ml>m && n>index) - return vl[index*ml+m]; - return 0; - } +sint TupleList::get_sint(unsigned int index, unsigned int m) +{ + if (mi > m && n > index) + return vi[index * mi + m]; + return 0; +} - ulong TupleList::get_ulong(unsigned int index, unsigned int m) - { - if (mul>m && n>index) - return vul[index*mul+m]; - return 0; - } +slong TupleList::get_int(unsigned int index, unsigned int m) +{ + if (ml > m && n > index) + return vl[index * ml + m]; + return 0; +} - realType TupleList::get_double(unsigned int index, unsigned int m) - { - if (mr>m && n>index) - return vr[index*mr+m]; - return 0; - } +ulong TupleList::get_ulong(unsigned int index, unsigned int m) +{ + if (mul > m && n > index) + return vul[index * mul + m]; + return 0; +} - ErrorCode TupleList::get(unsigned int index, const sint *&sp, - const slong *&ip, const ulong *&lp, - const realType *&dp) - { - if (index <= n){ - if (mi) *&sp = &vi[index*mi]; - else *&sp = NULL; - if (ml) *&ip = &vl[index*ml]; - else *&ip = NULL; - if (mul) *&lp = &vul[index*mul]; - else *&lp = NULL; - if (mr) *&dp = &vr[index*mr]; - else *&dp = NULL; - - return MB_SUCCESS; - } - return MB_FAILURE; - } +realType TupleList::get_double(unsigned int index, unsigned int m) +{ + if (mr > m && n > index) + return vr[index * mr + m]; + return 0; +} - unsigned int TupleList::push_back(sint *sp, slong *ip, - ulong *lp, realType *dp) +ErrorCode TupleList::get(unsigned int index, const sint *&sp, const slong *&ip, + const ulong *&lp, const realType *&dp) +{ + if (index <= n) { - reserve(); if (mi) - memcpy(&vi[mi*(n-1)], sp, mi*sizeof(sint)); + *&sp = &vi[index * mi]; + else + *&sp = NULL; if (ml) - memcpy(&vl[ml*(n-1)], ip, ml*sizeof(long)); + *&ip = &vl[index * ml]; + else + *&ip = NULL; if (mul) - memcpy(&vul[mul*(n-1)], lp, mul*sizeof(ulong)); + *&lp = &vul[index * mul]; + else + *&lp = NULL; if (mr) - memcpy(&vr[mr*(n-1)], dp, mr*sizeof(realType)); + *&dp = &vr[index * mr]; + else + *&dp = NULL; - last_sorted = -1; - return n-1; + return MB_SUCCESS; } + return MB_FAILURE; +} - void TupleList::enableWriteAccess() - { - writeEnabled = true; - last_sorted = -1; - vi_wr = vi; vl_wr = vl; vul_wr = vul; vr_wr = vr; - } +unsigned int TupleList::push_back(sint *sp, slong *ip, ulong *lp, realType *dp) +{ + reserve(); + if (mi) + memcpy(&vi[mi * (n - 1)], sp, mi * sizeof(sint)); + if (ml) + memcpy(&vl[ml * (n - 1)], ip, ml * sizeof(long)); + if (mul) + memcpy(&vul[mul * (n - 1)], lp, mul * sizeof(ulong)); + if (mr) + memcpy(&vr[mr * (n - 1)], dp, mr * sizeof(realType)); + + last_sorted = -1; + return n - 1; +} - void TupleList::disableWriteAccess() - { - writeEnabled = false; - vi_wr = NULL; vl_wr = NULL; - vul_wr= NULL; vr_wr = NULL; - } +void TupleList::enableWriteAccess() +{ + writeEnabled = true; + last_sorted = -1; + vi_wr = vi; + vl_wr = vl; + vul_wr = vul; + vr_wr = vr; +} - void TupleList::getTupleSize(uint &mi_out, uint &ml_out, - uint &mul_out, uint &mr_out) const - { - mi_out = mi; ml_out = ml; - mul_out = mul; mr_out = mr; - } +void TupleList::disableWriteAccess() +{ + writeEnabled = false; + vi_wr = NULL; + vl_wr = NULL; + vul_wr = NULL; + vr_wr = NULL; +} - uint TupleList::inc_n() - { - //Check for direct write access - if(!writeEnabled){ - enableWriteAccess(); - } - n++; - return n; - } +void TupleList::getTupleSize(uint &mi_out, uint &ml_out, uint &mul_out, + uint &mr_out) const +{ + mi_out = mi; + ml_out = ml; + mul_out = mul; + mr_out = mr; +} - void TupleList::set_n(uint n_in) +uint TupleList::inc_n() +{ + //Check for direct write access + if (!writeEnabled) { - //Check for direct write access; - if(!writeEnabled){ - enableWriteAccess(); - } - n = n_in; + enableWriteAccess(); } + n++; + return n; +} - void TupleList::print(const char *name) const +void TupleList::set_n(uint n_in) +{ + //Check for direct write access; + if (!writeEnabled) { - std::cout<<"Printing Tuple " << name << "==================="<<std::endl; - unsigned long i=0,l=0,ul=0,r=0; - for(uint k=0; k<n; k++){ - for(uint j=0; j<mi; j++){ - std::cout<<vi[i++]<<" | "; - } - for(uint j=0; j<ml; j++){ - std::cout<<vl[l++]<<" | "; - } - for(uint j=0; j<mul; j++){ - std::cout<<vul[ul++]<<" | "; - } - for(uint j=0; j<mr; j++){ - std::cout<<vr[r++]<<" | "; - } - std::cout<<std::endl; - } - std::cout<<"======================================="<<std::endl<<std::endl; + enableWriteAccess(); } + n = n_in; +} - - void TupleList::permute(uint *perm, void *work) +void TupleList::print(const char *name) const +{ + std::cout << "Printing Tuple " << name << "===================" << std::endl; + unsigned long i = 0, l = 0, ul = 0, r = 0; + for (uint k = 0; k < n; k++) { - const unsigned int_size = mi*sizeof(sint), - long_size = ml*sizeof(slong), - ulong_size = mul*sizeof(ulong), - real_size = mr*sizeof(realType); - if(mi) { - uint *p=perm, *pe=p+n; char *sorted=(char *)work; - while(p!=pe) memcpy((void *)sorted,&vi[mi*(*p++)],int_size),sorted+=int_size; - memcpy(vi,work,int_size*n); + for (uint j = 0; j < mi; j++) + { + std::cout << vi[i++] << " | "; } - if(ml) { - uint *p=perm, *pe=p+n; char *sorted=(char *)work; - while(p!=pe) memcpy((void *)sorted,&vl[ml*(*p++)],long_size),sorted+=long_size; - memcpy(vl,work,long_size*n); + for (uint j = 0; j < ml; j++) + { + std::cout << vl[l++] << " | "; } - if(mul) { - uint *p=perm, *pe=p+n; char *sorted=(char *)work; - while(p!=pe) memcpy((void *)sorted,&vul[mul*(*p++)],ulong_size),sorted+=ulong_size; - memcpy(vul,work,ulong_size*n); + for (uint j = 0; j < mul; j++) + { + std::cout << vul[ul++] << " | "; } - if(mr) { - uint *p=perm, *pe=p+n; char *sorted=(char *)work; - while(p!=pe) memcpy((void *)sorted,&vr[mr*(*p++)],real_size),sorted+=real_size; - memcpy(vr,work,real_size*n); + for (uint j = 0; j < mr; j++) + { + std::cout << vr[r++] << " | "; } + std::cout << std::endl; } - -# define umax_2(a, b) (((a)>(b)) ? (a):(b)) + std::cout << "=======================================" << std::endl + << std::endl; +} - ErrorCode TupleList::sort(uint key, TupleList::buffer *buf) - { - const unsigned int_size = mi*sizeof(sint); - const unsigned long_size = ml*sizeof(slong); - const unsigned ulong_size = mul*sizeof(ulong); - const unsigned real_size = mr*sizeof(realType); - const unsigned width = umax_2(umax_2(int_size,long_size), - umax_2(ulong_size,real_size)); - const unsigned data_size = key>=mi? - sizeof(SortData<long>): - sizeof(SortData<uint>); - - uint work_min= n * umax_2(2*data_size,sizeof(sint)+width); - uint *work; - buf->buffer_reserve(work_min); - work = (uint *)buf->ptr; - if(key<mi) - index_sort((uint *)&vi[key], n, mi, work, (SortData<uint>*)work); - else if (key < mi+ml) - index_sort((long*)&vl[key-mi], n, ml, work, (SortData<long>*)work); - else if (key < mi + ml + mul) - index_sort((ulong*)&vul[key-mi-ml], n, mul, work, (SortData<ulong>*)work); - else - return MB_NOT_IMPLEMENTED; +void TupleList::permute(uint *perm, void *work) +{ + const unsigned int_size = mi * sizeof(sint), long_size = ml * sizeof(slong), + ulong_size = mul * sizeof(ulong), real_size = mr * sizeof(realType); + if (mi) + { + uint *p = perm, *pe = p + n; + char *sorted = (char *) work; + while (p != pe) + memcpy((void *) sorted, &vi[mi * (*p++)], int_size), sorted += int_size; + memcpy(vi, work, int_size * n); + } + if (ml) + { + uint *p = perm, *pe = p + n; + char *sorted = (char *) work; + while (p != pe) + memcpy((void *) sorted, &vl[ml * (*p++)], long_size), sorted += long_size; + memcpy(vl, work, long_size * n); + } + if (mul) + { + uint *p = perm, *pe = p + n; + char *sorted = (char *) work; + while (p != pe) + memcpy((void *) sorted, &vul[mul * (*p++)], ulong_size), sorted += + ulong_size; + memcpy(vul, work, ulong_size * n); + } + if (mr) + { + uint *p = perm, *pe = p + n; + char *sorted = (char *) work; + while (p != pe) + memcpy((void *) sorted, &vr[mr * (*p++)], real_size), sorted += real_size; + memcpy(vr, work, real_size * n); + } +} - permute(work,work+n); +# define umax_2(a, b) (((a)>(b)) ? (a):(b)) - if(!writeEnabled) last_sorted = key; - return MB_SUCCESS; - } +ErrorCode TupleList::sort(uint key, TupleList::buffer *buf) +{ + const unsigned int_size = mi * sizeof(sint); + const unsigned long_size = ml * sizeof(slong); + const unsigned ulong_size = mul * sizeof(ulong); + const unsigned real_size = mr * sizeof(realType); + const unsigned width = umax_2(umax_2(int_size,long_size), + umax_2(ulong_size,real_size)); + const unsigned data_size = + key >= mi ? sizeof(SortData<long> ) : sizeof(SortData<uint> ); + + uint work_min = n * umax_2(2*data_size,sizeof(sint)+width); + uint *work; + buf->buffer_reserve(work_min); + work = (uint *) buf->ptr; + if (key < mi) + index_sort((uint *) &vi[key], n, mi, work, (SortData<uint>*) work); + else if (key < mi + ml) + index_sort((long*) &vl[key - mi], n, ml, work, (SortData<long>*) work); + else if (key < mi + ml + mul) + index_sort((ulong*) &vul[key - mi - ml], n, mul, work, + (SortData<ulong>*) work); + else + return MB_NOT_IMPLEMENTED; + + permute(work, work + n); + + if (!writeEnabled) + last_sorted = key; + return MB_SUCCESS; +} #undef umax_2 - #define DIGIT_BITS 8 #define DIGIT_VALUES (1<<DIGIT_BITS) #define DIGIT_MASK ((Value)(DIGIT_VALUES-1)) @@ -517,24 +595,24 @@ namespace moab { #define COUNT_DIGIT_32(n,i) COUNT_DIGIT_16(n,i); COUNT_DIGIT_16(n,i+16) #define COUNT_DIGIT_64(n,i) COUNT_DIGIT_32(n,i); COUNT_DIGIT_32(n,i+32) - template<class Value> Value TupleList::radix_count(const Value *A, const Value *end, Index stride, - Index count[DIGITS][DIGIT_VALUES]) + Index count[DIGITS][DIGIT_VALUES]) { Value bitorkey = 0; - memset(count,0,COUNT_SIZE*sizeof(Index)); - do { - Value val=*A; - bitorkey|=val; - COUNT_DIGIT_64(DIGITS,0); + memset(count, 0, COUNT_SIZE * sizeof(Index)); + do + { + Value val = *A; + bitorkey |= val; + COUNT_DIGIT_64(DIGITS, 0); // above macro expands to: //if(DIGITS> 0) count[ 0][val&DIGIT_MASK]++, val>>=DIGIT_BITS; //if(DIGITS> 1) count[ 1][val&DIGIT_MASK]++, val>>=DIGIT_BITS; // ... //if(DIGITS>63) count[63][val&DIGIT_MASK]++, val>>=DIGIT_BITS; - } while(A+=stride,A!=end); + } while (A += stride, A != end); return bitorkey; } @@ -548,157 +626,225 @@ Value TupleList::radix_count(const Value *A, const Value *end, Index stride, void TupleList::radix_offsets(Index *c) { - Index sum=0, t, *ce=c+DIGIT_VALUES; - do t=*c, *c++ = sum, sum+=t; while(c!=ce); + Index sum = 0, t, *ce = c + DIGIT_VALUES; + do + t = *c, *c++ = sum, sum += t; + while (c != ce); } template<class Value> -unsigned TupleList::radix_zeros(Value bitorkey, Index count[DIGITS][DIGIT_VALUES], - unsigned *shift, Index **offsets) -{ - unsigned digits=0, sh=0; Index *c = &count[0][0]; - do { - if(bitorkey&DIGIT_MASK) *shift++ = sh, *offsets++ = c, ++digits, - radix_offsets(c); - } while(bitorkey>>=DIGIT_BITS,sh+=DIGIT_BITS,c+=DIGIT_VALUES,sh!=VALUE_BITS); +unsigned TupleList::radix_zeros(Value bitorkey, + Index count[DIGITS][DIGIT_VALUES], unsigned *shift, Index **offsets) +{ + unsigned digits = 0, sh = 0; + Index *c = &count[0][0]; + do + { + if (bitorkey & DIGIT_MASK) + *shift++ = sh, *offsets++ = c, ++digits, radix_offsets(c); + } while (bitorkey >>= DIGIT_BITS,sh += DIGIT_BITS,c += DIGIT_VALUES,sh + != VALUE_BITS); return digits; } template<class Value> void TupleList::radix_index_pass_b(const Value *A, Index n, Index stride, - unsigned sh, Index *off, SortData<Value> *out) + unsigned sh, Index *off, SortData<Value> *out) { - Index i=0; - do { + Index i = 0; + do + { Value v = *A; - SortData<Value> *d = &out[off[(v>>sh)&DIGIT_MASK]++]; - d->v=v, d->i=i++; - } while(A+=stride,i!=n); + SortData<Value> *d = &out[off[(v >> sh) & DIGIT_MASK]++]; + d->v = v, d->i = i++; + } while (A += stride, i != n); } template<class Value> -void TupleList::radix_index_pass_m(const SortData<Value> *src, const SortData<Value> *end, - unsigned sh, Index *off, SortData<Value> *out) +void TupleList::radix_index_pass_m(const SortData<Value> *src, + const SortData<Value> *end, unsigned sh, Index *off, SortData<Value> *out) { - do { - SortData<Value> *d = &out[off[(src->v>>sh)&DIGIT_MASK]++]; - d->v=src->v,d->i=src->i; - } while(++src!=end); + do + { + SortData<Value> *d = &out[off[(src->v >> sh) & DIGIT_MASK]++]; + d->v = src->v, d->i = src->i; + } while (++src != end); } template<class Value> -void TupleList::radix_index_pass_e(const SortData<Value> *src, const SortData<Value> *end, - unsigned sh, Index *off, - Index *out) +void TupleList::radix_index_pass_e(const SortData<Value> *src, + const SortData<Value> *end, unsigned sh, Index *off, Index *out) { - do out[off[(src->v>>sh)&DIGIT_MASK]++]=src->i; while(++src!=end); + do + out[off[(src->v >> sh) & DIGIT_MASK]++] = src->i; + while (++src != end); } template<class Value> void TupleList::radix_index_pass_be(const Value *A, Index n, Index stride, - unsigned sh, Index *off, Index *out) + unsigned sh, Index *off, Index *out) { - Index i=0; - do out[off[(*A>>sh)&DIGIT_MASK]++]=i++; while(A+=stride,i!=n); + Index i = 0; + do + out[off[(*A >> sh) & DIGIT_MASK]++] = i++; + while (A += stride, i != n); } template<class Value> void TupleList::radix_index_sort(const Value *A, Index n, Index stride, - Index *idx, SortData<Value> *work) + Index *idx, SortData<Value> *work) { Index count[DIGITS][DIGIT_VALUES]; - Value bitorkey = radix_count(A, A+n*stride, stride, count); - unsigned shift[DIGITS]; Index *offsets[DIGITS]; - unsigned digits = radix_zeros(bitorkey,count,shift,offsets); - if(digits==0) { - Index i=0; do *idx++=i++; while(i!=n); - } else if(digits==1) { - radix_index_pass_be(A,n,stride,shift[0],offsets[0],idx); - } else { - SortData<Value> *src, *dst; unsigned d; - if((digits&1)==0) dst=work,src=dst+n; - else src=work,dst=src+n; - radix_index_pass_b(A,n,stride,shift[0],offsets[0],src); - for(d=1;d!=digits-1;++d) { + Value bitorkey = radix_count(A, A + n * stride, stride, count); + unsigned shift[DIGITS]; + Index *offsets[DIGITS]; + unsigned digits = radix_zeros(bitorkey, count, shift, offsets); + if (digits == 0) + { + Index i = 0; + do + *idx++ = i++; + while (i != n); + } + else if (digits == 1) + { + radix_index_pass_be(A, n, stride, shift[0], offsets[0], idx); + } + else + { + SortData<Value> *src, *dst; + unsigned d; + if ((digits & 1) == 0) + dst = work, src = dst + n; + else + src = work, dst = src + n; + radix_index_pass_b(A, n, stride, shift[0], offsets[0], src); + for (d = 1; d != digits - 1; ++d) + { SortData<Value> *t; - radix_index_pass_m(src,src+n,shift[d],offsets[d],dst); - t=src,src=dst,dst=t; + radix_index_pass_m(src, src + n, shift[d], offsets[d], dst); + t = src, src = dst, dst = t; } - radix_index_pass_e(src,src+n,shift[d],offsets[d],idx); + radix_index_pass_e(src, src + n, shift[d], offsets[d], idx); } } template<class Value> void TupleList::merge_index_sort(const Value *A, const Index An, Index stride, - Index *idx, SortData<Value> *work) + Index *idx, SortData<Value> *work) { - SortData<Value> *const buf[2]={work+An,work}; - Index n=An, base=-n, odd=0, c=0, b=1; - Index i=0; - for(;;) { + SortData<Value> * const buf[2] = { work + An, work }; + Index n = An, base = -n, odd = 0, c = 0, b = 1; + Index i = 0; + for (;;) + { SortData<Value> *p; - if((c&1)==0) { - base+=n, n+=(odd&1), c|=1, b^=1; - while(n>3) odd<<=1,odd|=(n&1),n>>=1,c<<=1,b^=1; - } else - base-=n-(odd&1),n<<=1,n-=(odd&1),odd>>=1,c>>=1; - if(c==0) break; - p = buf[b]+base; - if(n==2) { - Value v[2]; v[0]=*A,A+=stride,v[1]=*A,A+=stride; - if(v[1]<v[0]) p[0].v=v[1],p[0].i=i+1, p[1].v=v[0],p[1].i=i ; - else p[0].v=v[0],p[0].i=i , p[1].v=v[1],p[1].i=i+1; - i+=2; - } else if(n==3) { - Value v[3]; v[0]=*A,A+=stride,v[1]=*A,A+=stride,v[2]=*A,A+=stride; - if(v[1]<v[0]) { - if(v[2]<v[1]) p[0].v=v[2],p[1].v=v[1],p[2].v=v[0], - p[0].i=i+2 ,p[1].i=i+1 ,p[2].i=i ; - else { if(v[2]<v[0]) p[0].v=v[1],p[1].v=v[2],p[2].v=v[0], - p[0].i=i+1 ,p[1].i=i+2 ,p[2].i=i ; - else p[0].v=v[1],p[1].v=v[0],p[2].v=v[2], - p[0].i=i+1 ,p[1].i=i ,p[2].i=i+2 ; } - } else { - if(v[2]<v[0]) p[0].v=v[2],p[1].v=v[0],p[2].v=v[1], - p[0].i=i+2 ,p[1].i=i ,p[2].i=i+1 ; - else { if(v[2]<v[1]) p[0].v=v[0],p[1].v=v[2],p[2].v=v[1], - p[0].i=i ,p[1].i=i+2 ,p[2].i=i+1 ; - else p[0].v=v[0],p[1].v=v[1],p[2].v=v[2], - p[0].i=i ,p[1].i=i+1 ,p[2].i=i+2 ; } + if ((c & 1) == 0) + { + base += n, n += (odd & 1), c |= 1, b ^= 1; + while (n > 3) + odd <<= 1, odd |= (n & 1), n >>= 1, c <<= 1, b ^= 1; + } + else + base -= n - (odd & 1), n <<= 1, n -= (odd & 1), odd >>= 1, c >>= 1; + if (c == 0) + break; + p = buf[b] + base; + if (n == 2) + { + Value v[2]; + v[0] = *A, A += stride, v[1] = *A, A += stride; + if (v[1] < v[0]) + p[0].v = v[1], p[0].i = i + 1, p[1].v = v[0], p[1].i = i; + else + p[0].v = v[0], p[0].i = i, p[1].v = v[1], p[1].i = i + 1; + i += 2; + } + else if (n == 3) + { + Value v[3]; + v[0] = *A, A += stride, v[1] = *A, A += stride, v[2] = *A, A += stride; + if (v[1] < v[0]) + { + if (v[2] < v[1]) + p[0].v = v[2], p[1].v = v[1], p[2].v = v[0], p[0].i = i + 2, p[1].i = + i + 1, p[2].i = i; + else + { + if (v[2] < v[0]) + p[0].v = v[1], p[1].v = v[2], p[2].v = v[0], p[0].i = i + 1, p[1].i = + i + 2, p[2].i = i; + else + p[0].v = v[1], p[1].v = v[0], p[2].v = v[2], p[0].i = i + 1, p[1].i = + i, p[2].i = i + 2; + } } - i+=3; - } else { - const Index na = n>>1, nb = (n+1)>>1; - const SortData<Value> *ap = buf[b^1]+base, *ae = ap+na; - SortData<Value> *bp = p+na, *be = bp+nb; - for(;;) { - if(bp->v<ap->v) { - *p++=*bp++; - if(bp!=be) continue; - do *p++=*ap++; while(ap!=ae); + else + { + if (v[2] < v[0]) + p[0].v = v[2], p[1].v = v[0], p[2].v = v[1], p[0].i = i + 2, p[1].i = + i, p[2].i = i + 1; + else + { + if (v[2] < v[1]) + p[0].v = v[0], p[1].v = v[2], p[2].v = v[1], p[0].i = i, p[1].i = i + + 2, p[2].i = i + 1; + else + p[0].v = v[0], p[1].v = v[1], p[2].v = v[2], p[0].i = i, p[1].i = i + + 1, p[2].i = i + 2; + } + } + i += 3; + } + else + { + const Index na = n >> 1, nb = (n + 1) >> 1; + const SortData<Value> *ap = buf[b ^ 1] + base, *ae = ap + na; + SortData<Value> *bp = p + na, *be = bp + nb; + for (;;) + { + if (bp->v < ap->v) + { + *p++ = *bp++; + if (bp != be) + continue; + do + *p++ = *ap++; + while (ap != ae); break; - } else { - *p++=*ap++; - if(ap==ae) break; + } + else + { + *p++ = *ap++; + if (ap == ae) + break; } } } } { - const SortData<Value> *p = buf[0], *pe = p+An; - do *idx++ = (p++)->i; while(p!=pe); + const SortData<Value> *p = buf[0], *pe = p + An; + do + *idx++ = (p++)->i; + while (p != pe); } } template<class Value> -void TupleList::index_sort(const Value *A, Index n, Index stride, - Index *idx, SortData<Value> *work) +void TupleList::index_sort(const Value *A, Index n, Index stride, Index *idx, + SortData<Value> *work) { - if(n<DIGIT_VALUES) { - if(n==0) return; - if(n==1) *idx=0; - else merge_index_sort(A,n,stride,idx,work); - } else radix_index_sort(A,n,stride,idx,work); + if (n < DIGIT_VALUES) + { + if (n == 0) + return; + if (n == 1) + *idx = 0; + else + merge_index_sort(A, n, stride, idx, work); + } + else + radix_index_sort(A, n, stride, idx, work); } #undef DIGIT_BITS @@ -710,6 +856,5 @@ void TupleList::index_sort(const Value *A, Index n, Index stride, #undef COUNT_SIZE #undef sort_data_long - } //namespace This diff is so big that we needed to truncate the remainder. Repository URL: https://bitbucket.org/fathomteam/moab/ -- This is a commit notification from bitbucket.org. You are receiving this because you have the service enabled, addressing the recipient of this email.
participants (1)
-
commits-noreply＠bitbucket.org