← Back to branch summary

~canonical-dx-team/ubuntu/maverick/gtk+2.0/menuproxy

« back to all changes in this revision

Viewing changes to gtk/gtksequence.c

  • Committer: Bazaar Package Importer
  • Author(s): Sebastien Bacher
  • Date: 2007-05-04 12:24:25 UTC
  • mfrom: (1.1.21 upstream)
  • Revision ID: james.westby@ubuntu.com-20070504122425-0m8midgzrp40y8w2
Tags: 2.10.12-1ubuntu1
* Sync with Debian
* New upstream version:
  Fixed bugs:
  - 379414 file chooser warnings when changing path in the entry
  - 418585 GtkFileChooserDefault sizing code is not DPI independent
  - 419568 Crash in search if start with special letter
  - 435062 build dies with icon cache validation
  - 379399 Segfault to call gtk_print_operation_run twice.
  - 387889 cups backend has problems when there are too many printers
  - 418531 invalid read to gtkicontheme.c gtk_icon_theme_lookup_icon...
  - 423916 crash in color scheme code
  - 424042 Segmentation fault while quickly pressing Alt+arrows
  - 415260 Protect against negative indices when setting values in G...
  - 419171 XGetVisualInfo() may not set nxvisuals
  - 128852 Gdk cursors don't look good on win32
  - 344657 Ctrl-H doesn't toggle "Show Hidden Files" setting
  - 345345 PrintOperation::paginate is not emitted for class handler
  - 347567 GtkPrintOperation::end-print is not emitted if it's cance...
  - 369112 gtk_ui_manager_add_ui should accept unnamed separator
  - 392015 Selected menu item invisible on Windows Vista
  - 399253 MS-Windows Theme Bottom Tab placement rendering glitches
  - 399425 gtk_input_dialog_fill_axes() adds child to gtkscrolledwin...
  - 403251 [patch] little memory leak in GtkPrintJob
  - 403267 [patch] memory leak in GtkPageSetupUnixDialog
  - 403470 MS-Windows Theme tab placement other than on top leaks a ...
  - 404506 Windows system fonts that have multi-byte font names cann...
  - 405089 Incorrect window placement for GtkEventBox private window
  - 405515 Minor leak in gtkfilesystemmodel.c
  - 405539 gdk_pixbuf_save() for PNG saver can return FALSE without ...
  - 415681 gdk_window_clear_area includes an extra line and column o...
  - 418219 GtkRecentChooser should apply filter before sorting and c...
  - 418403 Scroll to printer after selecting it from settings
  - 421985 _gtk_print_operation_platform_backend_launch_preview
  - 421990 gtk_print_job_get_surface
  - 421993 gtk_print_operation_init
  - 423064 Conditional jump or move depends on uninitialised value(s...
  - 423722 Fix printing header in gtk-demo
  - 424168 gtk_print_operation_run on async preview
  - 425655 Don't install gtk+-unix-print-2.0.pc on non-UNIX platforms
  - 425786 GDK segfaults if XineramaQueryScreens fails
  - 428665 Lpr Backend gets stuck in infinite loop during gtk_enumer...
  - 429902 GtkPrintOperation leaks cairo contextes
  - 431997 First delay of GdkPixbufAnimationIter is wrong
  - 433242 Inconsistent scroll arrow position calculations
  - 433972 Placing gtk.Expander inside a gtk.TextView() changes gtk....
  - 434261 _gtk_toolbar_elide_underscores incorrectly handles some s...
  - 383354 ctrl-L should make 'Location' entry disappear
  - 418673 gtk_recent_manager_add_item
  - 429732 gtk_accel_group_finalize accesses invalid memory
  - 435028 WM_CLIENT_LEADER is wrong on the leader_window
  - 431067 Background of the header window is not updated
  - 338843 add recent files support inside the ui manager
  - 148535 add drop shadow to menus, tooltips, etc. under Windows XP
* debian/control.in:
  - Conflicts on ubuntulooks (<= 0.9.11-1)
* debian/patches/15_default-fallback-icon-theme.patch:
  - patch from Debian, fallback on gnome icon theme

Show diffs side-by-side

added added

removed removed

Lines of Context:
gtk/gtksequence.c
 
1
/* GLIB - Library of useful routines for C programming
 
2
 * Copyright (C) 2002  Soeren Sandmann (sandmann@daimi.au.dk)
 
3
 *
 
4
 * This library is free software; you can redistribute it and/or
 
5
 * modify it under the terms of the GNU Lesser General Public
 
6
 * License as published by the Free Software Foundation; either
 
7
 * version 2 of the License, or (at your option) any later version.
 
8
 *
 
9
 * This library is distributed in the hope that it will be useful,
 
10
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
12
 * Lesser General Public License for more details.
 
13
 *
 
14
 * You should have received a copy of the GNU Lesser General Public
 
15
 * License along with this library; if not, write to the
 
16
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
17
 * Boston, MA 02111-1307, USA.
 
18
 */
 
19
 
 
20
#include <glib.h>
 
21
 
 
22
#include "gtksequence.h"
 
23
#include "gtkalias.h"
 
24
 
 
25
typedef struct _GtkSequenceNode GtkSequenceNode;
 
26
 
 
27
struct _GtkSequence {
 
28
  GtkSequenceNode *node;        /* does not necessarily point to the root.
 
29
                                 * You can splay it if you want it to
 
30
                                 */
 
31
  GDestroyNotify data_destroy_notify;
 
32
};
 
33
 
 
34
struct _GtkSequenceNode {
 
35
  guint is_end  : 1;
 
36
  gint  n_nodes : 31;           /* number of nodes below this node,
 
37
                                 * including this node
 
38
                                 */
 
39
  GtkSequenceNode *parent;
 
40
  GtkSequenceNode *left;
 
41
  GtkSequenceNode *right;
 
42
  
 
43
  GtkSequence *sequence;
 
44
  
 
45
  gpointer data;
 
46
};
 
47
 
 
48
static GtkSequenceNode *_gtk_sequence_node_new          (gpointer          data);
 
49
static GtkSequenceNode *_gtk_sequence_node_find_first   (GtkSequenceNode    *node);
 
50
static GtkSequenceNode *_gtk_sequence_node_find_last    (GtkSequenceNode    *node);
 
51
static GtkSequenceNode *_gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
 
52
                                                         gint pos);
 
