Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Compound Members | File Members

int.Vec.cc File Reference

#include <stdlib.h>
#include "lib/builtin.h"
#include "lib/int.Vec.h"

Include dependency graph for int.Vec.cc:

Include dependency graph

Go to the source code of this file.

Defines

#define BYTES_PER_WORD   8
#define BYTES_PER_LONG   4
#define STACK_SIZE   (BYTES_PER_WORD * BYTES_PER_LONG)
#define PUSH(LOW, HIGH)   do {top->lo = LOW;top++->hi = HIGH;} while (0)
#define POP(LOW, HIGH)   do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
#define STACK_NOT_EMPTY   (stack < top)
#define MAX_THRESH   4

Functions

void default_intVec_error_handler (const char *msg)
one_arg_error_handler_t set_intVec_error_handler (one_arg_error_handler_t f)
intVec concat (intVec &a, intVec &b)
intVec combine (intCombiner f, intVec &a, intVec &b)
intVec reverse (intVec &a)
intVec map (intMapper f, intVec &a)
int operator== (intVec &a, intVec &b)
intVec merge (intVec &a, intVec &b, intComparator f)
int gsort (int *, int, intComparator)
void SWAP (int *A, int *B)

Variables

one_arg_error_handler_t intVec_error_handler = default_intVec_error_handler

Define Documentation

#define BYTES_PER_LONG   4
 

Definition at line 289 of file int.Vec.cc.

#define BYTES_PER_WORD   8
 

Definition at line 288 of file int.Vec.cc.

#define MAX_THRESH   4
 

Definition at line 300 of file int.Vec.cc.

Referenced by gsort().

#define POP (  LOW,
HIGH   )     do {LOW = (--top)->lo;HIGH = top->hi;} while (0)
 

Definition at line 295 of file int.Vec.cc.

Referenced by gsort().

#define PUSH (  LOW,
HIGH   )     do {top->lo = LOW;top++->hi = HIGH;} while (0)
 

Definition at line 294 of file int.Vec.cc.

Referenced by gsort().

#define STACK_NOT_EMPTY   (stack < top)
 

Definition at line 296 of file int.Vec.cc.

Referenced by gsort().

#define STACK_SIZE   (BYTES_PER_WORD * BYTES_PER_LONG)
 

Definition at line 293 of file int.Vec.cc.

Referenced by gsort().

Function Documentation

intVec combine (  intCombiner  f,
intVec &  a,
intVec &  b
) 
 

Definition at line 128 of file int.Vec.cc.

References intVec::len, and intVec::s. 

00129 {
00130   int newl = (a.len < b.len)? a.len : b.len;
00131   int* news = new int [newl];
00132   int* p = news;
00133   int* top = &(a.s[newl]);
00134   int* t = a.s;
00135   int* u = b.s;
00136   while (t < top) *p++ = (*f)(*t++, *u++);
00137   return intVec(newl, news);
00138 }

intVec concat (  intVec &  a,
intVec &  b
) 
 

Definition at line 113 of file int.Vec.cc.

References intVec::len, and intVec::s. 

00114 {
00115   int newl = a.len + b.len;
00116   int* news = new int [newl];
00117   int* p = news;
00118   int* top = &(a.s[a.len]);
00119   int* t = a.s;
00120   while (t < top) *p++ = *t++;
00121   top = &(b.s[b.len]);
00122   t = b.s;
00123   while (t < top) *p++ = *t++;
00124   return intVec(newl, news);
00125 }

void default_intVec_error_handler (  const char *  msg  ) 
 

Definition at line 30 of file int.Vec.cc. 

00031 {
00032 #if 0
00033   cerr << "Fatal intVec error. " << msg << "\n";
00034 #else
00035   // ns doesn't use streams
00036   fprintf(stderr, "Fatal intVec error. %s\n", msg);
00037 #endif
00038   exit(1);
00039 }

int gsort (  int *  ,
int  ,
intComparator 
)  [static]
 

Definition at line 327 of file int.Vec.cc.

References MAX_THRESH, POP, PUSH, STACK_NOT_EMPTY, STACK_SIZE, and SWAP().

Referenced by intVec::sort(). 

