1/*
2 * Copyright (c) 2002, 2003 Marcus Overhagen <Marcus@Overhagen.de>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files or portions
6 * thereof (the "Software"), to deal in the Software without restriction,
7 * including without limitation the rights to use, copy, modify, merge,
8 * publish, distribute, sublicense, and/or sell copies of the Software,
9 * and to permit persons to whom the Software is furnished to do so, subject
10 * to the following conditions:
11 *
12 *  * Redistributions of source code must retain the above copyright notice,
13 *    this list of conditions and the following disclaimer.
14 *
15 *  * Redistributions in binary form must reproduce the above copyright notice
16 *    in the  binary, as well as this list of conditions and the following
17 *    disclaimer in the documentation and/or other materials provided with
18 *    the distribution.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
26 * THE SOFTWARE.
27 *
28 */
29
30/* Implements _event_queue_imp used by BTimedEventQueue, not thread save!
31 */
32#include <string.h>
33
34#include <Autolock.h>
35#include <Buffer.h>
36#include <InterfaceDefs.h> //defines B_DELETE
37#include <TimedEventQueue.h>
38#include <TimeSource.h>
39
40#include "TimedEventQueuePrivate.h"
41
42#include "Debug.h"
43#include "MediaDebug.h"
44
45_event_queue_imp::_event_queue_imp() :
46	fLock(new BLocker("BTimedEventQueue locker")),
47	fEventCount(0),
48	fFirstEntry(NULL),
49	fLastEntry(NULL),
50	fCleanupHookContext(NULL),
51	fCleanupHook(0)
52{
53}
54
55
56_event_queue_imp::~_event_queue_imp()
57{
58	event_queue_entry *entry;
59	entry = fFirstEntry;
60	while (entry) {
61		event_queue_entry *deleteme;
62		deleteme = entry;
63		entry = entry->next;
64		delete deleteme;
65	}
66	delete fLock;
67}
68
69
70status_t
71_event_queue_imp::AddEvent(const media_timed_event &event)
72{
73	BAutolock lock(fLock);
74
75//	printf("        adding      %12Ld  at %12Ld\n", event.event_time, system_time());
76
77	if (event.type <= 0) {
78		 return B_BAD_VALUE;
79	}
80
81	//create a new queue
82	if (fFirstEntry == NULL) {
83		ASSERT(fEventCount == 0);
84		ASSERT(fLastEntry == NULL);
85		fFirstEntry = fLastEntry = new event_queue_entry;
86		fFirstEntry->event = event;
87		fFirstEntry->prev = NULL;
88		fFirstEntry->next = NULL;
89		fEventCount++;
90		return B_OK;
91	}
92
93	//insert at queue begin
94	if (fFirstEntry->event.event_time >= event.event_time) {
95		event_queue_entry *newentry = new event_queue_entry;
96		newentry->event = event;
97		newentry->prev = NULL;
98		newentry->next = fFirstEntry;
99		fFirstEntry->prev = newentry;
100		fFirstEntry = newentry;
101		fEventCount++;
102		return B_OK;
103	}
104
105	//insert at queue end
106	if (fLastEntry->event.event_time <= event.event_time) {
107		event_queue_entry *newentry = new event_queue_entry;
108		newentry->event = event;
109		newentry->prev = fLastEntry;
110		newentry->next = NULL;
111		fLastEntry->next = newentry;
112		fLastEntry = newentry;
113		fEventCount++;
114		return B_OK;
115	}
116
117	//insert into the queue
118	for (event_queue_entry *entry = fLastEntry; entry; entry = entry->prev) {
119		if (entry->event.event_time <= event.event_time) {
120			//insert after entry
121			event_queue_entry *newentry = new event_queue_entry;
122			newentry->event = event;
123			newentry->prev = entry;
124			newentry->next = entry->next;
125			(entry->next)->prev = newentry;
126			entry->next = newentry;
127			fEventCount++;
128			return B_OK;
129		}
130	}
131
132	debugger("_event_queue_imp::AddEvent failed, should not be here\n");
133	return B_OK;
134}
135
136
137status_t
138_event_queue_imp::RemoveEvent(const media_timed_event *event)
139{
140	BAutolock lock(fLock);
141
142	for (event_queue_entry *entry = fFirstEntry; entry; entry = entry->next) {
143		if (entry->event == *event) {
144			// No cleanup here
145			RemoveEntry(entry);
146			return B_OK;
147		}
148	}
149
150	return B_ERROR;
151}
152
153
154status_t
155_event_queue_imp::RemoveFirstEvent(media_timed_event * outEvent)
156{
157	BAutolock lock(fLock);
158
159	if (fFirstEntry == 0)
160		return B_ERROR;
161
162	if (outEvent != 0) {
163		// No cleanup here
164		*outEvent = fFirstEntry->event;
165	} else {
166		CleanupEvent(&fFirstEntry->event);
167	}
168
169	RemoveEntry(fFirstEntry);
170
171	return B_OK;
172}
173
174
175bool
176_event_queue_imp::HasEvents() const
177{
178	return fEventCount != 0;
179}
180
181
182int32
183_event_queue_imp::EventCount() const
184{
185	#if DEBUG > 1
186		Dump();
187	#endif
188	return fEventCount;
189}
190
191
192const media_timed_event *
193_event_queue_imp::FirstEvent() const
194{
195	return fFirstEntry ? &fFirstEntry->event : NULL;
196}
197
198
199bigtime_t
200_event_queue_imp::FirstEventTime() const
201{
202	return fFirstEntry ? fFirstEntry->event.event_time : B_INFINITE_TIMEOUT;
203}
204
205
206const media_timed_event *
207_event_queue_imp::LastEvent() const
208{
209	return fLastEntry ? &fLastEntry->event : NULL;
210}
211
212
213bigtime_t
214_event_queue_imp::LastEventTime() const
215{
216	return fLastEntry ? fLastEntry->event.event_time : B_INFINITE_TIMEOUT;
217}
218
219
220const media_timed_event *
221_event_queue_imp::FindFirstMatch(bigtime_t eventTime,
222								 BTimedEventQueue::time_direction direction,
223								 bool inclusive,
224								 int32 eventType)
225{
226	event_queue_entry *end;
227	event_queue_entry *entry;
228
229	BAutolock lock(fLock);
230
231	switch (direction) {
232		case BTimedEventQueue::B_ALWAYS:
233			for (entry = fFirstEntry; entry; entry = entry->next) {
234				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type)
235					return &entry->event;
236			}
237			return NULL;
238
239		case BTimedEventQueue::B_BEFORE_TIME:
240			end = GetEnd_BeforeTime(eventTime, inclusive);
241			if (end == NULL)
242				return NULL;
243			end = end->next;
244			for (entry = fFirstEntry; entry != end; entry = entry->next) {
245				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
246					return &entry->event;
247				}
248			}
249			return NULL;
250
251		case BTimedEventQueue::B_AT_TIME:
252			{
253				bool found_time = false;
254				for (entry = fFirstEntry; entry; entry = entry->next) {
255					if (eventTime == entry->event.event_time) {
256						found_time = true;
257						if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type)
258							return &entry->event;
259					} else if (found_time)
260						return NULL;
261				}
262				return NULL;
263			}
264
265		case BTimedEventQueue::B_AFTER_TIME:
266			for (entry = GetStart_AfterTime(eventTime, inclusive); entry; entry = entry->next) {
267				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
268					return &entry->event;
269				}
270			}
271			return NULL;
272	}
273
274	return NULL;
275}
276
277
278status_t
279_event_queue_imp::DoForEach(BTimedEventQueue::for_each_hook hook,
280							void *context,
281							bigtime_t eventTime,
282							BTimedEventQueue::time_direction direction,
283							bool inclusive,
284							int32 eventType)
285{
286	event_queue_entry *end;
287	event_queue_entry *entry;
288	event_queue_entry *remove;
289	BTimedEventQueue::queue_action action;
290
291	BAutolock lock(fLock);
292
293	switch (direction) {
294		case BTimedEventQueue::B_ALWAYS:
295			for (entry = fFirstEntry; entry; ) {
296				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
297					action = (*hook)(&entry->event, context);
298					switch (action) {
299						case BTimedEventQueue::B_DONE:
300							return B_OK;
301						case BTimedEventQueue::B_REMOVE_EVENT:
302							CleanupEvent(&entry->event);
303							remove = entry;
304							entry = entry->next;
305							RemoveEntry(remove);
306							break;
307						case BTimedEventQueue::B_NO_ACTION:
308						case BTimedEventQueue::B_RESORT_QUEUE:
309						default:
310							entry = entry->next;
311							break;
312					}
313				} else {
314					entry = entry->next;
315				}
316			}
317			return B_OK;
318
319		case BTimedEventQueue::B_BEFORE_TIME:
320			end = GetEnd_BeforeTime(eventTime, inclusive);
321			if (end == NULL)
322				return B_OK;
323			end = end->next;
324			for (entry = fFirstEntry; entry != end; ) {
325				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
326					action = (*hook)(&entry->event, context);
327					switch (action) {
328						case BTimedEventQueue::B_DONE:
329							return B_OK;
330						case BTimedEventQueue::B_REMOVE_EVENT:
331							CleanupEvent(&entry->event);
332							remove = entry;
333							entry = entry->next;
334							RemoveEntry(remove);
335							break;
336						case BTimedEventQueue::B_NO_ACTION:
337						case BTimedEventQueue::B_RESORT_QUEUE:
338						default:
339							entry = entry->next;
340							break;
341					}
342				} else {
343					entry = entry->next;
344				}
345			}
346			return B_OK;
347
348		case BTimedEventQueue::B_AT_TIME:
349			{
350				bool found_time = false;
351				for (entry = fFirstEntry; entry; ) {
352					if (eventTime == entry->event.event_time) {
353						found_time = true;
354						if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
355							action = (*hook)(&entry->event, context);
356							switch (action) {
357								case BTimedEventQueue::B_DONE:
358									return B_OK;
359								case BTimedEventQueue::B_REMOVE_EVENT:
360									CleanupEvent(&entry->event);
361									remove = entry;
362									entry = entry->next;
363									RemoveEntry(remove);
364									break;
365								case BTimedEventQueue::B_NO_ACTION:
366								case BTimedEventQueue::B_RESORT_QUEUE:
367								default:
368									entry = entry->next;
369									break;
370							}
371						} else {
372							entry = entry->next;
373						}
374					} else if (found_time) {
375						break;
376					} else {
377						entry = entry->next;
378					}
379				}
380				return B_OK;
381			}
382
383		case BTimedEventQueue::B_AFTER_TIME:
384			for (entry = GetStart_AfterTime(eventTime, inclusive); entry; ) {
385				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
386					action = (*hook)(&entry->event, context);
387					switch (action) {
388						case BTimedEventQueue::B_DONE:
389							return B_OK;
390						case BTimedEventQueue::B_REMOVE_EVENT:
391							CleanupEvent(&entry->event);
392							remove = entry;
393							entry = entry->next;
394							RemoveEntry(remove);
395							break;
396						case BTimedEventQueue::B_NO_ACTION:
397						case BTimedEventQueue::B_RESORT_QUEUE:
398						default:
399							entry = entry->next;
400							break;
401					}
402				} else {
403					entry = entry->next;
404				}
405			}
406			return B_OK;
407	}
408
409	return B_ERROR;
410}
411
412
413status_t
414_event_queue_imp::FlushEvents(bigtime_t eventTime,
415							  BTimedEventQueue::time_direction direction,
416							  bool inclusive,
417							  int32 eventType)
418{
419	event_queue_entry *end;
420	event_queue_entry *entry;
421	event_queue_entry *remove;
422
423	BAutolock lock(fLock);
424
425	switch (direction) {
426		case BTimedEventQueue::B_ALWAYS:
427			for (entry = fFirstEntry; entry; ) {
428				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
429					CleanupEvent(&entry->event);
430					remove = entry;
431					entry = entry->next;
432					RemoveEntry(remove);
433				} else {
434					entry = entry->next;
435				}
436			}
437			return B_OK;
438
439		case BTimedEventQueue::B_BEFORE_TIME:
440			end = GetEnd_BeforeTime(eventTime, inclusive);
441			if (end == NULL)
442				return B_OK;
443			end = end->next;
444			for (entry = fFirstEntry; entry != end; ) {
445				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
446					CleanupEvent(&entry->event);
447					remove = entry;
448					entry = entry->next;
449					RemoveEntry(remove);
450				} else {
451					entry = entry->next;
452				}
453			}
454			return B_OK;
455
456		case BTimedEventQueue::B_AT_TIME:
457			{
458				bool found_time = false;
459				for (entry = fFirstEntry; entry; ) {
460					if (eventTime == entry->event.event_time) {
461						found_time = true;
462						if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
463							CleanupEvent(&entry->event);
464							remove = entry;
465							entry = entry->next;
466							RemoveEntry(remove);
467						} else {
468							entry = entry->next;
469						}
470					} else if (found_time) {
471						break;
472					} else {
473						entry = entry->next;
474					}
475				}
476				return B_OK;
477			}
478
479		case BTimedEventQueue::B_AFTER_TIME:
480			for (entry = GetStart_AfterTime(eventTime, inclusive); entry; ) {
481				if (eventType == BTimedEventQueue::B_ANY_EVENT || eventType == entry->event.type) {
482					CleanupEvent(&entry->event);
483					remove = entry;
484					entry = entry->next;
485					RemoveEntry(remove);
486				} else {
487					entry = entry->next;
488				}
489			}
490			return B_OK;
491	}
492
493	return B_ERROR;
494}
495
496
497void
498_event_queue_imp::SetCleanupHook(BTimedEventQueue::cleanup_hook hook, void *context)
499{
500	BAutolock lock(fLock);
501	fCleanupHookContext = context;
502	fCleanupHook = hook;
503}
504
505
506void
507_event_queue_imp::RemoveEntry(event_queue_entry *entry)
508{
509	//remove the entry from double-linked list
510	//and delete it
511	if (entry->prev != NULL)
512		(entry->prev)->next = entry->next;
513	if (entry->next != NULL)
514		(entry->next)->prev = entry->prev;
515	if (entry == fFirstEntry) {
516		fFirstEntry = entry->next;
517		if (fFirstEntry != NULL)
518			fFirstEntry->prev = NULL;
519	}
520	if (entry == fLastEntry) {
521		fLastEntry = entry->prev;
522		if (fLastEntry != NULL)
523			fLastEntry->next = NULL;
524	}
525	delete entry;
526	fEventCount--;
527	ASSERT(fEventCount >= 0);
528	ASSERT(fEventCount != 0 || ((fFirstEntry == NULL) && (fLastEntry == NULL)));
529}
530
531
532void
533_event_queue_imp::CleanupEvent(media_timed_event *event)
534{
535	//perform the cleanup action required
536	//when deleting an event from the queue
537
538	//BeBook says:
539	//	Each event has a cleanup flag associated with it that indicates
540	//  what sort of special action needs to be performed when the event is
541	//  removed from the queue. If this value is B_NO_CLEANUP, nothing is done.
542	//  If it's B_RECYCLE, and the event is a B_HANDLE_BUFFER event, BTimedEventQueue
543	//  will automatically recycle the buffer associated with the event.
544	//  If the cleanup flag is B_DELETE or is B_USER_CLEANUP or greater,
545	//  the cleanup hook function will be called.
546	//and:
547	//  cleanup hook function specified by hook to be called for events
548	//  as they're removed from the queue. The hook will be called only
549	//  for events with cleanup_flag values of B_DELETE or B_USER_CLEANUP or greater.
550	//and:
551	//  These values define how BTimedEventQueue should handle removing
552	//  events from the queue. If the flag is B_USER_CLEANUP or greater,
553	//  the cleanup hook function is called when the event is removed.
554	//Problems:
555	//  B_DELETE is a keyboard code! (seems to have existed in early
556	//  sample code as a cleanup flag)
557	//
558	//  exiting cleanup flags are:
559	//		B_NO_CLEANUP = 0,
560	//		B_RECYCLE_BUFFER,		// recycle buffers handled by BTimedEventQueue
561	//		B_EXPIRE_TIMER,			// call TimerExpired() on the event->data
562	//		B_USER_CLEANUP = 0x4000	// others go to the cleanup func
563	//
564
565	if (event->cleanup == BTimedEventQueue::B_NO_CLEANUP) {
566		// do nothing
567	} else if (event->type == BTimedEventQueue::B_HANDLE_BUFFER
568			&& event->cleanup == BTimedEventQueue::B_RECYCLE_BUFFER) {
569		((BBuffer *)event->pointer)->Recycle();
570		DEBUG_ONLY(*const_cast<void **>(&event->pointer) = NULL);
571	} else if (event->cleanup == BTimedEventQueue::B_EXPIRE_TIMER) {
572		// do nothing, called in BMediaEventLooper::DispatchEvent
573	} else if (event->cleanup == B_DELETE
574			|| event->cleanup >= BTimedEventQueue::B_USER_CLEANUP) {
575		if (fCleanupHook)
576			(*fCleanupHook)(event,fCleanupHookContext);
577	} else {
578		ERROR("BTimedEventQueue cleanup unhandled! type = %" B_PRId32
579			", cleanup = %" B_PRId32 "\n", event->type, event->cleanup);
580	}
581}
582
583
584_event_queue_imp::event_queue_entry *
585_event_queue_imp::GetEnd_BeforeTime(bigtime_t eventTime, bool inclusive)
586{
587	event_queue_entry *entry;
588
589	entry = fLastEntry;
590	while (entry) {
591		if ((entry->event.event_time > eventTime) || (!inclusive && entry->event.event_time == eventTime))
592			entry = entry->prev;
593		else
594			break;
595	}
596	return entry;
597}
598
599
600_event_queue_imp::event_queue_entry *
601_event_queue_imp::GetStart_AfterTime(bigtime_t eventTime, bool inclusive)
602{
603	event_queue_entry *entry;
604
605	entry = fFirstEntry;
606	while (entry) {
607		if ((entry->event.event_time < eventTime) || (!inclusive && entry->event.event_time == eventTime))
608			entry = entry->next;
609		else
610			break;
611	}
612	return entry;
613}
614
615
616#if DEBUG > 1
617void
618_event_queue_imp::Dump() const
619{
620	TRACE("fEventCount = %" B_PRId32 "\n", fEventCount);
621	TRACE("fFirstEntry = 0x%p\n", (void*)fFirstEntry);
622	TRACE("fLastEntry  = 0x%p\n", (void*)fLastEntry);
623	for (event_queue_entry *entry = fFirstEntry; entry; entry = entry->next) {
624		TRACE("entry = 0x%p\n", (void*)entry);
625		TRACE("  entry.prev = 0x%p\n", (void*)entry->prev);
626		TRACE("  entry.next = 0x%p\n", (void*)entry->next);
627		TRACE("  entry.event.event_time = %" B_PRId64 "\n",
628			entry->event.event_time);
629	}
630}
631#endif
632