53
static GtkSequenceNode *_gtk_sequence_node_prev         (GtkSequenceNode    *node);
 
54
static GtkSequenceNode *_gtk_sequence_node_next         (GtkSequenceNode    *node);
 
55
static gint           _gtk_sequence_node_get_pos (GtkSequenceNode    *node);
 
56
static GtkSequence     *_gtk_sequence_node_get_sequence (GtkSequenceNode    *node);
 
57
static GtkSequenceNode *_gtk_sequence_node_find_closest (GtkSequenceNode    *node,
 
58
                                                         GtkSequenceNode    *other,
 
59
                                                         GCompareDataFunc  cmp,
 
60
                                                         gpointer          data);
 
61
static gint           _gtk_sequence_node_get_length   (GtkSequenceNode    *node);
 
62
static void           _gtk_sequence_node_free         (GtkSequenceNode    *node,
 
63
                                                       GDestroyNotify    destroy);
 
64
#if 0
 
65
static gboolean       _gtk_sequence_node_is_singleton (GtkSequenceNode    *node);
 
66
#endif
 
67
static void           _gtk_sequence_node_split        (GtkSequenceNode    *node,
 
68
                                                       GtkSequenceNode   **left,
 
69
                                                       GtkSequenceNode   **right);
 
70
static void           _gtk_sequence_node_insert_before (GtkSequenceNode *node,
 
71
                                                        GtkSequenceNode *new);
 
72
static void           _gtk_sequence_node_remove        (GtkSequenceNode *node);
 
73
static void           _gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
 
74
                                                        GtkSequenceNode *new,
 
75
                                                        GCompareDataFunc cmp_func,
 
76
                                                        gpointer cmp_data);
 
77
 
 
78
/* GtkSequence */
 
79
GtkSequence *
 
80
_gtk_sequence_new                (GDestroyNotify           data_destroy)
 
81
{
 
82
  GtkSequence *seq = g_new (GtkSequence, 1);
 
83
  seq->data_destroy_notify = data_destroy;
 
84
  
 
85
  seq->node = _gtk_sequence_node_new (NULL);
 
86
  seq->node->is_end = TRUE;
 
87
  seq->node->sequence = seq;
 
88
  
 
89
  return seq;
 
90
}
 
91
 
 
92
void
 
93
_gtk_sequence_foreach         (GtkSequence       *seq,
 
94
                               GFunc              func,
 
95
                               gpointer           data)
 
96
{
 
97
  GtkSequencePtr ptr;
 
98
  
 
99
  g_return_if_fail (seq != NULL);
 
100
  g_return_if_fail (func != NULL);
 
101
  
 
102
  ptr = _gtk_sequence_get_begin_ptr (seq);
 
103
  
 
104
  while (!_gtk_sequence_ptr_is_end (ptr))
 
105
    {
 
106
      GtkSequenceNode *node = ptr;
 
107
      
 
108
      func (node->data, data);
 
109
      
 
110
      ptr = _gtk_sequence_ptr_next (ptr);
 
111
    }
 
112
  
 
113
}
 
114
 
 
115
void
 
116
_gtk_sequence_free               (GtkSequence               *seq)
 
117
{
 
118
  g_return_if_fail (seq != NULL);
 
119
  
 
120
  _gtk_sequence_node_free (seq->node, seq->data_destroy_notify);
 
121
  
 
122
  g_free (seq);
 
123
}
 
124
 
 
125
#if 0
 
126
static void
 
127
flatten_nodes (GtkSequenceNode *node, GList **list)
 
128
{
 
129
  g_print ("flatten %p\n", node);
 
130
  if (!node)
 
131
    return;
 
132
  else if (_gtk_sequence_node_is_singleton (node))
 
133
    *list = g_list_prepend (*list, node);
 
134
  else
 
135
    {
 
136
      GtkSequenceNode *left;
 
137
      GtkSequenceNode *right;
 
138
      
 
139
      _gtk_sequence_node_split (node, &left, &right);
 
140
      
 
141
      flatten_nodes (left, list);
 
142
      flatten_nodes (right, list);
 
143
    }
 
144
}
 
145
#endif
 
146
 
 
147
typedef struct SortInfo SortInfo;
 
148
struct SortInfo {
 
149
  GCompareDataFunc cmp;
 
150
  gpointer data;
 
151
};
 
152
 
 
153
static gint
 
154
node_compare (gconstpointer n1, gconstpointer n2, gpointer data)
 
155
{
 
156
  const SortInfo *info = data;
 
157
  const GtkSequenceNode *node1 = n1;
 
158
  const GtkSequenceNode *node2 = n2;
 
159
  gint retval;
 
160
  
 
161
  if (node1->is_end)
 
162
      return 1;
 
163
 
 
164
  if (node2->is_end)
 
165
      return -1;
 
166
 
 
167
  retval = (* info->cmp) (node1, node2, info->data);
 
168
 
 
169
  /* If the nodes are different, but the user-supplied compare function
 
170
   * compares them equal, then force an arbitrary (but consistent) order
 
171
   * on them, so that our sorts will be stable
 
172
   */
 
173
  if (retval != 0 || n1 == n2)
 
174
    return retval;
 
175
  
 
176
  if (n1 > n2)
 
177
    return 1;
 
178
  else
 
179
    return -1;
 
180
}
 
