No issues found
1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*-
2 *
3 * Copyright (C) 2003 Jeffrey Yasskin <jyasskin@mail.utexas.edu>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * The Rhythmbox authors hereby grant permission for non-GPL compatible
11 * GStreamer plugins to be used and distributed together with GStreamer
12 * and Rhythmbox. This permission is above and beyond the permissions granted
13 * by the GPL license by which Rhythmbox is covered. If you modify this code
14 * you may extend this exception to your version of the code, but you are not
15 * obligated to do so. If you do not wish to do so, delete this exception
16 * statement from your version.
17 *
18 * This program is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License
24 * along with this program; if not, write to the Free Software
25 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
26 *
27 */
28
29 #include "config.h"
30
31 #include <string.h>
32
33 #include "rb-history.h"
34
35 #include "rhythmdb.h"
36
37 /**
38 * SECTION:rb-history
39 * @short_description: sequence data structure useful for implementing play orders
40 *
41 * RBHistory is a GSequence that maintains a "current" pointer and can delete
42 * an arbitrary element in amortized O(log(N)) time. It can call a deletion
43 * callback when it removes one of its entries.
44 *
45 * All operations take amortized O(log(N)) (worst-case O(N)) time unless noted
46 * otherwise.
47 */
48
49 struct RBHistoryPrivate
50 {
51 GSequence *seq;
52 /* If seq is empty, current == g_sequence_get_end_ptr (seq) */
53 GSequenceIter *current;
54
55 GHashTable *entry_to_seqptr;
56
57 gboolean truncate_on_play;
58 guint maximum_size;
59
60 GFunc destroyer;
61 gpointer destroy_userdata;
62 };
63
64 #define RB_HISTORY_GET_PRIVATE(o) (G_TYPE_INSTANCE_GET_PRIVATE ((o), RB_TYPE_HISTORY, RBHistoryPrivate))
65
66 #define MAX_HISTORY_SIZE 50
67
68 static void rb_history_class_init (RBHistoryClass *klass);
69 static void rb_history_init (RBHistory *shell_player);
70 static void rb_history_finalize (GObject *object);
71
72 static void rb_history_set_property (GObject *object,
73 guint prop_id,
74 const GValue *value,
75 GParamSpec *pspec);
76 static void rb_history_get_property (GObject *object,
77 guint prop_id,
78 GValue *value,
79 GParamSpec *pspec);
80
81 static void rb_history_limit_size (RBHistory *hist, gboolean cut_from_beginning);
82
83 static void rb_history_remove_entry_internal (RBHistory *hist,
84 RhythmDBEntry *entry,
85 gboolean from_seq);
86
87 enum
88 {
89 PROP_0,
90 PROP_TRUNCATE_ON_PLAY,
91 PROP_MAX_SIZE,
92 };
93
94 G_DEFINE_TYPE (RBHistory, rb_history, G_TYPE_OBJECT)
95
96 static void
97 rb_history_class_init (RBHistoryClass *klass)
98 {
99 GObjectClass *object_class = G_OBJECT_CLASS (klass);
100
101 object_class->finalize = rb_history_finalize;
102
103 object_class->set_property = rb_history_set_property;
104 object_class->get_property = rb_history_get_property;
105
106 /**
107 * RBHistory:truncate-on-play:
108 *
109 * If set, rb_history_set_playing() truncates the rest of the history
110 */
111 g_object_class_install_property (object_class,
112 PROP_TRUNCATE_ON_PLAY,
113 g_param_spec_boolean ("truncate-on-play",
114 "Truncate on Play",
115 "Whether rb_history_set_playing() truncates the rest of the list",
116 FALSE,
117 G_PARAM_READWRITE | G_PARAM_CONSTRUCT));
118
119 /**
120 * RBHistory:maximum-size:
121 *
122 * Maximum number of entries to store in the history. If 0, no limit is applied.
123 */
124 g_object_class_install_property (object_class,
125 PROP_MAX_SIZE,
126 g_param_spec_uint ("maximum-size",
127 "Maximum Size",
128 "Maximum length of the history. Infinite if 0",
129 0, G_MAXUINT,
130 0,
131 G_PARAM_READWRITE));
132
133 g_type_class_add_private (klass, sizeof (RBHistoryPrivate));
134 }
135
136 /**
137 * rb_history_new:
138 * @truncate_on_play: Whether rb_history_set_playing() should truncate the history
139 * @destroyer: (scope async): function to call when removing an entry from the history
140 * @destroy_userdata: data to pass to @destroyer
141 *
142 * Creates a new history instance.
143 *
144 * Return value: a new #RBHistory
145 */
146 RBHistory *
147 rb_history_new (gboolean truncate_on_play, GFunc destroyer, gpointer destroy_userdata)
148 {
149 RBHistory *history;
150
151 history = g_object_new (RB_TYPE_HISTORY,
152 "truncate-on-play", truncate_on_play,
153 NULL);
154
155 g_return_val_if_fail (history->priv != NULL, NULL);
156
157 history->priv->destroyer = destroyer;
158 history->priv->destroy_userdata = destroy_userdata;
159
160 return history;
161 }
162
163 static void
164 rb_history_init (RBHistory *hist)
165 {
166 hist->priv = RB_HISTORY_GET_PRIVATE (hist);
167
168 hist->priv->entry_to_seqptr = g_hash_table_new (g_direct_hash,
169 g_direct_equal);
170 hist->priv->seq = g_sequence_new (NULL);
171 hist->priv->current = g_sequence_get_begin_iter (hist->priv->seq);
172 }
173
174 static void
175 rb_history_finalize (GObject *object)
176 {
177 RBHistory *hist;
178 g_return_if_fail (object != NULL);
179 g_return_if_fail (RB_IS_HISTORY (object));
180
181 hist = RB_HISTORY (object);
182
183 /* remove all of the stored entries */
184 rb_history_clear (hist);
185
186 g_hash_table_destroy (hist->priv->entry_to_seqptr);
187 g_sequence_free (hist->priv->seq);
188
189 G_OBJECT_CLASS (rb_history_parent_class)->finalize (object);
190 }
191
192 static void
193 rb_history_set_property (GObject *object,
194 guint prop_id,
195 const GValue *value,
196 GParamSpec *pspec)
197 {
198 RBHistory *hist = RB_HISTORY (object);
199
200 switch (prop_id)
201 {
202 case PROP_TRUNCATE_ON_PLAY: {
203 hist->priv->truncate_on_play = g_value_get_boolean (value);
204 } break;
205 case PROP_MAX_SIZE: {
206 hist->priv->maximum_size = g_value_get_uint (value);
207 rb_history_limit_size (hist, TRUE);
208 } break;
209 default:
210 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
211 break;
212 }
213 }
214
215 static void
216 rb_history_get_property (GObject *object,
217 guint prop_id,
218 GValue *value,
219 GParamSpec *pspec)
220 {
221 RBHistory *hist = RB_HISTORY (object);
222
223 switch (prop_id)
224 {
225 case PROP_TRUNCATE_ON_PLAY: {
226 g_value_set_boolean (value, hist->priv->truncate_on_play);
227 } break;
228 case PROP_MAX_SIZE: {
229 g_value_set_uint (value, hist->priv->maximum_size);
230 } break;
231 default:
232 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
233 break;
234 }
235
236 }
237
238 /**
239 * rb_history_set_destroy_notify:
240 * @hist: a #RBHistory
241 * @destroyer: (scope async): function to call when removing an entry from the history
242 * @destroy_userdata: data to pass to @destroyer
243 *
244 * Sets a new function to call when removing entries from the history.
245 */
246 void
247 rb_history_set_destroy_notify (RBHistory *hist, GFunc destroyer, gpointer destroy_userdata)
248 {
249 g_return_if_fail (RB_IS_HISTORY (hist));
250
251 hist->priv->destroyer = destroyer;
252 hist->priv->destroy_userdata = destroy_userdata;
253 }
254
255 /**
256 * rb_history_set_truncate_on_play:
257 * @hist: a #RBHistory
258 * @truncate_on_play: Whether rb_history_set_playing() should truncate the history
259 *
260 * Sets the 'truncate-on-play' property.
261 */
262 void
263 rb_history_set_truncate_on_play (RBHistory *hist, gboolean truncate_on_play)
264 {
265 g_return_if_fail (RB_IS_HISTORY (hist));
266
267 hist->priv->truncate_on_play = truncate_on_play;
268 g_object_notify (G_OBJECT (hist), "truncate-on-play");
269 }
270
271 /**
272 * rb_history_set_maximum_size:
273 * @hist: a #RBHistory
274 * @maximum_size: new maximum size of the history (or 0 for no limit)
275 *
276 * Sets the maximum-size property
277 */
278 void
279 rb_history_set_maximum_size (RBHistory *hist, guint maximum_size)
280 {
281 g_return_if_fail (RB_IS_HISTORY (hist));
282
283 hist->priv->maximum_size = maximum_size;
284 g_object_notify (G_OBJECT (hist), "maximum-size");
285 }
286
287 /**
288 * rb_history_length:
289 * @hist: a #RBHistory
290 *
291 * Returns the number of entries in the history.
292 *
293 * Return value: number of entries
294 */
295 guint
296 rb_history_length (RBHistory *hist)
297 {
298 g_return_val_if_fail (RB_IS_HISTORY (hist), 0);
299
300 return g_sequence_get_length (hist->priv->seq);
301 }
302
303 /**
304 * rb_history_first:
305 * @hist: a #RBHistory
306 *
307 * Returns the first entry in the history.
308 *
309 * Return value: (transfer none): first entry
310 */
311 RhythmDBEntry *
312 rb_history_first (RBHistory *hist)
313 {
314 GSequenceIter *begin;
315 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
316
317 begin = g_sequence_get_begin_iter (hist->priv->seq);
318 return g_sequence_iter_is_end (begin) ? NULL : g_sequence_get (begin);
319 }
320
321 /**
322 * rb_history_previous:
323 * @hist: a #RBHistory
324 *
325 * Returns the #RhythmDBEntry before the current position.
326 *
327 * Return value: (transfer none): previous entry
328 */
329 RhythmDBEntry *
330 rb_history_previous (RBHistory *hist)
331 {
332 GSequenceIter *prev;
333
334 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
335
336 prev = g_sequence_iter_prev (hist->priv->current);
337 return prev == hist->priv->current ? NULL : g_sequence_get (prev);
338 }
339
340 /**
341 * rb_history_current:
342 * @hist: a #RBHistory
343 *
344 * Returns the current #RhythmDBEntry, or NULL if there is no current position
345 *
346 * Return value: (transfer none): current entry or NULL
347 */
348 RhythmDBEntry *
349 rb_history_current (RBHistory *hist)
350 {
351 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
352
353 return g_sequence_iter_is_end (hist->priv->current) ? NULL : g_sequence_get (hist->priv->current);
354 }
355
356 /**
357 * rb_history_next:
358 * @hist: a #RBHistory
359 *
360 * Returns the #RhythmDBEntry after the current position
361 *
362 * Return value: (transfer none): next entry
363 */
364 RhythmDBEntry *
365 rb_history_next (RBHistory *hist)
366 {
367 GSequenceIter *next;
368 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
369
370 next = g_sequence_iter_next (hist->priv->current);
371 return g_sequence_iter_is_end (next) ? NULL : g_sequence_get (next);
372 }
373
374 /**
375 * rb_history_last:
376 * @hist: a #RBHistory
377 *
378 * Returns the last #RhythmDBEntry in the history
379 *
380 * Return value: (transfer none): last entry
381 */
382 RhythmDBEntry *
383 rb_history_last (RBHistory *hist)
384 {
385 GSequenceIter *last;
386
387 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
388
389 last = g_sequence_iter_prev (g_sequence_get_end_iter (hist->priv->seq));
390 return g_sequence_iter_is_end (last) ? NULL : g_sequence_get (last);
391 }
392
393 /**
394 * rb_history_go_first:
395 * @hist: a #RBHistory
396 *
397 * Moves the current position to the first entry in the history
398 */
399 void
400 rb_history_go_first (RBHistory *hist)
401 {
402 g_return_if_fail (RB_IS_HISTORY (hist));
403
404 hist->priv->current = g_sequence_get_begin_iter (hist->priv->seq);
405 }
406
407 /**
408 * rb_history_go_previous:
409 * @hist: a #RBHistory
410 *
411 * Moves the current position to the previous entry. If the current position is
412 * already at the start of the history, nothing happens.
413 */
414 void
415 rb_history_go_previous (RBHistory *hist)
416 {
417 GSequenceIter *prev;
418 g_return_if_fail (RB_IS_HISTORY (hist));
419
420 prev = g_sequence_iter_prev (hist->priv->current);
421 if (prev)
422 hist->priv->current = prev;
423 }
424
425 /**
426 * rb_history_go_next:
427 * @hist: a #RBHistory
428 *
429 * Moves the current position to the next entry. If the current position is
430 * already at the end of the history, nothing happens.
431 */
432 void
433 rb_history_go_next (RBHistory *hist)
434 {
435 g_return_if_fail (RB_IS_HISTORY (hist));
436
437 hist->priv->current = g_sequence_iter_next (hist->priv->current);
438 }
439
440 /**
441 * rb_history_go_last:
442 * @hist: a #RBHistory
443 *
444 * Moves the current position to the last entry in the history
445 */
446 void
447 rb_history_go_last (RBHistory *hist)
448 {
449 GSequenceIter *last;
450 g_return_if_fail (RB_IS_HISTORY (hist));
451
452 last = g_sequence_iter_prev (g_sequence_get_end_iter (hist->priv->seq));
453 hist->priv->current = last ? last : g_sequence_get_end_iter (hist->priv->seq);
454 }
455
456 static void
457 _history_remove_swapped (RhythmDBEntry *entry, RBHistory *hist)
458 {
459 rb_history_remove_entry_internal (hist, entry, FALSE);
460 }
461
462 /**
463 * rb_history_set_playing:
464 * @hist: a #RBHistory
465 * @entry: the new playing #RhythmDBEntry
466 *
467 * Updates the current position to point to the specified entry.
468 * If the truncate-on-play property is set, this will remove all entries
469 * after that.
470 */
471 void
472 rb_history_set_playing (RBHistory *hist, RhythmDBEntry *entry)
473 {
474 g_return_if_fail (RB_IS_HISTORY (hist));
475
476 if (entry == NULL) {
477 hist->priv->current = g_sequence_get_end_iter (hist->priv->seq);
478 return;
479 }
480
481 rb_history_remove_entry (hist, entry);
482
483 g_sequence_insert_before (g_sequence_iter_next (hist->priv->current), entry);
484 /* make hist->priv->current point to the new entry */
485 if (g_sequence_iter_is_end (hist->priv->current))
486 hist->priv->current = g_sequence_iter_prev (hist->priv->current);
487 else
488 hist->priv->current = g_sequence_iter_next (hist->priv->current);
489 g_hash_table_insert (hist->priv->entry_to_seqptr, entry, hist->priv->current);
490
491 if (hist->priv->truncate_on_play) {
492 g_sequence_foreach_range (g_sequence_iter_next (hist->priv->current),
493 g_sequence_get_end_iter (hist->priv->seq),
494 (GFunc)_history_remove_swapped, hist);
495 g_sequence_remove_range (g_sequence_iter_next (hist->priv->current),
496 g_sequence_get_end_iter (hist->priv->seq));
497 }
498
499 rb_history_limit_size (hist, TRUE);
500 }
501
502 /**
503 * rb_history_append:
504 * @hist: a #RBHistory
505 * @entry: a #RhythmDBEntry to append
506 *
507 * Adds a new entry to the end of the history list.
508 * If a size limit is set, an entry may be removed from the start to
509 * keep the history list within the limit.
510 */
511 void
512 rb_history_append (RBHistory *hist, RhythmDBEntry *entry)
513 {
514 GSequenceIter *new_node;
515 GSequenceIter *last;
516
517 g_return_if_fail (RB_IS_HISTORY (hist));
518 g_return_if_fail (entry != NULL);
519
520 if (g_sequence_iter_is_end (hist->priv->current) == FALSE &&
521 entry == g_sequence_get (hist->priv->current)) {
522 rb_history_remove_entry (hist, entry);
523 last = g_sequence_iter_prev (g_sequence_get_end_iter (hist->priv->seq));
524 hist->priv->current = last ? last : g_sequence_get_end_iter (hist->priv->seq);
525 } else {
526 rb_history_remove_entry (hist, entry);
527 }
528
529 g_sequence_append (hist->priv->seq, entry);
530 new_node = g_sequence_iter_prev (g_sequence_get_end_iter (hist->priv->seq));
531 g_hash_table_insert (hist->priv->entry_to_seqptr, entry, new_node);
532
533 rb_history_limit_size (hist, TRUE);
534 }
535
536 /**
537 * rb_history_get_current_index:
538 * @hist: a #RBHistory
539 *
540 * Gets the index of the current entry. This is guaranteed to be < the
541 * history's size, so if the history is empty, it returns -1.
542 *
543 * Return value: index of the current entry
544 */
545 gint
546 rb_history_get_current_index (RBHistory *hist)
547 {
548 g_return_val_if_fail (RB_IS_HISTORY (hist), -1);
549
550 return g_sequence_iter_get_position (hist->priv->current);
551 }
552
553 /**
554 * rb_history_insert_at_index:
555 * @hist: a #RBHistory
556 * @entry: a #RhythmDBEntry to insert
557 * @index: position at which to insert @entry
558 *
559 * Inserts @entry at @index within the history list. 0<=@index<=size
560 */
561 void
562 rb_history_insert_at_index (RBHistory *hist, RhythmDBEntry *entry, guint index)
563 {
564 GSequenceIter *old_node;
565 GSequenceIter *new_node;
566
567 g_return_if_fail (RB_IS_HISTORY (hist));
568 g_return_if_fail (entry != NULL);
569 g_return_if_fail (index <= g_sequence_get_length (hist->priv->seq));
570
571 /* Deal with case where the entry is moving forward */
572 old_node = g_hash_table_lookup (hist->priv->entry_to_seqptr, entry);
573 if (old_node && g_sequence_iter_get_position (old_node) < index)
574 index--;
575
576 rb_history_remove_entry (hist, entry);
577
578 new_node = g_sequence_get_iter_at_pos (hist->priv->seq, index);
579 g_sequence_insert_before (new_node, entry);
580 new_node = g_sequence_iter_prev (new_node);
581 g_hash_table_insert (hist->priv->entry_to_seqptr, entry, new_node);
582
583 if (g_sequence_iter_is_end (hist->priv->current) && index == g_sequence_get_length (hist->priv->seq)-1 /*length just increased*/)
584 hist->priv->current = new_node;
585
586 rb_history_limit_size (hist, TRUE);
587 }
588
589 /*
590 * Cuts nodes off of the history from the desired end until it is smaller than max_size.
591 * Never cuts off the current node.
592 */
593 static void
594 rb_history_limit_size (RBHistory *hist, gboolean cut_from_beginning)
595 {
596 if (hist->priv->maximum_size != 0) {
597 while (g_sequence_get_length (hist->priv->seq) > hist->priv->maximum_size) {
598 if (cut_from_beginning
599 || hist->priv->current == g_sequence_iter_prev (g_sequence_get_end_iter (hist->priv->seq))) {
600 rb_history_remove_entry (hist, rb_history_first (hist));
601 } else {
602 rb_history_remove_entry (hist, rb_history_last (hist));
603 }
604 }
605 }
606 }
607
608 /**
609 * rb_history_remove_entry:
610 * @hist: a #RBHistory
611 * @entry: the #RhythmDBEntry to remove
612 *
613 * Removes the specified entry from the history list.
614 */
615 void
616 rb_history_remove_entry (RBHistory *hist, RhythmDBEntry *entry)
617 {
618 rb_history_remove_entry_internal (hist, entry, TRUE);
619 }
620
621 static void
622 rb_history_remove_entry_internal (RBHistory *hist, RhythmDBEntry *entry, gboolean from_seq)
623 {
624 GSequenceIter *to_delete;
625 g_return_if_fail (RB_IS_HISTORY (hist));
626
627 to_delete = g_hash_table_lookup (hist->priv->entry_to_seqptr, entry);
628 if (to_delete) {
629 g_hash_table_remove (hist->priv->entry_to_seqptr, entry);
630 if (hist->priv->destroyer)
631 hist->priv->destroyer (entry, hist->priv->destroy_userdata);
632
633 if (to_delete == hist->priv->current) {
634 hist->priv->current = g_sequence_get_end_iter (hist->priv->seq);
635 }
636 g_assert (to_delete != hist->priv->current);
637 if (from_seq) {
638 g_sequence_remove (to_delete);
639 }
640 }
641 }
642
643 /**
644 * rb_history_clear:
645 * @hist: a #RBHistory
646 *
647 * Empties the history list.
648 */
649 void
650 rb_history_clear (RBHistory *hist)
651 {
652 g_return_if_fail (RB_IS_HISTORY (hist));
653
654 g_sequence_foreach (hist->priv->seq, (GFunc)_history_remove_swapped, hist);
655 g_sequence_remove_range (g_sequence_get_begin_iter (hist->priv->seq),
656 g_sequence_get_end_iter (hist->priv->seq));
657
658 /* When the sequence is empty, the hash table should also be empty. */
659 g_assert (g_hash_table_size (hist->priv->entry_to_seqptr) == 0);
660 }
661
662 /**
663 * rb_history_dump:
664 * @hist: a #RBHistory
665 *
666 * Constructs a copy of the whole history in order. Caller must free the result.
667 * The caller does not own any references on the entries in the returned array.
668 * Takes O(Nlog(N)) time.
669 *
670 * Return value: (element-type RB.RhythmDBEntry) (transfer container): a copy of the history list
671 */
672 GPtrArray *
673 rb_history_dump (RBHistory *hist)
674 {
675 GSequenceIter *cur;
676 GPtrArray *result;
677
678 g_return_val_if_fail (RB_IS_HISTORY (hist), NULL);
679
680 result = g_ptr_array_sized_new (g_sequence_get_length (hist->priv->seq));
681 for (cur = g_sequence_get_begin_iter (hist->priv->seq);
682 !g_sequence_iter_is_end (cur);
683 cur = g_sequence_iter_next (cur)) {
684 g_ptr_array_add (result, g_sequence_get (cur));
685 }
686 return result;
687 }
688
689 /**
690 * rb_history_contains_entry:
691 * @hist: a #RBHistory
692 * @entry: a #RhythmDBEntry to check for
693 *
694 * Returns %TRUE if the entry is present in the history list.
695 *
696 * Return value: %TRUE if found
697 */
698 gboolean
699 rb_history_contains_entry (RBHistory *hist, RhythmDBEntry *entry)
700 {
701 g_return_val_if_fail (RB_IS_HISTORY (hist), FALSE);
702
703 return g_hash_table_lookup (hist->priv->entry_to_seqptr, entry) != NULL;
704 }