[pcsx_rearmed.git] / deps / libretro-common / queues / message_queue.c

/* Copyright  (C) 2010-2020 The RetroArch team
 *
 * ---------------------------------------------------------------------------------------
 * The following license statement only applies to this file (message_queue.c).
 * ---------------------------------------------------------------------------------------
 *
 * Permission is hereby granted, free of charge,
 * to any person obtaining a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
 * and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include <stdlib.h>
#include <string.h>

#include <boolean.h>
#include <queues/message_queue.h>
#include <compat/strl.h>
#include <compat/posix_string.h>

static bool msg_queue_initialize_internal(msg_queue_t *queue, size_t size)
{
   struct queue_elem **elems = (struct queue_elem**)calloc(size + 1,
         sizeof(struct queue_elem*));

   if (!elems)
      return false;

   queue->tmp_msg            = NULL;
   queue->elems              = elems;
   queue->ptr                = 1;
   queue->size               = size + 1;

   return true;
}

/**
 * msg_queue_new:
 * @size              : maximum size of message
 *
 * Creates a message queue with maximum size different messages.
 *
 * Returns: NULL if allocation error, pointer to a message queue
 * if successful. Has to be freed manually.
 **/
msg_queue_t *msg_queue_new(size_t size)
{
   msg_queue_t *queue        = (msg_queue_t*)malloc(sizeof(*queue));

   if (!queue)
      return NULL;

   if (!msg_queue_initialize_internal(queue, size))
   {
      free(queue);
      return NULL;
   }

   return queue;
}

bool msg_queue_initialize(msg_queue_t *queue, size_t size)
{
   if (!queue)
      return false;
   return msg_queue_initialize_internal(queue, size);
}

/**
 * msg_queue_free:
 * @queue             : pointer to queue object
 *
 * Frees message queue..
 **/
void msg_queue_free(msg_queue_t *queue)
{
   if (!queue)
      return;
   msg_queue_clear(queue);
   free(queue->elems);
   free(queue);
}

bool msg_queue_deinitialize(msg_queue_t *queue)
{
   if (!queue)
      return false;
   msg_queue_clear(queue);
   free(queue->elems);
   queue->elems   = NULL;
   queue->tmp_msg = NULL;
   queue->ptr     = 0;
   queue->size    = 0;
   return true;
}

/**
 * msg_queue_push:
 * @queue             : pointer to queue object
 * @msg               : message to add to the queue
 * @prio              : priority level of the message
 * @duration          : how many times the message can be pulled
 *                      before it vanishes (E.g. show a message for
 *                      3 seconds @ 60fps = 180 duration).
 *
 * Push a new message onto the queue.
 **/
void msg_queue_push(msg_queue_t *queue, const char *msg,
      unsigned prio, unsigned duration,
      char *title,
      enum message_queue_icon icon, enum message_queue_category category)
{
   size_t tmp_ptr = 0;
   struct queue_elem *new_elem = NULL;

   if (!queue || queue->ptr >= queue->size)
      return;

   new_elem                      = (struct queue_elem*)malloc(
      sizeof(struct queue_elem));
   if (!new_elem)
      return;

   new_elem->duration            = duration;
   new_elem->prio                = prio;
   new_elem->msg                 = msg   ? strdup(msg)   : NULL;
   new_elem->title               = title ? strdup(title) : NULL;
   new_elem->icon                = icon;
   new_elem->category            = category;

   queue->elems[queue->ptr]      = new_elem;

   tmp_ptr                       = queue->ptr++;

   while (tmp_ptr > 1)
   {
      struct queue_elem *parent  = queue->elems[tmp_ptr >> 1];
      struct queue_elem *child   = queue->elems[tmp_ptr];

      if (child->prio <= parent->prio)
         break;

      queue->elems[tmp_ptr >> 1] = child;
      queue->elems[tmp_ptr]      = parent;

      tmp_ptr >>= 1;
   }
}