181
 
 
182
void
 
183
_gtk_sequence_append             (GtkSequence               *seq,
 
184
                                  gpointer                 data)
 
185
{
 
186
  GtkSequenceNode *node, *last;
 
187
  
 
188
  g_return_if_fail (seq != NULL);
 
189
  
 
190
  node = _gtk_sequence_node_new (data);
 
191
  node->sequence = seq;
 
192
  last = _gtk_sequence_node_find_last (seq->node);
 
193
  _gtk_sequence_node_insert_before (last, node);
 
194
}
 
195
#if 0
 
196
 
 
197
void
 
198
_gtk_sequence_prepend            (GtkSequence               *seq,
 
199
                                  gpointer                 data)
 
200
{
 
201
  GtkSequenceNode *node, *second;
 
202
  
 
203
  g_return_if_fail (seq != NULL);
 
204
  
 
205
  node = _gtk_sequence_node_new (data);
 
206
  node->sequence = seq;
 
207
  second = _gtk_sequence_node_next (_gtk_sequence_node_find_first (seq->node));
 
208
  
 
209
  _gtk_sequence_node_insert_before (second, node);
 
210
}
 
211
#endif
 
212
 
 
213
GtkSequencePtr 
 
214
_gtk_sequence_insert             (GtkSequencePtr             ptr,
 
215
                                  gpointer                 data)
 
216
{
 
217
  GtkSequenceNode *node;
 
218
  
 
219
  g_return_val_if_fail (ptr != NULL, NULL);
 
220
  
 
221
  node = _gtk_sequence_node_new (data);
 
222
  node->sequence = ptr->sequence;
 
223
 
 
224
  _gtk_sequence_node_insert_before (ptr, node);
 
225
 
 
226
  return node;
 
227
}
 
228
 
 
229
static void
 
230
_gtk_sequence_unlink (GtkSequence *seq,
 
231
                      GtkSequenceNode *node)
 
232
{
 
233
  g_assert (!node->is_end);
 
234
  
 
235
  seq->node = _gtk_sequence_node_next (node);
 
236
  
 
237
  g_assert (seq->node);
 
238
  g_assert (seq->node != node);
 
239
  
 
240
  _gtk_sequence_node_remove (node);
 
241
}
 
242
 
 
243
void
 
244
_gtk_sequence_remove             (GtkSequencePtr             ptr)
 
245
{
 
246
  GtkSequence *seq;
 
247
  
 
248
  g_return_if_fail (ptr != NULL);
 
249
  g_return_if_fail (!ptr->is_end);
 
250
  
 
251
  seq = _gtk_sequence_node_get_sequence (ptr); 
 
252
  _gtk_sequence_unlink (seq, ptr);
 
253
  _gtk_sequence_node_free (ptr, seq->data_destroy_notify);
 
254
}
 
255
 
 
256
void
 
257
_gtk_sequence_sort               (GtkSequence               *seq,
 
258
                                  GCompareDataFunc         cmp_func,
 
259
                                  gpointer                 cmp_data)
 
260
{
 
261
  GtkSequence *tmp;
 
262
  GtkSequenceNode *begin, *end;
 
263
  
 
264
  g_return_if_fail (seq != NULL);
 
265
  g_return_if_fail (cmp_func != NULL);
 
266
  
 
267
  begin = _gtk_sequence_get_begin_ptr (seq);
 
268
  end   = _gtk_sequence_get_end_ptr (seq);
 
269
  
 
270
  _gtk_sequence_remove_range (begin, end, &tmp);
 
271
  
 
272
  while (_gtk_sequence_get_length (tmp) > 0)
 
273
    {
 
274
      GtkSequenceNode *node = _gtk_sequence_get_begin_ptr (tmp);
 
275
      _gtk_sequence_unlink (tmp, node);
 
276
      
 
277
      _gtk_sequence_node_insert_sorted (seq->node, node, cmp_func, cmp_data);
 
278
    }
 
279
  
 
280
  _gtk_sequence_free (tmp);
 
281
}
 
282
 
 
283
gpointer
 
284
_gtk_sequence_ptr_get_data           (GtkSequencePtr             ptr)
 
285
{
 
286
  g_return_val_if_fail (ptr != NULL, NULL);
 
287
  g_return_val_if_fail (!ptr->is_end, NULL);
 
288
  
 
289
  return ptr->data;
 
290
}
 
291
 
 
292
GtkSequencePtr
 
293
_gtk_sequence_insert_sorted      (GtkSequence               *seq,
 
294
                                  gpointer                 data,
 
295
                                  GCompareDataFunc         cmp_func,
 
296
                                  gpointer                 cmp_data)
 
297
{
 
298
  GtkSequenceNode *new_node = _gtk_sequence_node_new (data);
 
299
  new_node->sequence = seq;
 
300
  _gtk_sequence_node_insert_sorted (seq->node, new_node, cmp_func, cmp_data);
 
301
  return new_node;
 
302
}
 
303
 
 
304
void
 
305
_gtk_sequence_insert_sequence    (GtkSequencePtr             ptr,
 
306
                                  GtkSequence               *other_seq)
 
307
{
 
308
  GtkSequenceNode *last;
 
309
  
 
310
  g_return_if_fail (other_seq != NULL);
 
311
  g_return_if_fail (ptr != NULL);
 
312
  
 
313
  last = _gtk_sequence_node_find_last (other_seq->node);
 
314
  _gtk_sequence_node_insert_before (ptr, last);
 
315
  _gtk_sequence_node_remove (last);
 
316
  _gtk_sequence_node_free (last, NULL);
 
317
  other_seq->node = NULL;
 
318
  _gtk_sequence_free (other_seq);
 
319
}
 
