bucket.c File Reference

#include <space.h>

Go to the source code of this file.

Functions
bucket_t *	newBucket (PORD_INT maxbin, PORD_INT maxitem, PORD_INT offset)
void	freeBucket (bucket_t *bucket)
bucket_t *	setupBucket (PORD_INT maxbin, PORD_INT maxitem, PORD_INT offset)
PORD_INT	minBucket (bucket_t *bucket)
void	insertBucket (bucket_t *bucket, PORD_INT k, PORD_INT item)
void	removeBucket (bucket_t *bucket, PORD_INT item)

Function Documentation

freeBucket()

void freeBucket

(

bucket_t *

bucket

)

Definition at line 78 of file bucket.c.

{
  free(bucket->bin);
  free(bucket->next);
  free(bucket->last);
  free(bucket->key);
  free(bucket);
}

insertBucket()

void insertBucket	(	bucket_t *	bucket,
		PORD_INT	k,
		PORD_INT	item )

Definition at line 163 of file bucket.c.

{ PORD_INT s, nextitem;
 
  /* ------------------------------------
     check whether there are any problems
     ------------------------------------ */
  if (abs(k) >= MAX_INT - bucket->offset - 1)
   { fprintf(stderr, "\nError in function insertBucket\n"
          "  key %d too large/small for bucket\n", k);
     quit();
   }
  if (item > bucket->maxitem)
   { fprintf(stderr, "\nError in function insertBucket\n"
          "  item %d too large for bucket (maxitem is %d)\n", item,
          bucket->maxitem);
     quit();
   }
  if (bucket->key[item] != MAX_INT)
   { fprintf(stderr, "\nError in function insertBucket\n"
          "  item %d already in bucket\n", item);
     quit();
   }
 
  /* -------------------------------------
     determine the bin that holds the item
     ------------------------------------- */
  s = max(0, (k + bucket->offset));
  s = min(s, bucket->maxbin);
 
  /* --------------------------------------------------------------
     adjust minbin, increase nobj, and mark item as being in bucket
     -------------------------------------------------------------- */
  bucket->minbin = min(bucket->minbin, s);
  bucket->nobj++;
  bucket->key[item] = k;
 
  /* -----------------------------
     finally, insert item in bin s
     ----------------------------- */
  nextitem = bucket->bin[s];
  if (nextitem != -1)
    bucket->last[nextitem] = item;
  bucket->next[item] = nextitem;
  bucket->last[item] = -1;
  bucket->bin[s] = item;
}

minBucket()

PORD_INT minBucket

(

bucket_t *

bucket

)

Definition at line 117 of file bucket.c.

{ PORD_INT *bin, *next, *key, maxbin, minbin, nobj;
  PORD_INT item, bestitem, bestkey;
 
  maxbin = bucket->maxbin;
  nobj = bucket->nobj;
  minbin = bucket->minbin;
  bin = bucket->bin;
  next = bucket->next;
  key = bucket->key;
 
  if (nobj > 0)
   { /* ---------------------------------------------
        get the first item from leftmost nonempty bin
        --------------------------------------------- */
     while (bin[minbin] == -1) minbin++;
     bucket->minbin = minbin;
     bestitem = bin[minbin];
     bestkey = minbin;
 
     /* --------------------------------------------------
        items in bins 0 and maxbin can have different keys
        => search for item with smallest key
        -------------------------------------------------- */
     if ((minbin == 0) || (minbin == maxbin))
      { item = next[bestitem];
        while (item != -1)
         { if (key[item] < bestkey)
            { bestitem = item;
              bestkey = key[item];
            }
           item = next[item];
         }
      }
     /* ---------------------------------
        return the item with smallest key
        --------------------------------- */
     return(bestitem);
   }
  else return(-1);
}

newBucket()

bucket_t * newBucket	(	PORD_INT	maxbin,
		PORD_INT	maxitem,
		PORD_INT	offset )

Definition at line 56 of file bucket.c.

{ bucket_t *bucket;
 
  mymalloc(bucket, 1, bucket_t);
  mymalloc(bucket->bin, (maxbin+1), PORD_INT);
  mymalloc(bucket->next, (maxitem+1), PORD_INT);
  mymalloc(bucket->last, (maxitem+1), PORD_INT);
  mymalloc(bucket->key, (maxitem+1), PORD_INT);
 
  bucket->maxbin = maxbin;
  bucket->maxitem = maxitem;
  bucket->offset = offset;
  bucket->nobj = 0;
  bucket->minbin = MAX_INT;
 
  return(bucket);
}

removeBucket()

void removeBucket	(	bucket_t *	bucket,
		PORD_INT	item )

Definition at line 214 of file bucket.c.

{ PORD_INT s, nextitem, lastitem;
 
  /* ----------------------------
     check whether item in bucket
     ---------------------------- */
  if (bucket->key[item] == MAX_INT)
   { fprintf(stderr, "\nError in function removeBucket\n"
          "  item %d is not in bucket\n", item);
     quit();
   }
 
  /* -----------------------
     remove item from bucket
     ----------------------- */
  nextitem = bucket->next[item];
  lastitem = bucket->last[item];
  if (nextitem != -1)
    bucket->last[nextitem] = lastitem;
  if (lastitem != -1)
    bucket->next[lastitem] = nextitem;
  else
   { s = max(0, (bucket->key[item] + bucket->offset));
     s = min(s, bucket->maxbin);
     bucket->bin[s] = nextitem;
   }
 
  /* --------------------------------------------
     decrease nobj and mark item as being removed
     -------------------------------------------- */
  bucket->nobj--;
  bucket->key[item] = MAX_INT;
}

setupBucket()

bucket_t * setupBucket	(	PORD_INT	maxbin,
		PORD_INT	maxitem,
		PORD_INT	offset )

Definition at line 91 of file bucket.c.

{ bucket_t *bucket;
  PORD_INT      i, u;
 
  if (offset < 0)
   { fprintf(stderr, "\nError in function setupBucket\n"
          "  offset must be >= 0\n");
     quit();
   }
 
  bucket = newBucket(maxbin, maxitem, offset);
 
  for (i = 0; i <= maxbin; i++)
    bucket->bin[i] = -1;
  for (u = 0; u <= maxitem; u++)
    { bucket->next[u] = bucket->last[u] = -1;
      bucket->key[u] = MAX_INT;
    }
 
  return(bucket);
}