00328 {
00329 /* Stack node declarations used to store unfulfilled partition obligations. */
00330   struct stack_node {  int *lo;  int *hi; };
00331   int   pivot_buffer;
00332   int   max_thresh   = MAX_THRESH;
00333 
00334   if (total_elems > MAX_THRESH)
00335     {
00336       int       *lo = base_ptr;
00337       int       *hi = lo + (total_elems - 1);
00338       int       *left_ptr;
00339       int       *right_ptr;
00340       stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */
00341       stack_node *top = stack + 1;
00342 
00343       while (STACK_NOT_EMPTY)
00344         {
00345           {
00346             int *pivot = &pivot_buffer;
00347             {
00348               /* Select median value from among LO, MID, and HI. Rearrange
00349                  LO and HI so the three values are sorted. This lowers the 
00350                  probability of picking a pathological pivot value and 
00351                  skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
00352 
00353               int *mid = lo + ((hi - lo) >> 1);
00354 
00355               if ((*cmp) (*mid, *lo) < 0)
00356                 SWAP (mid, lo);
00357               if ((*cmp) (*hi, *mid) < 0)
00358               {
00359                 SWAP (mid, hi);
00360                 if ((*cmp) (*mid, *lo) < 0)
00361                   SWAP (mid, lo);
00362               }
00363               *pivot = *mid;
00364               pivot = &pivot_buffer;
00365             }
00366             left_ptr  = lo + 1;
00367             right_ptr = hi - 1; 
00368 
00369             /* Here's the famous ``collapse the walls'' section of quicksort.  
00370                Gotta like those tight inner loops!  They are the main reason 
00371                that this algorithm runs much faster than others. */
00372             do 
00373               {
00374                 while ((*cmp) (*left_ptr, *pivot) < 0)
00375                   left_ptr += 1;
00376 
00377                 while ((*cmp) (*pivot, *right_ptr) < 0)
00378                   right_ptr -= 1;
00379 
00380                 if (left_ptr < right_ptr) 
00381                   {
00382                     SWAP (left_ptr, right_ptr);
00383                     left_ptr += 1;
00384                     right_ptr -= 1;
00385                   }
00386                 else if (left_ptr == right_ptr) 
00387                   {
00388                     left_ptr += 1;
00389                     right_ptr -= 1;
00390                     break;
00391                   }
00392               } 
00393             while (left_ptr <= right_ptr);
00394 
00395           }
00396 
00397           /* Set up pointers for next iteration.  First determine whether
00398              left and right partitions are below the threshold size. If so, 
00399              ignore one or both.  Otherwise, push the larger partition's
00400              bounds on the stack and continue sorting the smaller one. */
00401 
00402           if ((right_ptr - lo) <= max_thresh)
00403             {
00404               if ((hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */
00405                 POP (lo, hi); 
00406               else              /* Ignore small left partition. */  
00407                 lo = left_ptr;
00408             }
00409           else if ((hi - left_ptr) <= max_thresh) /* Ignore small right partition. */
00410             hi = right_ptr;
00411           else if ((right_ptr - lo) > (hi - left_ptr)) /* Push larger left partition indices. */
00412             {                   
00413               PUSH (lo, right_ptr);
00414               lo = left_ptr;
00415             }
00416           else                  /* Push larger right partition indices. */
00417             {                   
00418               PUSH (left_ptr, hi);
00419               hi = right_ptr;
00420             }
00421         }
00422     }
00423 
00424   /* Once the BASE_PTR array is partially sorted by quicksort the rest
00425      is completely sorted using insertion sort, since this is efficient 
00426      for partitions below MAX_THRESH size. BASE_PTR points to the beginning 
00427      of the array to sort, and END_PTR points at the very last element in
00428      the array (*not* one beyond it!). */
00429 
00430 
00431   {
00432     int *end_ptr = base_ptr + 1 * (total_elems - 1);
00433     int *run_ptr;
00434     int *tmp_ptr = base_ptr;
00435     int *thresh  = (end_ptr < (base_ptr + max_thresh))? 
00436       end_ptr : (base_ptr + max_thresh);
00437 
00438     /* Find smallest element in first threshold and place it at the
00439        array's beginning.  This is the smallest array element,
00440        and the operation speeds up insertion sort's inner loop. */
00441 
00442     for (run_ptr = tmp_ptr + 1; run_ptr <= thresh; run_ptr += 1)
00443       if ((*cmp) (*run_ptr, *tmp_ptr) < 0)
00444         tmp_ptr = run_ptr;
00445 
00446     if (tmp_ptr != base_ptr)
00447       SWAP (tmp_ptr, base_ptr);
00448 
00449     /* Insertion sort, running from left-hand-side up to `right-hand-side.' 
00450        Pretty much straight out of the original GNU qsort routine. */
00451 
00452     for (run_ptr = base_ptr + 1; (tmp_ptr = run_ptr += 1) <= end_ptr; )
00453       {
00454 
00455         while ((*cmp) (*run_ptr, *(tmp_ptr -= 1)) < 0)
00456           ;
00457 
00458         if ((tmp_ptr += 1) != run_ptr)
00459           {
00460             int *trav;
00461 
00462             for (trav = run_ptr + 1; --trav >= run_ptr;)
00463               {
00464                 int c = *trav;
00465                 int *hi, *lo;
00466 
00467                 for (hi = lo = trav; (lo -= 1) >= tmp_ptr; hi = lo)
00468                   *hi = *lo;
00469                 *hi = c;
00470               }
00471           }
00472 
00473       }
00474   }
00475   return 1;
00476 }

Here is the call graph for this function:

intVec map (  intMapper  f,
intVec &  a
) 
 

Definition at line 187 of file int.Vec.cc.

References intVec::len, and intVec::s. 

00188 {
00189   int* news = new int [a.len];
00190   int* p = news;
00191   int* top = &(a.s[a.len]);
00192   int* t = a.s;
00193   while(t < top) *p++ = (*f)(*t++);
00194   return intVec(a.len, news);
00195 }

intVec merge (  intVec &  a,
intVec &  b,
intComparator  f
) 
 

Definition at line 242 of file int.Vec.cc.

References intVec::len, and intVec::s. 

00243 {
00244   int newl = a.len + b.len;
00245   int* news = new int [newl];
00246   int* p = news;
00247   int* topa = &(a.s[a.len]);
00248   int* as = a.s;
00249   int* topb = &(b.s[b.len]);
00250   int* bs = b.s;
00251 
00252   for (;;)
00253   {
00254     if (as >= topa)
00255     {
00256       while (bs < topb) *p++ = *bs++;
00257       break;
00258     }
00259     else if (bs >= topb)
00260     {
00261       while (as < topa) *p++ = *as++;
00262       break;
00263     }
00264     else if ((*f)(*as, *bs) <= 0)
00265       *p++ = *as++;
00266     else
00267       *p++ = *bs++;
00268   }
00269   return intVec(newl, news);
00270 }

int operator== (  intVec &  a,
intVec &  b
) 
 

Definition at line 197 of file int.Vec.cc.

References intEQ, intVec::len, and intVec::s. 

00198 {
00199   if (a.len != b.len)
00200     return 0;
00201   int* top = &(a.s[a.len]);
00202   int* t = a.s;
00203   int* u = b.s;
00204   while (t < top) if (!(intEQ(*t++, *u++))) return 0;
00205   return 1;
00206 }

intVec reverse (  intVec &  a  ) 
 

Definition at line 149 of file int.Vec.cc.

References intVec::len. 

00150 {
00151   int* news = new int [a.len];
00152   if (a.len != 0)
00153   {
00154     int* lo = news;
00155     int* hi = &(news[a.len - 1]);
00156     while (lo < hi)
00157     {
00158       int tmp = *lo;
00159       *lo++ = *hi;
00160       *hi-- = tmp;
00161     }
00162   }
00163   return intVec(a.len, news);
00164 }

one_arg_error_handler_t set_intVec_error_handler (  one_arg_error_handler_t  f  ) 
 

Definition at line 43 of file int.Vec.cc.

References intVec_error_handler, and one_arg_error_handler_t. 

00044 {
00045   one_arg_error_handler_t old = intVec_error_handler;
00046   intVec_error_handler = f;
00047   return old;
00048 }

void SWAP (  int *  A,
int *  B
)  [inline, static]
 

Definition at line 282 of file int.Vec.cc.

Referenced by gsort(). 

00283 {
00284   int tmp = *A; *A = *B; *B = tmp;
00285 }

Variable Documentation

one_arg_error_handler_t intVec_error_handler = default_intVec_error_handler
 

Definition at line 41 of file int.Vec.cc.

Referenced by set_intVec_error_handler().

Generated on Tue Apr 20 12:21:41 2004 for NS2.26SourcesOriginal by doxygen 1.3.3