320
 
 
321
void
 
322
_gtk_sequence_concatenate        (GtkSequence               *seq1,
 
323
                                  GtkSequence               *seq2)
 
324
{
 
325
  GtkSequenceNode *last;
 
326
  
 
327
  g_return_if_fail (seq1 != NULL);
 
328
  g_return_if_fail (seq2 != NULL);
 
329
  
 
330
  last = _gtk_sequence_node_find_last (seq1->node);
 
331
  _gtk_sequence_insert_sequence (last, seq2);
 
332
}
 
333
 
 
334
/*
 
335
 * The new sequence inherits the destroy notify from the sequence that
 
336
 * beign and end comes from
 
337
 */
 
338
void
 
339
_gtk_sequence_remove_range       (GtkSequencePtr             begin,
 
340
                                  GtkSequencePtr             end,
 
341
                                  GtkSequence              **removed)
 
342
{
 
343
  GtkSequence *seq;
 
344
  GtkSequenceNode *s1, *s2, *s3;
 
345
  
 
346
  seq = _gtk_sequence_node_get_sequence (begin);
 
347
  
 
348
  g_assert (end != NULL);
 
349
  
 
350
  g_return_if_fail (seq == _gtk_sequence_node_get_sequence (end));
 
351
  
 
352
  _gtk_sequence_node_split (begin, &s1, &s2);
 
353
  _gtk_sequence_node_split (end, NULL, &s3);
 
354
  
 
355
  if (s1)
 
356
    _gtk_sequence_node_insert_before (s3, s1);
 
357
  
 
358
  seq->node = s3;
 
359
  
 
360
  if (removed)
 
361
    {
 
362
      *removed = _gtk_sequence_new (seq->data_destroy_notify);
 
363
      _gtk_sequence_node_insert_before ((*removed)->node, s2);
 
364
    }
 
365
  else
 
366
    {
 
367
      _gtk_sequence_node_free (s2, seq->data_destroy_notify);
 
368
    }
 
369
}
 
370
 
 
371
gint
 
372
_gtk_sequence_get_length         (GtkSequence               *seq)
 
373
{
 
374
  return _gtk_sequence_node_get_length (seq->node) - 1;
 
375
}
 
376
 
 
377
GtkSequencePtr
 
378
_gtk_sequence_get_end_ptr        (GtkSequence               *seq)
 
379
{
 
380
  g_return_val_if_fail (seq != NULL, NULL);
 
381
  return _gtk_sequence_node_find_last (seq->node);
 
382
}
 
383
 
 
384
GtkSequencePtr
 
385
_gtk_sequence_get_begin_ptr      (GtkSequence               *seq)
 
386
{
 
387
  g_return_val_if_fail (seq != NULL, NULL);
 
388
  return _gtk_sequence_node_find_first (seq->node);
 
389
}
 
390
 
 
391
/*
 
392
 * if pos > number of items or -1, will return end pointer
 
393
 */
 
394
GtkSequencePtr
 
395
_gtk_sequence_get_ptr_at_pos     (GtkSequence               *seq,
 
396
                                  gint                     pos)
 
397
{
 
398
  gint len;
 
399
  
 
400
  g_return_val_if_fail (seq != NULL, NULL);
 
401
  
 
402
  len = _gtk_sequence_get_length (seq);
 
403
  
 
404
  if (pos > len || pos == -1)
 
405
    pos = len;
 
406
  
 
407
  return _gtk_sequence_node_find_by_pos (seq->node, pos);
 
408
}
 
409
 
 
410
 
 
411
/* GtkSequencePtr */
 
412
gboolean
 
413
_gtk_sequence_ptr_is_end         (GtkSequencePtr             ptr)
 
414
{
 
415
  g_return_val_if_fail (ptr != NULL, FALSE);
 
416
  return ptr->is_end;
 
417
}
 
418
 
 
419
gboolean
 
420
_gtk_sequence_ptr_is_begin       (GtkSequencePtr             ptr)
 
421
{
 
422
  return (_gtk_sequence_node_prev (ptr) == ptr);
 
423
}
 
424
 
 
425
/* If you call this on an end pointer you'll get
 
426
 * the length of the sequence
 
427
 */
 
428
gint
 
429
_gtk_sequence_ptr_get_position   (GtkSequencePtr             ptr)
 
430
{
 
431
  g_return_val_if_fail (ptr != NULL, -1);
 
432
  
 
433
  return _gtk_sequence_node_get_pos (ptr);
 
434
}
 
435
 
 
436
GtkSequencePtr
 
437
_gtk_sequence_ptr_next           (GtkSequencePtr             ptr)
 
438
{
 
439
  g_return_val_if_fail (ptr != NULL, NULL);
 
440
  
 
441
  return _gtk_sequence_node_next (ptr);
 
442
}
 
443
 
 
444
GtkSequencePtr
 
445
_gtk_sequence_ptr_prev           (GtkSequencePtr             ptr)
 
446
{
 
447
  g_return_val_if_fail (ptr != NULL, NULL);
 
448
  
 
449
  return _gtk_sequence_node_prev (ptr);
 
450
}
 
451
 
 
452
GtkSequencePtr
 
453
_gtk_sequence_ptr_move           (GtkSequencePtr             ptr,
 
454
                                  guint                    delta)
 
