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, doubling 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:   PetscFunctionBegin;
 75:   if (queue->num < queue->size) PetscFunctionReturn(PETSC_SUCCESS);
 76:   queue->size *= 2;
 77:   PetscCall(PetscRealloc(queue->size * sizeof(PetscInt), &queue->points));
 78:   PetscFunctionReturn(PETSC_SUCCESS);
 79: }

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

 84:   Not Collective

 86:   Input Parameters:
 87: + queue - the queue
 88: - p     - the mesh point to enqueue

 90:   Level: developer

 92: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueDequeue()`, `DMPlexPointQueueBack()`
 93: @*/
 94: PetscErrorCode DMPlexPointQueueEnqueue(DMPlexPointQueue queue, PetscInt p)
 95: {
 96:   PetscFunctionBegin;
 97:   PetscCall(DMPlexPointQueueEnsureSize(queue));
 98:   queue->back                = (queue->back + 1) % queue->size;
 99:   queue->points[queue->back] = p;
100:   ++queue->num;
101:   PetscFunctionReturn(PETSC_SUCCESS);
102: }

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

107:   Not Collective

109:   Input Parameter:
110: . queue - the queue

112:   Output Parameter:
113: . p - the mesh point that was at the front of the queue

115:   Level: developer

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

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

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

135:   Not Collective

137:   Input Parameter:
138: . queue - the queue

140:   Output Parameter:
141: . p - the mesh point at the front of the queue

143:   Level: developer

145: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueBack()`, `DMPlexPointQueueDequeue()`, `DMPlexPointQueueEmpty()`
146: @*/
147: PetscErrorCode DMPlexPointQueueFront(DMPlexPointQueue queue, PetscInt *p)
148: {
149:   PetscFunctionBegin;
150:   PetscCheck(queue->num, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Cannot get the front of an empty queue");
151:   *p = queue->points[queue->front];
152:   PetscFunctionReturn(PETSC_SUCCESS);
153: }

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

158:   Not Collective

160:   Input Parameter:
161: . queue - the queue

163:   Output Parameter:
164: . p - the mesh point at the back of the queue

166:   Level: developer

168: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueFront()`, `DMPlexPointQueueEnqueue()`, `DMPlexPointQueueEmpty()`
169: @*/
170: PetscErrorCode DMPlexPointQueueBack(DMPlexPointQueue queue, PetscInt *p)
171: {
172:   PetscFunctionBegin;
173:   PetscCheck(queue->num, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, "Cannot get the back of an empty queue");
174:   *p = queue->points[queue->back];
175:   PetscFunctionReturn(PETSC_SUCCESS);
176: }

178: PetscBool DMPlexPointQueueEmpty(DMPlexPointQueue queue)
179: {
180:   if (!queue->num) return PETSC_TRUE;
181:   return PETSC_FALSE;
182: }

184: /*@
185:   DMPlexPointQueueEmptyCollective - Collectively determine whether a `DMPlexPointQueue` is empty on every rank of a communicator.

187:   Collective

189:   Input Parameters:
190: + obj   - a `PetscObject` whose communicator is used for the reduction
191: - queue - the queue

193:   Output Parameter:
194: . empty - `PETSC_TRUE` if the queue is empty on every rank, `PETSC_FALSE` otherwise

196:   Level: developer

198: .seealso: `DMPLEX`, `DMPlexPointQueue`, `DMPlexPointQueueEmpty()`
199: @*/
200: PetscErrorCode DMPlexPointQueueEmptyCollective(PetscObject obj, DMPlexPointQueue queue, PetscBool *empty)
201: {
202:   PetscFunctionBeginHot;
203:   *empty = DMPlexPointQueueEmpty(queue);
204:   PetscCallMPI(MPIU_Allreduce(MPI_IN_PLACE, empty, 1, MPI_C_BOOL, MPI_LAND, PetscObjectComm(obj)));
205:   PetscFunctionReturn(PETSC_SUCCESS);
206: }