![[Previous]](ttlprev.gif)
![[HOME]](ttlhome.gif)
![[NEXT]](ttlnxt.gif)
/* =======================================================================
heap.h
====================================================================== */
#ifndef HEAP_H
#define HEAP_H
/*--- use char for bards > 128x128 and less than 256x256 ---*/
typedef signed char INDEX;
typedef struct HeapCell HEAPCELL;
struct HeapCell
{
int *SubTree;
HEAPCELL *prev;
HEAPCELL *next;
};
typedef struct HeapType HEAPTYPE;
struct HeapType
{
int HeapTop;
HEAPCELL *front;
HEAPCELL *back;
int *SubTreeHeight;
int Locked;
int Initialized;
};
int EmptyHeap(void);
void Lock(HEAPTYPE *HeapP);
void Unlock(HEAPTYPE *HeapP);
int GetTopTree(int *tree);
int GetTopTreeAndLeaf(int *tree, int *Leaf);
void InsertHeap(int *Tree);
void GetLoad(int *Height, int *Number);
void InitializeHeap(int N);
void SafeInsertHeap(int *Tree);
#endif
/* =======================================================================
heap.c
D. Thiebaut Department of Computer Science
thiebaut@sophia.smith.edu Smith College
Northampton, MA 01063
DESCRIPTION:
This module implements the heap where the trees corresponding to
partial solutions are kept.
====================================================================== */
#include <stdio.h>
#include <stdlib.h>
#include "balance.h"
#include "conc.h"
#include "heap.h"
/*--- The heap data structure ---*/
HEAPTYPE Heap = { 0, /* heaptop */
NULL, /* front */
NULL, /* back */
NULL, /* SubTreeHeight */
1, /* locked */
0}; /* initialized */
extern int NoNodes; /* Number of transputers in network */
extern int N; /* size of chessboard */
/* -------------------------------------------------------------------- */
/* EMPTYHEAP: Returns status of the heap (1 for empty, 0 for not empty) */
/* -------------------------------------------------------------------- */
int EmptyHeap(void)
{
return (Heap.HeapTop==0);
}
/* -------------------------------------------------------------------- */
/* INITIALIZEHEAP: */
/* Creates the heap data structure and assigns trees to the nodes as */
/* follows. All first possible positions for the queen in the first row*/
/* are distributed to all the nodes, in a round-robin fashion. */
/* SubTreeHeight[i] contains the number of trees of height i */
/* -------------------------------------------------------------------- */
void InitializeHeap(int N)
{
int i, Tree[2];
/*--- create array of SubTreeHeight height ---*/
Heap.SubTreeHeight = (int *) safemalloc((int) ((N+1)*SIZEINT));
for (i = 0; i<=N; i++)
Heap.SubTreeHeight[i] = 0;
/*--- initialize the heap with 1/N of the trees ---*/
/*--- (because of symmetry) ---*/
for (i = 0; i<N/2; i++)
{
if (i%NoNodes!=_node_number-1)
continue;
Tree[0] = 1;
Tree[1] = i+1;
SafeInsertHeap(Tree);
}
/*--- allow load-balancing and search modules to access heap ---*/
Unlock(&Heap);
Heap.Initialized = 1;
}
/* -------------------------------------------------------------------- */
/* GETLOAD: */
/* Returns the number of tallest trees in the heap. */
/* -------------------------------------------------------------------- */
void GetLoad(int *Height, int *Number)
{
int i;
*Height = 0;
*Number = 0;
/*--- Heap not created yet? ---*/
if (!Heap.Initialized)
{
i = ProcToLow();
while (!Heap.Initialized)
ProcReschedule();
if (i==0)
ProcToHigh();
}
/*--- Find deepest tree ---*/
for (i = N; i>=0; i--)
if (Heap.SubTreeHeight[i]!=0)
{
*Height = i;
*Number = Heap.SubTreeHeight[i];
return;
}
}
/* -------------------------------------------------------------------- */
/* INSERTHEAP: */
/* Add a new tree to the heap */
/* -------------------------------------------------------------------- */
void InsertHeap(int *Tree)
{
/*--- secure priviledged access ---*/
Lock(&Heap);
SafeInsertHeap(Tree);
/*--- release lock ---*/
Unlock(&Heap);
}
/* -------------------------------------------------------------------- */
/* SAFEINSERTHEAP: */
/* Add a new tree to the heap. Assumes that the heap is already locked */
/* and that it is safe to access it directly. */
/* -------------------------------------------------------------------- */
void SafeInsertHeap(int *Tree)
{
HEAPCELL *p;
int i;
/*--- copy tree in newly created storage ---*/
p = (HEAPCELL *) safemalloc((int) sizeof(HEAPCELL));
p->SubTree = (int *) safemalloc((int) ((Tree[0]+1)*SIZEINT));
for (i = 0; i<=Tree[0]; i++)
p->SubTree[i] = Tree[i];
/*--- update heap statistics ---*/
Heap.SubTreeHeight[Tree[0]] += 1; /* one more subtree */
Heap.HeapTop += 1;
/*--- add to heap linked-list ---*/
if (Heap.front==NULL)
{
Heap.front = p;
Heap.back = p;
p->prev = p;
p->next = p;
}
else
{
p->prev = Heap.back;
p->next = Heap.front;
Heap.back->next = p;
Heap.front->prev = p;
Heap.back = p;
}
}
/* -------------------------------------------------------------------- */
/* GETTOPTREE: */
/* Removes the tree from the top of the heap. */
/* -------------------------------------------------------------------- */
int GetTopTree(int *TreeBuffer)
{
int dummy;
return GetTopTreeAndLeaf(TreeBuffer, &dummy);
}
/* -------------------------------------------------------------------- */
/* GETTOPTREEANDLEAF: */
/* Removes the top tree from the heap and returns the index of its last */
/* node (leaf). */
/* -------------------------------------------------------------------- */
int GetTopTreeAndLeaf(int *CurrentTree, int *CurrentLeafP)
{
HEAPCELL *p;
/*--- secure priviledge access ---*/
Lock(&Heap);
if (Heap.HeapTop<=0)
{
Unlock(&Heap);
return (CurrentTree[0] = 0);
}
(Heap.HeapTop)--;
p = Heap.back;
/*--- Copy tree to CurrentTree, use CurrentLeaf as index ---*/
for (*CurrentLeafP = 0; *CurrentLeafP<=p->SubTree[0];
(*CurrentLeafP)++)
CurrentTree[*CurrentLeafP] = p->SubTree[*CurrentLeafP];
/*--- adjust ---*/
(*CurrentLeafP)--;
/*--- there is now 1 fewer subtree of height CurrentTree[0] ---*/
Heap.SubTreeHeight[CurrentTree[0]] -= 1;
/*--- remove the tree ---*/
p->prev->next = Heap.front;
Heap.back = p->prev;
Heap.front->prev = Heap.back;
free(p->SubTree);
free(p);
/*--- Adjust the heap ---*/
if (Heap.HeapTop==0)
{
Heap.front = NULL;
Heap.back = NULL;
}
/*--- release lock ---*/
Unlock(&Heap);
}
/* -------------------------------------------------------------------- */
/* LOCK: */
/* Requests access to the heap, and once access is granted, locks the */
/* use of the heap to the requester. */
/* -------------------------------------------------------------------- */
void Lock(HEAPTYPE *HeapP)
{
int OldPrio;
/*--- remember priority upon entering ---*/
OldPrio = ProcToHigh();
/*--- spin if heap already locked ---*/
while (HeapP->Locked)
{
ProcToLow();
while (HeapP->Locked)
ProcReschedule();
ProcToHigh();
}
/*--- lock the heap ---*/
HeapP->Locked = 1;
/*--- return priority to original level ---*/
if (OldPrio==1)
ProcToLow();
}
/* -------------------------------------------------------------------- */
/* UNLOCK */
/* Reverses the effects of lock() */
/* -------------------------------------------------------------------- */
void Unlock(HEAPTYPE *HeapP)
{
/*--- The caller must be the owner of the lock, so
no need to check for anything ---*/
HeapP->Locked = 0;
}
Note that when the heap is initialized, it is loaded automatically with trees containing only 1 queen, located on the top row of the board. The node with _node_number equal to 1 will receive a tree with the queen located in the first column of the first row. Node 2 will receive a tree with the queen located in the second column, and so on. This is an example of an indexing function, as seen in Chapter 9. But instead of the assignment including all the N possible positions on the first row, it only covers the first N/2 since the solutions starting with queens located on the second half of the row will be symmetrical copies of solutions for the queens on the first half. When the number of processors (NoNodes) is larger than the size of the board (N), this allows several processors to work on trees with identical roots. The load-balancing module gathers information about the number of solutions found by the different nodes, as part of its regular load information gathering, and insures that the program will stop when a sufficient number of solutions are found.
The second portion of code we highlighted contains the lock and unlock functions. They are required because the heap is accessed by two different modules: the search module, which adds newly found trees and removes the top tree from time to time to investigate new solution paths, and the load-balancing module, which adds or removes trees as part of its balancing operation. We could have implemented any of the semaphore mechanisms we covered in Chapter 7, but we elected to explore a different solution involving the testing of the locked field of the heap data structure. This field is used to protect and define critical sections where a tree is either added (pushed on-) to the heap, or removed (popped out) from it. Upon calling lock() and finding the heap locked, a task will deschedule and demote itself to low priority until it sees the resource unlocked. As soon as this happens it quickly moves to high priority and locks the resource. Note that the code is robust, and that if the resource gets locked right after the test, the lock() function will return back to a waiting mode.
Unlock() is trivial, since it can be called only by a task having sole access to the resource, and there is no need for priority changes or testing. The field locked is simply reset to 0.