455
{
 
456
  gint new_pos;
 
457
  
 
458
  g_return_val_if_fail (ptr != NULL, NULL);
 
459
  
 
460
  new_pos = _gtk_sequence_node_get_pos (ptr) + delta;
 
461
  
 
462
  return _gtk_sequence_node_find_by_pos (ptr, new_pos);
 
463
}
 
464
 
 
465
void
 
466
_gtk_sequence_sort_changed  (GtkSequencePtr          ptr,
 
467
                             GCompareDataFunc        cmp_func,
 
468
                             gpointer                cmp_data)
 
469
  
 
470
{
 
471
  GtkSequence *seq;
 
472
 
 
473
  g_return_if_fail (ptr != NULL);
 
474
  g_return_if_fail (!ptr->is_end);
 
475
 
 
476
  seq = _gtk_sequence_node_get_sequence (ptr);
 
477
  _gtk_sequence_unlink (seq, ptr);
 
478
  _gtk_sequence_node_insert_sorted (seq->node, ptr, cmp_func, cmp_data);
 
479
}
 
480
 
 
481
/* search
 
482
 *
 
483
 * The only restriction on the search function is that it
 
484
 * must not delete any nodes. It is permitted to insert new nodes,
 
485
 * but the caller should "know what he is doing"
 
486
 */
 
487
void
 
488
_gtk_sequence_search             (GtkSequence               *seq,
 
489
                                  GtkSequenceSearchFunc      f,
 
490
                                  gpointer                 data)
 
491
{
 
492
  GQueue *intervals = g_queue_new ();
 
493
  
 
494
  g_queue_push_tail (intervals, _gtk_sequence_node_find_first (seq->node));
 
495
  g_queue_push_tail (intervals, _gtk_sequence_node_find_last (seq->node));
 
496
  
 
497
  while (!g_queue_is_empty (intervals))
 
498
    {
 
499
      GtkSequenceNode *begin = g_queue_pop_head (intervals);
 
500
      GtkSequenceNode *end   = g_queue_pop_head (intervals);
 
501
      
 
502
      if (f (begin, end, data))
 
503
        {
 
504
          gint begin_pos = _gtk_sequence_node_get_pos (begin);
 
505
          gint end_pos   = _gtk_sequence_node_get_pos (end);
 
506
          
 
507
          if (end_pos - begin_pos > 1)
 
508
            {
 
509
              GtkSequenceNode *mid;
 
510
              gint mid_pos;
 
511
              
 
512
              mid_pos = begin_pos + (end_pos - begin_pos) / 2;
 
513
              mid = _gtk_sequence_node_find_by_pos (begin, mid_pos);
 
514
              
 
515
              g_queue_push_tail (intervals, begin);
 
516
              g_queue_push_tail (intervals, mid);
 
517
              
 
518
              g_queue_push_tail (intervals, mid);
 
519
              g_queue_push_tail (intervals, end);
 
520
            }
 
521
        }
 
522
    }
 
523
  
 
524
  g_queue_free (intervals);
 
525
}
 
526
 
 
527
#if 0
 
528
/* aggregates */
 
529
void
 
530
_gtk_sequence_add_aggregate      (GtkSequence               *seq,
 
531
                                  const gchar             *aggregate,
 
532
                                  GtkSequenceAggregateFunc   f,
 
533
                                  gpointer                 data,
 
534
                                  GDestroyNotify           destroy)
 
535
{
 
536
  /* FIXME */
 
537
}
 
538
 
 
539
void
 
540
_gtk_sequence_remove_aggregate   (GtkSequence               *seq,
 
541
                                  const gchar              aggregate)
 
542
{
 
543
  /* FIXME */
 
544
  
 
545
}
 
546
 
 
547
void
 
548
_gtk_sequence_set_aggregate_data (GtkSequencePtr             ptr,
 
549
                                  const gchar             *aggregate,
 
550
                                  gpointer                 data)
 
551
{
 
552
  /* FIXME */
 
553
  
 
554
}
 
555
 
 
556
gpointer
 
557
_gtk_sequence_get_aggregate_data (GtkSequencePtr             begin,
 
558
                                  GtkSequencePtr             end,
 
559
                                  const gchar             *aggregate)
 
560
{
 
561
  g_assert_not_reached();
 
562
  return NULL;
 
563
}
 
564
#endif
 
565
 
 
566
 
 
567
/* Nodes
 
568
 */
 
569
static void
 
570
_gtk_sequence_node_update_fields (GtkSequenceNode *node)
 
571
{
 
572
  g_assert (node != NULL);
 
573
  
 
574
  node->n_nodes = 1;
 
575
  
 
576
  if (node->left)
 
577
    node->n_nodes += node->left->n_nodes;
 
578
  
 
579
  if (node->right)
 
580
    node->n_nodes += node->right->n_nodes;
 
581
  
 
582
#if 0
 
583
  if (node->left || node->right)
 
584
    g_assert (node->n_nodes > 1);
 
585
#endif
 
586
}
 
587
 
 
588
#define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
 
589
#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
 
590
 
 
591
static void
 
592
_gtk_sequence_node_rotate (GtkSequenceNode *node)
 