/**
 * msg_queue_clear:
 * @queue             : pointer to queue object
 *
 * Clears out everything in the queue.
 **/
void msg_queue_clear(msg_queue_t *queue)
{
   size_t i;

   if (!queue)
      return;

   for (i = 1; i < queue->ptr; i++)
   {
      if (queue->elems[i])
      {
         free(queue->elems[i]->msg);
         free(queue->elems[i]->title);
         free(queue->elems[i]);
         queue->elems[i] = NULL;
      }
   }
   queue->ptr = 1;
   free(queue->tmp_msg);
   queue->tmp_msg = NULL;
}

/**
 * msg_queue_pull:
 * @queue             : pointer to queue object
 *
 * Pulls highest priority message in queue.
 *
 * Returns: NULL if no message in queue, otherwise a string
 * containing the message.
 **/
const char *msg_queue_pull(msg_queue_t *queue)
{
   struct queue_elem *front  = NULL, *last = NULL;
   size_t tmp_ptr = 1;

   (void)tmp_ptr;

   /* Nothing in queue. */
   if (!queue || queue->ptr == 1)
      return NULL;

   front = (struct queue_elem*)queue->elems[1];
   front->duration--;
   if (front->duration > 0)
      return front->msg;

   free(queue->tmp_msg);
   queue->tmp_msg = front->msg;
   front->msg = NULL;

   last  = (struct queue_elem*)queue->elems[--queue->ptr];
   queue->elems[1] = last;
   free(front->title);
   free(front);

   for (;;)
   {
      struct queue_elem *parent = NULL;
      struct queue_elem *child  = NULL;
      size_t switch_index       = tmp_ptr;
      bool left                 = (tmp_ptr * 2 <= queue->ptr)
         && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
      bool right                = (tmp_ptr * 2 + 1 <= queue->ptr)
         && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);

      if (!left && !right)
         break;

      if (left && !right)
         switch_index <<= 1;
      else if (right && !left)
         switch_index += switch_index + 1;
      else
      {
         if (queue->elems[tmp_ptr * 2]
               >= queue->elems[tmp_ptr * 2 + 1])
            switch_index <<= 1;
         else
            switch_index += switch_index + 1;
      }

      parent = (struct queue_elem*)queue->elems[tmp_ptr];
      child  = (struct queue_elem*)queue->elems[switch_index];
      queue->elems[tmp_ptr]      = child;
      queue->elems[switch_index] = parent;
      tmp_ptr                    = switch_index;
   }

   return queue->tmp_msg;
}

/**
 * msg_queue_extract:
 * @queue             : pointer to queue object
 * @queue_entry       : pointer to external queue entry struct
 *
 * Removes highest priority message from queue, copying
 * contents into queue_entry struct.
 *
 * Returns: false if no messages in queue, otherwise true
 **/
bool msg_queue_extract(msg_queue_t *queue, msg_queue_entry_t *queue_entry)
{
   struct queue_elem *front  = NULL, *last = NULL;
   size_t tmp_ptr = 1;

   /* Ensure arguments are valid and queue is not
    * empty */
   if (!queue || queue->ptr == 1 || !queue_entry)
      return false;

   front = (struct queue_elem*)queue->elems[1];
   last  = (struct queue_elem*)queue->elems[--queue->ptr];
   queue->elems[1] = last;

   /* Copy element parameters */
   queue_entry->duration = front->duration;
   queue_entry->prio     = front->prio;
   queue_entry->icon     = front->icon;
   queue_entry->category = front->category;
   queue_entry->msg[0]   = '\0';
   queue_entry->title[0] = '\0';

   if (front->msg)
      strlcpy(queue_entry->msg, front->msg, sizeof(queue_entry->msg));

   if (front->title)
      strlcpy(queue_entry->title, front->title, sizeof(queue_entry->title));

   /* Delete element */
   free(front->msg);
   free(front->title);
   free(front);

   for (;;)
   {
      struct queue_elem *parent = NULL;
      struct queue_elem *child  = NULL;
      size_t switch_index       = tmp_ptr;
      bool left                 = (tmp_ptr * 2 <= queue->ptr)
         && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
      bool right                = (tmp_ptr * 2 + 1 <= queue->ptr)
         && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);

      if (!left && !right)
         break;

      if (left && !right)
         switch_index <<= 1;
      else if (right && !left)
         switch_index += switch_index + 1;
      else
      {
         if (queue->elems[tmp_ptr * 2]
               >= queue->elems[tmp_ptr * 2 + 1])
            switch_index <<= 1;
         else
            switch_index += switch_index + 1;
      }

      parent = (struct queue_elem*)queue->elems[tmp_ptr];
      child  = (struct queue_elem*)queue->elems[switch_index];
      queue->elems[tmp_ptr]      = child;
      queue->elems[switch_index] = parent;
      tmp_ptr                    = switch_index;
   }

   return true;
}

