1: #include <petsc/private/dmpleximpl.h>

  3: /*@
  4:   DMPlexPointQueueCreate - Create a `DMPlexPointQueue`, a simple FIFO queue of `PetscInt` mesh points used by `DMPLEX` traversal routines.

  6:   Not Collective

  8:   Input Parameter:
  9: . size - the initial capacity of the queue

 11:   Output Parameter:
 12: . queue - the newly created `DMPlexPointQueue`

 14:   Level: developer

 16:   Note:
 17:   The queue grows automatically when full; see `DMPlexPointQueueEnsureSize()`.

 19: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueDestroy()`, `DMPlexPointQueueEnqueue()`, `DMPlexPointQueueDequeue()`
 20: @*/
 21: PetscErrorCode DMPlexPointQueueCreate(PetscInt size, DMPlexPointQueue *queue)
 22: {
 23:   DMPlexPointQueue q;

 25:   PetscFunctionBegin;
 26:   PetscCheck(size >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Queue size %" PetscInt_FMT " must be non-negative", size);
 27:   PetscCall(PetscCalloc1(1, &q));
 28:   q->size = size;
 29:   PetscCall(PetscMalloc1(q->size, &q->points));
 30:   q->num   = 0;
 31:   q->front = 0;
 32:   q->back  = q->size - 1;
 33:   *queue   = q;
 34:   PetscFunctionReturn(PETSC_SUCCESS);
 35: }

 37: /*@
 38:   DMPlexPointQueueDestroy - Destroy a `DMPlexPointQueue` previously created with `DMPlexPointQueueCreate()`.

 40:   Not Collective

 42:   Input Parameter:
 43: . queue - the queue to destroy; set to `NULL` on return

 45:   Level: developer

 47: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueCreate()`
 48: @*/
 49: PetscErrorCode DMPlexPointQueueDestroy(DMPlexPointQueue *queue)
 50: {
 51:   DMPlexPointQueue q = *queue;

 53:   PetscFunctionBegin;
 54:   PetscCall(PetscFree(q->points));
 55:   PetscCall(PetscFree(q));
 56:   *queue = NULL;
 57:   PetscFunctionReturn(PETSC_SUCCESS);
 58: }

 60: /*@
 61:   DMPlexPointQueueEnsureSize - Ensure that a `DMPlexPointQueue` has room for at least one more entry, growing its capacity if it is full.

 63:   Not Collective

 65:   Input Parameter:
 66: . queue - the queue

 68:   Level: developer

 70: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueCreate()`, `DMPlexPointQueueEnqueue()`
 71: @*/
 72: PetscErrorCode DMPlexPointQueueEnsureSize(DMPlexPointQueue queue)
 73: {
 74:   PetscInt oldSize;

 76:   PetscFunctionBegin;
 77:   if (queue->num < queue->size) PetscFunctionReturn(PETSC_SUCCESS);
 78:   oldSize     = queue->size;
 79:   queue->size = PetscMax(2 * oldSize, 1);
 80:   PetscCall(PetscRealloc(queue->size * sizeof(PetscInt), &queue->points));
 81:   // Full ring: entries are front..oldSize-1 then 0..front-1, so move the wrapped part after the old end
 82:   if (queue->front > 0) PetscCall(PetscArraycpy(&queue->points[oldSize], queue->points, queue->front));
 83:   queue->back = queue->front + oldSize - 1;
 84:   PetscFunctionReturn(PETSC_SUCCESS);
 85: }

 87: /*@
 88:   DMPlexPointQueueEnqueue - Add a mesh point to the back of a `DMPlexPointQueue`.

 90:   Not Collective

 92:   Input Parameters:
 93: + queue - the queue
 94: - p     - the mesh point to enqueue

 96:   Level: developer

 98: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueDequeue()`, `DMPlexPointQueueBack()`
 99: @*/
100: PetscErrorCode DMPlexPointQueueEnqueue(DMPlexPointQueue queue, PetscInt p)
101: {
102:   PetscFunctionBegin;
103:   PetscCall(DMPlexPointQueueEnsureSize(queue));
104:   queue->back                = (queue->back + 1) % queue->size;
105:   queue->points[queue->back] = p;
106:   ++queue->num;
107:   PetscFunctionReturn(PETSC_SUCCESS);
108: }

110: /*@
111:   DMPlexPointQueueDequeue - Remove and return the mesh point at the front of a `DMPlexPointQueue`.

113:   Not Collective

115:   Input Parameter:
116: . queue - the queue

118:   Output Parameter:
119: . p - the mesh point that was at the front of the queue

121:   Level: developer

123:   Note:
124:   It is an error to dequeue from an empty queue; use `DMPlexPointQueueEmpty()` to check first.

126: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueEnqueue()`, `DMPlexPointQueueFront()`, `DMPlexPointQueueEmpty()`
127: @*/
128: PetscErrorCode DMPlexPointQueueDequeue(DMPlexPointQueue queue, PetscInt *p)
129: {
130:   PetscFunctionBegin;
131:   PetscCheck(queue->num, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Cannot dequeue from an empty queue");
132:   *p           = queue->points[queue->front];
133:   queue->front = (queue->front + 1) % queue->size;
134:   --queue->num;
135:   PetscFunctionReturn(PETSC_SUCCESS);
136: }

138: /*@
139:   DMPlexPointQueueFront - Return, without removing, the mesh point at the front of a `DMPlexPointQueue`.

141:   Not Collective

143:   Input Parameter:
144: . queue - the queue

146:   Output Parameter:
147: . p - the mesh point at the front of the queue

149:   Level: developer

151: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueBack()`, `DMPlexPointQueueDequeue()`, `DMPlexPointQueueEmpty()`
152: @*/
153: PetscErrorCode DMPlexPointQueueFront(DMPlexPointQueue queue, PetscInt *p)
154: {
155:   PetscFunctionBegin;
156:   PetscCheck(queue->num, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Cannot get the front of an empty queue");
157:   *p = queue->points[queue->front];
158:   PetscFunctionReturn(PETSC_SUCCESS);
159: }

161: /*@
162:   DMPlexPointQueueBack - Return, without removing, the mesh point at the back of a `DMPlexPointQueue`.

164:   Not Collective

166:   Input Parameter:
167: . queue - the queue

169:   Output Parameter:
170: . p - the mesh point at the back of the queue

172:   Level: developer

174: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueFront()`, `DMPlexPointQueueEnqueue()`, `DMPlexPointQueueEmpty()`
175: @*/
176: PetscErrorCode DMPlexPointQueueBack(DMPlexPointQueue queue, PetscInt *p)
177: {
178:   PetscFunctionBegin;
179:   PetscCheck(queue->num, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Cannot get the back of an empty queue");
180:   *p = queue->points[queue->back];
181:   PetscFunctionReturn(PETSC_SUCCESS);
182: }

184: /*@
185:   DMPlexPointQueueEmpty - Returns `PETSC_TRUE` if the queue is empty

187:   Not Collective

189:   Input Parameter:
190: . queue - the queue

192:   Level: developer

194:   Note:
195:   Unlike most PETSc functions this does not return an error code.

197: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueFront()`, `DMPlexPointQueueEnqueue()`
198: @*/
199: PetscBool DMPlexPointQueueEmpty(DMPlexPointQueue queue)
200: {
201:   if (!queue->num) return PETSC_TRUE;
202:   return PETSC_FALSE;
203: }

205: /*@
206:   DMPlexPointQueueEmptyCollective - Collectively determine whether a `DMPlexPointQueue` is empty on every process of an MPI communicator.

208:   Collective

210:   Input Parameters:
211: + obj   - a `PetscObject` whose MPI communicator is used for the reduction
212: - queue - the queue

214:   Output Parameter:
215: . empty - `PETSC_TRUE` if the queue is empty on every process in the MPI communicator, `PETSC_FALSE` otherwise

217:   Level: developer

219: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueEmpty()`
220: @*/
221: PetscErrorCode DMPlexPointQueueEmptyCollective(PetscObject obj, DMPlexPointQueue queue, PetscBool *empty)
222: {
223:   PetscFunctionBeginHot;
224:   *empty = DMPlexPointQueueEmpty(queue);
225:   PetscCallMPI(MPIU_Allreduce(MPI_IN_PLACE, empty, 1, MPI_C_BOOL, MPI_LAND, PetscObjectComm(obj)));
226:   PetscFunctionReturn(PETSC_SUCCESS);
227: }