593
{
 
594
  GtkSequenceNode *tmp, *old;
 
595
  
 
596
  g_assert (node->parent);
 
597
  g_assert (node->parent != node);
 
598
  
 
599
  if (NODE_LEFT_CHILD (node))
 
600
    {
 
601
      /* rotate right */
 
602
      tmp = node->right;
 
603
      
 
604
      node->right = node->parent;
 
605
      node->parent = node->parent->parent;
 
606
      if (node->parent)
 
607
        {
 
608
          if (node->parent->left == node->right)
 
609
            node->parent->left = node;
 
610
          else
 
611
            node->parent->right = node;
 
612
        }
 
613
      
 
614
      g_assert (node->right);
 
615
      
 
616
      node->right->parent = node;
 
617
      node->right->left = tmp;
 
618
      
 
619
      if (node->right->left)
 
620
        node->right->left->parent = node->right;
 
621
      
 
622
      old = node->right;
 
623
    }
 
624
  else
 
625
    {
 
626
      /* rotate left */
 
627
      tmp = node->left;
 
628
      
 
629
      node->left = node->parent;
 
630
      node->parent = node->parent->parent;
 
631
      if (node->parent)
 
632
        {
 
633
          if (node->parent->right == node->left)
 
634
            node->parent->right = node;
 
635
          else
 
636
            node->parent->left = node;
 
637
        }
 
638
      
 
639
      g_assert (node->left);
 
640
      
 
641
      node->left->parent = node;
 
642
      node->left->right = tmp;
 
643
      
 
644
      if (node->left->right)
 
645
        node->left->right->parent = node->left;
 
646
      
 
647
      old = node->left;
 
648
    }
 
649
  
 
650
  _gtk_sequence_node_update_fields (old);
 
651
  _gtk_sequence_node_update_fields (node);
 
652
}
 
653
 
 
654
static GtkSequenceNode *
 
655
splay (GtkSequenceNode *node)
 
656
{
 
657
  while (node->parent)
 
658
    {
 
659
      if (!node->parent->parent)
 
660
        {
 
661
          /* zig */
 
662
          _gtk_sequence_node_rotate (node);
 
663
        }
 
664
      else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
 
665
               (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
 
666
        {
 
667
          /* zig-zig */
 
668
          _gtk_sequence_node_rotate (node->parent);
 
669
          _gtk_sequence_node_rotate (node);
 
670
        }
 
671
      else
 
672
        {
 
673
          /* zig-zag */
 
674
          _gtk_sequence_node_rotate (node);
 
675
          _gtk_sequence_node_rotate (node);
 
676
        }
 
677
    }
 
678
  
 
679
  return node;
 
680
}
 
681
 
 
682
static GtkSequenceNode *
 
683
_gtk_sequence_node_new (gpointer          data)
 
684
{
 
685
  GtkSequenceNode *node = g_new0 (GtkSequenceNode, 1);
 
686
  
 
687
  node->parent = NULL;
 
688
  node->left = NULL;
 
689
  node->right = NULL;
 
690
  
 
691
  node->data = data;
 
692
  node->is_end = FALSE;
 
693
  node->n_nodes = 1;
 
694
  
 
695
  return node;
 
696
}
 
697
 
 
698
static GtkSequenceNode *
 
699
find_min (GtkSequenceNode *node)
 
700
{
 
701
  splay (node);
 
702
  
 
703
  while (node->left)
 
704
    node = node->left;
 
705
  
 
706
  return node;
 
707
}
 
708
 
 
709
static GtkSequenceNode *
 
710
find_max (GtkSequenceNode *node)
 
711
{
 
712
  splay (node);
 
713
  
 
714
  while (node->right)
 
715
    node = node->right;
 
716
  
 
717
  return node;
 
718
}
 
719
 
 
720
static GtkSequenceNode *
 
721
_gtk_sequence_node_find_first   (GtkSequenceNode    *node)
 
722
{
 
723
  return splay (find_min (node));
 
724
}
 
725
 
 
726
static GtkSequenceNode *
 
727
_gtk_sequence_node_find_last    (GtkSequenceNode    *node)
 
728
{
 
729
  return splay (find_max (node));
 
730
}
 
731
 
 
732
static gint
 
733
get_n_nodes (GtkSequenceNode *node)
 
734
{
 
735
  if (node)
 
736
    return node->n_nodes;
 
737
  else
 
738
    return 0;
 
739
}
 
740
 
 
741
static GtkSequenceNode *
 
742
_gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
 
743
                                 gint              pos)
 
744
{
 
745
  gint i;
 
746
  
 
747
  g_assert (node != NULL);
 
748
  
 
749
  splay (node);
 
750
  
 
751
  while ((i = get_n_nodes (node->left)) != pos)
 
752
    {
 
753
      if (i < pos)
 
754
        {
 
755
          node = node->right;
 
756
          pos -= (i + 1);
 
757
        }
 
758
      else
 
759
        {
 
760
          node = node->left;
 
761
          g_assert (node->parent != NULL);
 
762
        }
 
763
    }
 
764
  
 
765
  return splay (node);
 
766
}
 
767
 
 
768
static GtkSequenceNode *
 
769
_gtk_sequence_node_prev         (GtkSequenceNode    *node)
 
770
{
 
771
  splay (node);
 
772
  
 
773
  if (node->left)
 
774
    {
 
775
      node = node->left;
 
776
      while (node->right)
 
777
        node = node->right;
 
778
    }
 
779
  
 
780
  return splay (node);
 
781
}
 
782
 
 
783
static GtkSequenceNode *
 
784
_gtk_sequence_node_next         (GtkSequenceNode    *node)
 
785
{
 
786
  splay (node);
 
787
  
 
788
  if (node->right)
 
789
    {
 
790
      node = node->right;
 
791
      while (node->left)
 
792
        node = node->left;
 
793
    }
 
794
  
 
795
  return splay (node);
 
796
}
 
797
 
 
798
static gint
 
799
_gtk_sequence_node_get_pos (GtkSequenceNode    *node)
 
800
{
 
801
  splay (node);
 
802
  
 
803
  return get_n_nodes (node->left);
 
804
}
 
805
 
 
806
static GtkSequence *
 
807
_gtk_sequence_node_get_sequence (GtkSequenceNode    *node)
 
808
{
 
809
  splay (node);
 
810
  
 
811
  return node->sequence;
 
812
}
 