/**
 * msg_queue_size:
 * @queue             : pointer to queue object
 *
 * Fetches number of messages in queue.
 *
 * Returns: Number of messages in queue.
 **/
size_t msg_queue_size(msg_queue_t *queue)
{
   if (!queue || queue->ptr <= 1)
      return 0;

   return queue->ptr - 1;
}
Commit	Line	Data
3719602c PC	1	/* Copyright (C) 2010-2020 The RetroArch team
	2	*
	3	* ---------------------------------------------------------------------------------------
	4	* The following license statement only applies to this file (message_queue.c).
	5	* ---------------------------------------------------------------------------------------
	6	*
	7	* Permission is hereby granted, free of charge,
	8	* to any person obtaining a copy of this software and associated documentation files (the "Software"),
	9	* to deal in the Software without restriction, including without limitation the rights to
	10	* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
	11	* and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
	12	*
	13	* The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
	14	*
	15	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
	16	* INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	17	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
	18	* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
	19	* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	20	* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	21	*/
	22
	23	#include <stdlib.h>
	24	#include <string.h>
	25
	26	#include <boolean.h>
	27	#include <queues/message_queue.h>
	28	#include <compat/strl.h>
	29	#include <compat/posix_string.h>
	30
	31	static bool msg_queue_initialize_internal(msg_queue_t *queue, size_t size)
	32	{
	33	struct queue_elem elems = (struct queue_elem)calloc(size + 1,
	34	sizeof(struct queue_elem*));
	35
	36	if (!elems)
	37	return false;
	38
	39	queue->tmp_msg = NULL;
	40	queue->elems = elems;
	41	queue->ptr = 1;
	42	queue->size = size + 1;
	43
	44	return true;
	45	}
	46
	47	/**
	48	* msg_queue_new:
	49	* @size : maximum size of message
	50	*
	51	* Creates a message queue with maximum size different messages.
	52	*
	53	* Returns: NULL if allocation error, pointer to a message queue
	54	* if successful. Has to be freed manually.
	55	**/
	56	msg_queue_t *msg_queue_new(size_t size)
	57	{
	58	msg_queue_t queue = (msg_queue_t)malloc(sizeof(*queue));
	59
	60	if (!queue)
	61	return NULL;
	62
	63	if (!msg_queue_initialize_internal(queue, size))
	64	{
65	free(queue);
66	return NULL;
67	}
68
69	return queue;
70	}
71
72	bool msg_queue_initialize(msg_queue_t *queue, size_t size)
73	{
74	if (!queue)
75	return false;
76	return msg_queue_initialize_internal(queue, size);
77	}
78
79	/**
80	* msg_queue_free:
81	* @queue : pointer to queue object
82	*
83	* Frees message queue..
84	**/
85	void msg_queue_free(msg_queue_t *queue)
86	{
87	if (!queue)
88	return;
89	msg_queue_clear(queue);
90	free(queue->elems);
91	free(queue);
92	}
93
94	bool msg_queue_deinitialize(msg_queue_t *queue)
95	{
96	if (!queue)
97	return false;
98	msg_queue_clear(queue);
99	free(queue->elems);
100	queue->elems = NULL;
101	queue->tmp_msg = NULL;
102	queue->ptr = 0;
103	queue->size = 0;
104	return true;
105	}
106
107	/**
108	* msg_queue_push:
109	* @queue : pointer to queue object
110	* @msg : message to add to the queue
111	* @prio : priority level of the message
112	* @duration : how many times the message can be pulled
113	* before it vanishes (E.g. show a message for
114	* 3 seconds @ 60fps = 180 duration).
115	*
116	* Push a new message onto the queue.
117	**/
118	void msg_queue_push(msg_queue_t queue, const char msg,
119	unsigned prio, unsigned duration,
120	char *title,
121	enum message_queue_icon icon, enum message_queue_category category)
122	{
123	size_t tmp_ptr = 0;
124	struct queue_elem *new_elem = NULL;
125
126	if (!queue \|\| queue->ptr >= queue->size)
127	return;
128
129	new_elem = (struct queue_elem*)malloc(
130	sizeof(struct queue_elem));
131	if (!new_elem)
132	return;
133
134	new_elem->duration = duration;
135	new_elem->prio = prio;
136	new_elem->msg = msg ? strdup(msg) : NULL;
137	new_elem->title = title ? strdup(title) : NULL;
138	new_elem->icon = icon;
139	new_elem->category = category;
140
141	queue->elems[queue->ptr] = new_elem;
142
143	tmp_ptr = queue->ptr++;
144
145	while (tmp_ptr > 1)
146	{
147	struct queue_elem *parent = queue->elems[tmp_ptr >> 1];
148	struct queue_elem *child = queue->elems[tmp_ptr];
149
150	if (child->prio <= parent->prio)
151	break;
152
153	queue->elems[tmp_ptr >> 1] = child;
154	queue->elems[tmp_ptr] = parent;
155
156	tmp_ptr >>= 1;
157	}
158	}
159
160	/**
161	* msg_queue_clear:
162	* @queue : pointer to queue object
163	*
164	* Clears out everything in the queue.
165	**/
166	void msg_queue_clear(msg_queue_t *queue)
167	{
168	size_t i;
169
170	if (!queue)
171	return;
172
173	for (i = 1; i < queue->ptr; i++)
174	{
175	if (queue->elems[i])
176	{
177	free(queue->elems[i]->msg);
178	free(queue->elems[i]->title);
179	free(queue->elems[i]);
180	queue->elems[i] = NULL;
181	}
182	}
183	queue->ptr = 1;
184	free(queue->tmp_msg);
185	queue->tmp_msg = NULL;
186	}
187
188	/**
189	* msg_queue_pull:
190	* @queue : pointer to queue object
191	*
192	* Pulls highest priority message in queue.
193	*
194	* Returns: NULL if no message in queue, otherwise a string
195	* containing the message.
196	**/
197	const char msg_queue_pull(msg_queue_t queue)
198	{
199	struct queue_elem front = NULL, last = NULL;
200	size_t tmp_ptr = 1;
201
202	(void)tmp_ptr;
203
204	/* Nothing in queue. */
205	if (!queue \|\| queue->ptr == 1)
206	return NULL;
207
208	front = (struct queue_elem*)queue->elems[1];
209	front->duration--;
210	if (front->duration > 0)
211	return front->msg;
212
213	free(queue->tmp_msg);
214	queue->tmp_msg = front->msg;
215	front->msg = NULL;
216
217	last = (struct queue_elem*)queue->elems[--queue->ptr];
218	queue->elems[1] = last;
219	free(front->title);
220	free(front);
221
222	for (;;)
223	{
224	struct queue_elem *parent = NULL;
225	struct queue_elem *child = NULL;
226	size_t switch_index = tmp_ptr;
227	bool left = (tmp_ptr * 2 <= queue->ptr)
228	&& (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
229	bool right = (tmp_ptr * 2 + 1 <= queue->ptr)
230	&& (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);
231
232	if (!left && !right)
233	break;
234
235	if (left && !right)
236	switch_index <<= 1;
237	else if (right && !left)
238	switch_index += switch_index + 1;
239	else
240	{
241	if (queue->elems[tmp_ptr * 2]
242	>= queue->elems[tmp_ptr * 2 + 1])
243	switch_index <<= 1;
244	else
245	switch_index += switch_index + 1;
246	}
247
248	parent = (struct queue_elem*)queue->elems[tmp_ptr];
249	child = (struct queue_elem*)queue->elems[switch_index];
250	queue->elems[tmp_ptr] = child;
251	queue->elems[switch_index] = parent;
252	tmp_ptr = switch_index;
253	}
254
255	return queue->tmp_msg;
256	}
257
258	/**
259	* msg_queue_extract:
260	* @queue : pointer to queue object
261	* @queue_entry : pointer to external queue entry struct
262	*
263	* Removes highest priority message from queue, copying
264	* contents into queue_entry struct.
265	*
266	* Returns: false if no messages in queue, otherwise true
267	**/
268	bool msg_queue_extract(msg_queue_t queue, msg_queue_entry_t queue_entry)
269	{
270	struct queue_elem front = NULL, last = NULL;
271	size_t tmp_ptr = 1;
272
273	/* Ensure arguments are valid and queue is not
274	* empty */
275	if (!queue \|\| queue->ptr == 1 \|\| !queue_entry)
276	return false;
277
278	front = (struct queue_elem*)queue->elems[1];
279	last = (struct queue_elem*)queue->elems[--queue->ptr];
280	queue->elems[1] = last;
281
282	/* Copy element parameters */
283	queue_entry->duration = front->duration;
284	queue_entry->prio = front->prio;
285	queue_entry->icon = front->icon;
286	queue_entry->category = front->category;
287	queue_entry->msg[0] = '\0';
288	queue_entry->title[0] = '\0';
289
290	if (front->msg)
291	strlcpy(queue_entry->msg, front->msg, sizeof(queue_entry->msg));
292
293	if (front->title)
294	strlcpy(queue_entry->title, front->title, sizeof(queue_entry->title));
295
296	/* Delete element */
297	free(front->msg);
298	free(front->title);
299	free(front);
300
301	for (;;)
302	{
303	struct queue_elem *parent = NULL;
304	struct queue_elem *child = NULL;
305	size_t switch_index = tmp_ptr;
306	bool left = (tmp_ptr * 2 <= queue->ptr)
307	&& (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
308	bool right = (tmp_ptr * 2 + 1 <= queue->ptr)
309	&& (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);
310
311	if (!left && !right)
312	break;
313
314	if (left && !right)
315	switch_index <<= 1;
316	else if (right && !left)
317	switch_index += switch_index + 1;
318	else
319	{
320	if (queue->elems[tmp_ptr * 2]
321	>= queue->elems[tmp_ptr * 2 + 1])
322	switch_index <<= 1;
323	else
324	switch_index += switch_index + 1;
325	}
326
327	parent = (struct queue_elem*)queue->elems[tmp_ptr];
328	child = (struct queue_elem*)queue->elems[switch_index];
329	queue->elems[tmp_ptr] = child;
330	queue->elems[switch_index] = parent;
331	tmp_ptr = switch_index;
332	}
333
334	return true;
335	}
336
337	/**
338	* msg_queue_size:
339	* @queue : pointer to queue object
340	*
341	* Fetches number of messages in queue.
342	*
343	* Returns: Number of messages in queue.
344	**/
345	size_t msg_queue_size(msg_queue_t *queue)
346	{
347	if (!queue \|\| queue->ptr <= 1)
348	return 0;
349
350	return queue->ptr - 1;
351	}