813
 
 
814
static GtkSequenceNode *
 
815
_gtk_sequence_node_find_closest (GtkSequenceNode    *node,
 
816
                                 GtkSequenceNode    *other,
 
817
                                 GCompareDataFunc  cmp,
 
818
                                 gpointer          data)
 
819
{
 
820
  GtkSequenceNode *best;
 
821
  gint c;
 
822
  
 
823
  splay (node);
 
824
 
 
825
  do
 
826
    {
 
827
      best = node;
 
828
 
 
829
      if ((c = cmp (node, other, data)) != 0)
 
830
        {
 
831
          if (c < 0)
 
832
            node = node->right;
 
833
          else
 
834
            node = node->left;
 
835
        }
 
836
    }
 
837
  while (c != 0 && node != NULL);
 
838
  
 
839
  return best;
 
840
}
 
841
 
 
842
static void
 
843
_gtk_sequence_node_free         (GtkSequenceNode    *node,
 
844
                                 GDestroyNotify    destroy)
 
845
{
 
846
  /* FIXME:
 
847
   *
 
848
   * This is to avoid excessively deep recursions. A splay tree is not necessarily
 
849
   * balanced at all.
 
850
   *
 
851
   * I _think_ this is still linear in the number of nodes, but I'd like to
 
852
   * do something more efficient.
 
853
   */
 
854
  
 
855
  while (node)
 
856
    {
 
857
      GtkSequenceNode *next;
 
858
      
 
859
      node = splay (find_min (node));
 
860
      next = node->right;
 
861
      if (next)
 
862
        next->parent = NULL;
 
863
      
 
864
      if (destroy && !node->is_end)
 
865
        destroy (node->data);
 
866
      g_free (node);
 
867
      
 
868
      node = next;
 
869
    }
 
870
}
 
871
 
 
872
#if 0
 
873
static gboolean
 
874
_gtk_sequence_node_is_singleton (GtkSequenceNode    *node)
 
875
{
 
876
  splay (node);
 
877
  
 
878
  if (node->left || node->right)
 
879
    return FALSE;
 
880
  
 
881
  return TRUE;
 
882
}
 
883
#endif
 
884
 
 
885
static void
 
886
_gtk_sequence_node_split        (GtkSequenceNode    *node,
 
887
                                 GtkSequenceNode   **left,
 
888
                                 GtkSequenceNode   **right)
 
889
{
 
890
  GtkSequenceNode *left_tree;
 
891
  
 
892
  splay (node);
 
893
  
 
894
  left_tree = node->left;
 
895
  if (left_tree)
 
896
    {
 
897
      left_tree->parent = NULL;
 
898
      _gtk_sequence_node_update_fields (left_tree);
 
899
    }
 
900
  
 
901
  node->left = NULL;
 
902
  _gtk_sequence_node_update_fields (node);
 
903
  
 
904
  if (left)
 
905
    *left = left_tree;
 
906
  
 
907
  if (right)
 
908
    *right = node;
 
909
}
 
910
 
 
911
static void
 
912
_gtk_sequence_node_insert_before (GtkSequenceNode *node,
 
913
                                  GtkSequenceNode *new)
 
914
{
 
915
  g_assert (node != NULL);
 
916
  g_assert (new != NULL);
 
917
  
 
918
  splay (node);
 
919
  
 
920
  new = splay (find_min (new));
 
921
  g_assert (new->left == NULL);
 
922
  
 
923
  if (node->left)
 
924
    node->left->parent = new;
 
925
  
 
926
  new->left = node->left;
 
927
  new->parent = node;
 
928
  
 
929
  node->left = new;
 
930
  
 
931
  _gtk_sequence_node_update_fields (new);
 
932
  _gtk_sequence_node_update_fields (node);
 
933
}
 
934
 
 
935
static gint
 
936
_gtk_sequence_node_get_length (GtkSequenceNode    *node)
 
937
{
 
938
  g_assert (node != NULL);
 
939
  
 
940
  splay (node);
 
941
  return node->n_nodes;
 
942
}
 
943
 
 
944
static void
 
945
_gtk_sequence_node_remove        (GtkSequenceNode *node)
 
946
{
 
947
  GtkSequenceNode *right, *left;
 
948
  
 
949
  splay (node);
 
950
  
 
951
  left = node->left;
 
952
  right = node->right;
 
953
  
 
954
  node->left = node->right = NULL;
 
955
  
 
956
  if (right)
 
957
    {
 
958
      right->parent = NULL;
 
959
      
 
960
      right = _gtk_sequence_node_find_first (right);
 
961
      g_assert (right->left == NULL);
 
962
      
 
963
      right->left = left;
 
964
      if (left)
 
965
        {
 
966
          left->parent = right;
 
967
          _gtk_sequence_node_update_fields (right);
 
968
        }
 
969
    }
 
970
  else if (left)
 
971
    left->parent = NULL;
 
972
}
 
973
 
 
974
#if 0
 
975
/* debug func */
 
976
static gint
 
977
_gtk_sequence_node_calc_height (GtkSequenceNode *node)
 
978
{
 
979
  /* breadth first traversal */
 
980
  gint height = 0;
 
981
  GQueue *nodes = g_queue_new ();
 
982
  
 
983
  g_queue_push_tail (nodes, node);
 
984
  
 
985
  while (!g_queue_is_empty (nodes))
 
986
    {
 
987
      GQueue *tmp = g_queue_new ();
 
988
      
 
989
      height++;
 
990
      while (!g_queue_is_empty (nodes))
 
991
        {
 
992
          GtkSequenceNode *node = g_queue_pop_head (nodes);
 
993
          if (node->left)
 
994
            g_queue_push_tail (tmp, node->left);
 
995
          if (node->right)
 
996
            g_queue_push_tail (tmp, node->right);
 
997
        }
 
998
      
 
999
      g_queue_free (nodes);
 
1000
      
 
1001
      nodes = tmp;
 
1002
    }
 
1003
  g_queue_free (nodes);
 
1004
  
 
1005
  return height;
 
1006
}
 
1007
#endif
 
1008
 
 
1009
static void
 
1010
_gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
 
1011
                                  GtkSequenceNode *new,
 
1012
                                  GCompareDataFunc cmp_func,
 
1013
                                  gpointer cmp_data)
 
1014
{
 
1015
  SortInfo info;
 
1016
  GtkSequenceNode *closest;
 
1017
  info.cmp = cmp_func;
 
1018
  info.data = cmp_data;
 
1019
  
 
1020
  closest =
 
1021
    _gtk_sequence_node_find_closest (node, new, node_compare, &info);
 
1022
 
 
1023
  g_assert (closest != new);
 
1024
  
 
1025
  if (node_compare (new, closest, &info) > 0)
 
1026
    closest = _gtk_sequence_node_next (closest);
 
1027
 
 
1028
  _gtk_sequence_node_insert_before (closest, new);
 
1029
}
 
1030
 
 
1031
static gint
 
1032
_gtk_sequence_node_calc_height (GtkSequenceNode *node)
 
1033
{
 
1034
  gint left_height;
 
1035
  gint right_height;
 
1036
  
 
1037
  if (node)
 
1038
    {
 
1039
      left_height = 0;
 
1040
      right_height = 0;
 
1041
      
 
1042
      if (node->left)
 
1043
        left_height = _gtk_sequence_node_calc_height (node->left);
 
1044
      
 
1045
      if (node->right)
 
1046
        right_height = _gtk_sequence_node_calc_height (node->right);
 
1047
      
 
1048
      return MAX (left_height, right_height) + 1;
 
1049
    }
 
1050
  
 
1051
  return 0;
 
1052
}
 
1053
 
 
1054
gint
 
1055
_gtk_sequence_calc_tree_height   (GtkSequence               *seq)
 
1056
{
 
1057
  GtkSequenceNode *node = seq->node;
 
1058
  gint r, l;
 
1059
  while (node->parent)
 
1060
    node = node->parent;
 
1061
  
 
1062
  if (node)
 
1063
    {
 
1064
      r = _gtk_sequence_node_calc_height (node->right);
 
1065
      l = _gtk_sequence_node_calc_height (node->left);
 
1066
      
 
1067
      return MAX (r, l) + 1;
 
1068
    }
 
1069
  else
 
1070
    return 0;
 
1071
}
 
1072
 
 
1073
GtkSequence   *
 
1074
_gtk_sequence_ptr_get_sequence (GtkSequencePtr    ptr)
 
1075
{
 
1076
  GtkSequenceNode *node = ptr;
 
1077
  
 
1078
  return node->sequence;
 
1079
}
 
1080
 
 
1081
void
 
1082
_gtk_sequence_swap (GtkSequencePtr a,
 
1083
                    GtkSequencePtr b)
 
1084
{
 
1085
  GtkSequenceNode *leftmost, *rightmost, *rightmost_next;
 
1086
  int a_pos, b_pos;
 
1087
  
 
1088
  g_return_if_fail (!_gtk_sequence_ptr_is_end (a));
 
1089
  g_return_if_fail (!_gtk_sequence_ptr_is_end (b));
 
1090
 
 
1091
  if (a == b)
 
1092
      return;
 
1093
 
 
1094
  a_pos = _gtk_sequence_ptr_get_position (a);
 
1095
  b_pos = _gtk_sequence_ptr_get_position (b);
 
1096
 
 
1097
  if (a_pos > b_pos)
 
1098
    {
 
1099
      leftmost = b;
 
1100
      rightmost = a;
 
1101
    }
 
1102
  else
 
1103
    {
 
1104
      leftmost = a;
 
1105
      rightmost = b;
 
1106
    }
 
1107
 
 
1108
  rightmost_next = _gtk_sequence_node_next (rightmost);
 
1109
 
 
1110
  /* Situation now:  ..., leftmost, ......., rightmost, rightmost_next, ... */
 
1111
  
 
1112
  _gtk_sequence_move (rightmost, leftmost);
 
1113
  _gtk_sequence_move (leftmost, rightmost_next);
 
1114
}
 
1115
 
 
1116
void
 
1117
_gtk_sequence_move (GtkSequencePtr ptr,
 
1118
                    GtkSequencePtr new_pos)
 
1119
{
 
1120
  g_return_if_fail (ptr != NULL);
 
1121
  g_return_if_fail (new_pos != NULL);
 
1122
  
 
1123
  if (ptr == new_pos)
 
1124
    return;
 
1125
  
 
1126
  _gtk_sequence_unlink (ptr->sequence, ptr);
 
1127
  _gtk_sequence_node_insert_before (new_pos, ptr);
 
1128
}
 
1129
 
 
1130
/* Overwrites the existing pointer. */
 
1131
void
 
1132
_gtk_sequence_set             (GtkSequencePtr     ptr,
 
1133
                               gpointer           data)
 
1134
{
 
1135
  GtkSequence *seq;
 
1136
 
 
1137
  g_return_if_fail (!_gtk_sequence_ptr_is_end (ptr));
 
1138
  
 
1139
  seq = _gtk_sequence_node_get_sequence (ptr);
 
1140
  if (seq->data_destroy_notify)
 
1141
    seq->data_destroy_notify (ptr->data);
 
1142
  ptr->data = data;
 
1143
}