← Back to branch summary

~posulliv/drizzle/optimizer-style-cleanup

« back to all changes in this revision

Viewing changes to plugin/pbxt/src/sortedlist_xt.cc

  • Committer: Padraig O'Sullivan
  • Date: 2010-04-17 01:38:47 UTC
  • mfrom: (1237.9.238 bad-staging)
  • Revision ID: osullivan.padraig@gmail.com-20100417013847-ibjioqsfbmf5yg4g
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/pbxt/src/sortedlist_xt.cc
 
1
/* Copyright (c) 2005 PrimeBase Technologies GmbH
 
2
 *
 
3
 * PrimeBase XT
 
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
 * This program is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU General Public License
 
16
 * along with this program; if not, write to the Free Software
 
17
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 
18
 *
 
19
 * 2005-02-04   Paul McCullagh
 
20
 *
 
21
 * H&G2JCtL
 
22
 */
 
23
 
 
24
#include "xt_config.h"
 
25
 
 
26
#include "pthread_xt.h"
 
27
#include "thread_xt.h"
 
28
#include "sortedlist_xt.h"
 
29
 
 
30
XTSortedListPtr xt_new_sortedlist_ns(u_int item_size, u_int grow_size, XTCompareFunc comp_func, void *thunk, XTFreeFunc free_func)
 
31
{
 
32
        XTSortedListPtr sl;
 
33
 
 
34
        if (!(sl = (XTSortedListPtr) xt_calloc_ns(sizeof(XTSortedListRec))))
 
35
                return NULL;
 
36
        sl->sl_item_size = item_size;
 
37
        sl->sl_grow_size = grow_size;
 
38
        sl->sl_comp_func = comp_func;
 
39
        sl->sl_thunk = thunk;
 
40
        sl->sl_free_func = free_func;
 
41
        sl->sl_current_size = 0;
 
42
        return sl;
 
43
}
 
44
 
 
45
XTSortedListPtr xt_new_sortedlist(XTThreadPtr self, u_int item_size, u_int initial_size, u_int grow_size, XTCompareFunc comp_func, void *thunk, XTFreeFunc free_func, xtBool with_lock, xtBool with_cond)
 
46
{
 
47
        XTSortedListPtr sl;
 
48
 
 
49
        sl = (XTSortedListPtr) xt_calloc(self, sizeof(XTSortedListRec));
 
50
        xt_init_sortedlist(self, sl, item_size, initial_size, grow_size, comp_func, thunk, free_func, with_lock, with_cond);
 
51
        return sl;
 
52
}
 
53
 
 
54
xtPublic void xt_init_sortedlist(XTThreadPtr self, XTSortedListPtr sl, u_int item_size, u_int initial_size, u_int grow_size, XTCompareFunc comp_func, void *thunk, XTFreeFunc free_func, xtBool with_lock, xtBool with_cond)
 
55
{
 
56
        sl->sl_item_size = item_size;
 
57
        sl->sl_grow_size = grow_size;
 
58
        sl->sl_comp_func = comp_func;
 
59
        sl->sl_thunk = thunk;
 
60
        sl->sl_free_func = free_func;
 
61
        sl->sl_current_size = initial_size;
 
62
 
 
63
        if (initial_size) {
 
64
                try_(a) {
 
65
                        sl->sl_data = (char *) xt_malloc(self, initial_size * item_size);
 
66
                }
 
67
                catch_(a) {
 
68
                        xt_free(self, sl);
 
69
                        throw_();
 
70
                }
 
71
                cont_(a);
 
72
        }
 
73
 
 
74
        if (with_lock || with_cond) {
 
75
                sl->sl_lock = (xt_mutex_type *) xt_calloc(self, sizeof(xt_mutex_type));
 
76
                try_(b) {
 
77
                        xt_init_mutex_with_autoname(self, sl->sl_lock);
 
78
                }
 
79
                catch_(b) {
 
80
                        xt_free(self, sl->sl_lock);
 
81
                        sl->sl_lock = NULL;
 
82
                        xt_free_sortedlist(self, sl);
 
83
                        throw_();
 
84
                }
 
85
                cont_(b);
 
86
        }
 
87
 
 
88
        if (with_cond) {
 
89
                sl->sl_cond = (xt_cond_type *) xt_calloc(self, sizeof(xt_cond_type));
 
90
                try_(c) {
 
91
                        xt_init_cond(self, sl->sl_cond);
 
92
                }
 
93
                catch_(c) {
 
94
                        xt_free(self, sl->sl_cond);
 
95
                        sl->sl_cond = NULL;
 
96
                        xt_free_sortedlist(self, sl);
 
97
                        throw_();
 
98
                }
 
99
                cont_(c);
 
100
        }
 
101
}
 
102
 
 
103
xtPublic xtBool xt_init_sortedlist_ns(XTSortedListPtr sl, u_int item_size, u_int initial_size, u_int grow_size, XTCompareFunc comp_func, void *thunk, XTFreeFunc free_func, xtBool with_lock, xtBool with_cond)
 
104
{
 
105
        memset(sl, 0, sizeof(XTSortedListRec));
 
106
        sl->sl_item_size = item_size;
 
107
        sl->sl_grow_size = grow_size;
 
108
        sl->sl_comp_func = comp_func;
 
109
        sl->sl_thunk = thunk;
 
110
        sl->sl_free_func = free_func;
 
111
        sl->sl_current_size = initial_size;
 
112
 
 
113
        if (initial_size) {
 
114
                if (!(sl->sl_data = (char *) xt_malloc_ns(initial_size * item_size)))
 
115
                        goto failed;
 
116
        }
 
117
 
 
118
        if (with_lock || with_cond) {
 
119
                if (!(sl->sl_lock = (xt_mutex_type *) xt_calloc_ns(sizeof(xt_mutex_type))))
 
120
                        goto failed;
 
121
                if (!xt_init_mutex_with_autoname(NULL, sl->sl_lock))
 
122
                        goto failed;
 
123
        }
 
124
 
 
125
        if (with_cond) {
 
126
                if (!(sl->sl_cond = (xt_cond_type *) xt_calloc_ns(sizeof(xt_cond_type))))
 
127
                        goto failed;
 
128
                if (!xt_init_cond(NULL, sl->sl_cond))
 
129
                        goto failed;
 
130
        }
 
131
 
 
132
        return OK;
 
133
 
 
134
        failed:
 
135
        xt_free_sortedlist(NULL, sl);
 
136
        return FAILED;
 
137
}
 
138
 
 
139
xtPublic void xt_empty_sortedlist(XTThreadPtr self, XTSortedListPtr sl)
 
140
{
 
141
        if (sl->sl_lock)
 
142
                xt_lock_mutex(self, sl->sl_lock);
 
143
        if (sl->sl_data) {
 
144
                if (sl->sl_free_func) {
 
145
                        while (sl->sl_usage_count > 0) {
 
146
                                sl->sl_usage_count--;
 
147
                                if (sl->sl_free_func)
 
148
                                        (*sl->sl_free_func)(self, sl->sl_thunk, &sl->sl_data[sl->sl_usage_count * sl->sl_item_size]);
 
149
                        }
 
150
                }
 
151
                else
 
152
                        sl->sl_usage_count = 0;
 
153
        }
 
154
        if (sl->sl_lock)
 
155
                xt_unlock_mutex(self, sl->sl_lock);
 
156
}
 
157
 
 
158
xtPublic void xt_clear_sortedlist(XTSortedListPtr sl)
 
159
{
 
160
        if (sl->sl_data) {
 
161
                xt_free_ns(sl->sl_data);
 
162
                sl->sl_data = NULL;
 
163
        }
 
164
        if (sl->sl_lock) {
 
165
                xt_free_mutex(sl->sl_lock);
 
166
                xt_free_ns(sl->sl_lock);
 
167
        }
 
168
        if (sl->sl_cond) {
 
169
                xt_free_cond(sl->sl_cond);
 
170
                xt_free_ns(sl->sl_cond);
 
171
        }
 
172
}
 
173
 
 
174
xtPublic void xt_free_sortedlist(XTThreadPtr self, XTSortedListPtr sl)
 
175
{
 
176
        xt_empty_sortedlist(self, sl);
 
177
        xt_clear_sortedlist(sl);
 
178
        xt_free(self, sl);
 
179
}
 
180
 
 
181
xtPublic void *xt_sl_find(XTThreadPtr self, XTSortedListPtr sl, void *key)
 
182
{
 
183
        void    *result;
 
184
        size_t  idx;
 
185
 
 
186
        if (sl->sl_usage_count == 0)
 
187
                return NULL;
 
188
        else if (sl->sl_usage_count == 1) {
 
189
                if ((*sl->sl_comp_func)(self, sl->sl_thunk, key, sl->sl_data) == 0)
 
190
                        return sl->sl_data;
 
191
                return NULL;
 
192
        }
 
193
        result = xt_bsearch(self, key, sl->sl_data, sl->sl_usage_count, sl->sl_item_size, &idx, sl->sl_thunk, sl->sl_comp_func);
 
194
        return result;
 
195
}
 
196
 
 
197
/* This function is the same as find, but it also returns the
 
198
 * index position for the item.
 
199
 *
 
200
 * If the item is not in the list, then it returns the index at which the item
 
201
 * should be inserted.
 
202
 */
 
203
xtPublic void *xt_sl_search(XTThreadPtr self, size_t *idx, XTSortedListPtr sl, void *key)
 
204
{
 
205
        if (sl->sl_usage_count == 0) {
 
206
                *idx = 0;
 
207
                return NULL;
 
208
        }
 
209
        else if (sl->sl_usage_count == 1) {
 
210
                int r;
 
211
 
 
212
                if ((r = (*sl->sl_comp_func)(self, sl->sl_thunk, key, sl->sl_data)) == 0) {
 
213
                        *idx = 0;
 
214
                        return sl->sl_data;
 
215
                }
 
216
                if (r > 0)
 
217
                        *idx = 1;
 
218
                else
 
219
                        *idx = 0;
 
220
                return NULL;
 
221
        }
 
222
        return xt_bsearch(self, key, sl->sl_data, sl->sl_usage_count, sl->sl_item_size, idx, sl->sl_thunk, sl->sl_comp_func);
 
223
}
 
224
 
 
225
/*
 
226
 * Returns:
 
227
 * 1 = Value inserted.
 
228
 * 2 = Value not inserted, already in the list (returned value is index + 2).
 
229
 * 0 = An error occurred.
 
230
 */
 
231
xtPublic int xt_sl_insert(XTThreadPtr self, XTSortedListPtr sl, void *key, void *data)
 
232
{
 
233
        size_t idx;
 
234
 
 
235
        if (sl->sl_usage_count == 0)
 
236
                idx = 0;
 
237
        else if (sl->sl_usage_count == 1) {
 
238
                int r;
 
239
 
 
240
                if ((r = (*sl->sl_comp_func)(self, sl->sl_thunk, key, sl->sl_data)) == 0) {
 
241
                        if (sl->sl_free_func)
 
242
                                (*sl->sl_free_func)(self, sl->sl_thunk, data);
 
243
                        return 2;
 
244
                }
 
245
                if (r < 0)
 
246
                        idx = 0;
 
247
                else
 
248
                        idx = 1;
 
249
        }
 
250
        else {
 
251
                if (xt_bsearch(self, key, sl->sl_data, sl->sl_usage_count, sl->sl_item_size, &idx, sl->sl_thunk, sl->sl_comp_func)) {
 
252
                        if (sl->sl_free_func)
 
253
                                (*sl->sl_free_func)(self, sl->sl_thunk, data);
 
254
                        return 2;
 
255
                }
 
256
        }
 
257
        if (sl->sl_usage_count == sl->sl_current_size) {                
 
258
                if (!xt_realloc_ns((void **) &sl->sl_data, (sl->sl_current_size + sl->sl_grow_size) * sl->sl_item_size)) {
 
259
                        if (sl->sl_free_func)
 
260
                                (*sl->sl_free_func)(self, sl->sl_thunk, data);
 
261
                        if (self)
 
262
                                xt_throw(self);
 
263
                        return 0;
 
264
                }
 
265
                sl->sl_current_size = sl->sl_current_size + sl->sl_grow_size;
 
266
        }
 
267
        XT_MEMMOVE(sl->sl_data, &sl->sl_data[(idx+1) * sl->sl_item_size], &sl->sl_data[idx * sl->sl_item_size], (sl->sl_usage_count-idx) * sl->sl_item_size);
 
268
        XT_MEMCPY(sl->sl_data, &sl->sl_data[idx * sl->sl_item_size], data, sl->sl_item_size);
 
269
        sl->sl_usage_count++;
 
270
        return 1;
 
271
}
 
272
 
 
273
xtPublic xtBool xt_sl_insert_item_at(XTThreadPtr self, XTSortedListPtr sl, size_t idx, void *data)
 
274
{
 
275
        ASSERT(idx <= sl->sl_usage_count);
 
276
        if (sl->sl_usage_count == sl->sl_current_size) {                
 
277
                if (!xt_realloc_ns((void **) &sl->sl_data, (sl->sl_current_size + sl->sl_grow_size) * sl->sl_item_size)) {
 
278
                        if (sl->sl_free_func)
 
279
                                (*sl->sl_free_func)(self, sl->sl_thunk, data);
 
280
                        if (self)
 
281
                                xt_throw(self);
 
282
                        return FAILED;
 
283
                }
 
284
                sl->sl_current_size = sl->sl_current_size + sl->sl_grow_size;
 
285
        }
 
286
        XT_MEMMOVE(sl->sl_data, &sl->sl_data[(idx+1) * sl->sl_item_size], &sl->sl_data[idx * sl->sl_item_size], (sl->sl_usage_count-idx) * sl->sl_item_size);
 
287
        XT_MEMCPY(sl->sl_data, &sl->sl_data[idx * sl->sl_item_size], data, sl->sl_item_size);
 
288
        sl->sl_usage_count++;
 
289
        return OK;
 
290
}
 
291
 
 
292
xtPublic xtBool xt_sl_delete(XTThreadPtr self, XTSortedListPtr sl, void *key)
 
293
{
 
294
        void    *result;
 
295
        size_t  idx;
 
296
        
 
297
        if (sl->sl_usage_count == 0)
 
298
                return FALSE;
 
299
        if (sl->sl_usage_count == 1) {
 
300
                if ((*sl->sl_comp_func)(self, sl->sl_thunk, key, sl->sl_data) != 0)
 
301
                        return FALSE;
 
302
                idx = 0;
 
303
                result = sl->sl_data;
 
304
        }
 
305
        else {
 
306
                if (!(result = xt_bsearch(self, key, sl->sl_data, sl->sl_usage_count, sl->sl_item_size, &idx, sl->sl_thunk, sl->sl_comp_func)))
 
307
                        return FALSE;
 
308
        }
 
309
        if (sl->sl_free_func)
 
310
                (*sl->sl_free_func)(self, sl->sl_thunk, result);
 
311
        sl->sl_usage_count--;
 
312
        XT_MEMMOVE(sl->sl_data, &sl->sl_data[idx * sl->sl_item_size], &sl->sl_data[(idx+1) * sl->sl_item_size], (sl->sl_usage_count-idx) * sl->sl_item_size);
 
313
        return TRUE;
 
314
}
 
315
 
 
316
xtPublic void xt_sl_delete_item_at(XTThreadPtr self, XTSortedListPtr sl, size_t idx)
 
317
{
 
318
        void *result;
 
319
 
 
320
        if (idx >= sl->sl_usage_count)
 
321
                return;
 
322
        result = &sl->sl_data[idx * sl->sl_item_size];
 
323
        if (sl->sl_free_func)
 
324
                (*sl->sl_free_func)(self, sl->sl_thunk, result);
 
325
        sl->sl_usage_count--;
 
326
        XT_MEMMOVE(sl->sl_data, &sl->sl_data[idx * sl->sl_item_size], &sl->sl_data[(idx+1) * sl->sl_item_size], (sl->sl_usage_count-idx) * sl->sl_item_size);
 
327
}
 
328
 
 
329
xtPublic void xt_sl_remove_from_front(struct XTThread *XT_UNUSED(self), XTSortedListPtr sl, size_t items)
 
330
{
 
331
        if (sl->sl_usage_count <= items)
 
332
                xt_sl_set_size(sl, 0);
 
333
        else {
 
334
                XT_MEMMOVE(sl->sl_data, sl->sl_data, &sl->sl_data[items * sl->sl_item_size], (sl->sl_usage_count-items) * sl->sl_item_size);
 
335
                sl->sl_usage_count -= items;
 
336
        }
 
337
}
 
338
 
 
339
xtPublic void xt_sl_delete_from_info(XTThreadPtr self, XTSortedListInfoPtr li_undo)
 
340
{       
 
341
        xt_sl_delete(self, li_undo->li_sl, li_undo->li_key);
 
342
}
 
343
 
 
344
xtPublic void xt_sl_set_size(XTSortedListPtr sl, size_t new_size)
 
345
{
 
346
        sl->sl_usage_count = new_size;
 
347
        if (sl->sl_usage_count + sl->sl_grow_size <= sl->sl_current_size) {
 
348
                size_t curr_size;
 
349
 
 
350
                curr_size = sl->sl_usage_count;
 
351
                if (curr_size < sl->sl_grow_size)
 
352
                        curr_size = sl->sl_grow_size;
 
353
 
 
354
                if (xt_realloc(NULL, (void **) &sl->sl_data, curr_size * sl->sl_item_size))
 
355
                        sl->sl_current_size = curr_size;
 
356
        }
 
357
}
 
358
 
 
359
xtPublic void *xt_sl_item_at(XTSortedListPtr sl, size_t idx)
 
360
{
 
361
        if (idx < sl->sl_usage_count)
 
362
                return &sl->sl_data[idx * sl->sl_item_size];
 
363
        return NULL;
 
364
}
 
365
 
 
366
xtPublic void *xt_sl_last_item(XTSortedListPtr sl)
 
367
{
 
368
        if (sl->sl_usage_count > 0)
 
369
                return xt_sl_item_at(sl, sl->sl_usage_count - 1);
 
370
        return NULL;
 
371
}
 
372
 
 
373
xtPublic void *xt_sl_first_item(XTSortedListPtr sl)
 
374
{
 
375
        if (sl->sl_usage_count > 0)
 
376
                return xt_sl_item_at(sl, 0);
 
377
        return NULL;
 
378
}
 
379
 
 
380
xtPublic xtBool xt_sl_lock(XTThreadPtr self, XTSortedListPtr sl)
 
381
{
 
382
        xtBool r = OK;
 
383
        
 
384
        if (sl->sl_locker != self)
 
385
                r = xt_lock_mutex(self, sl->sl_lock);
 
386
        if (r) {
 
387
                sl->sl_locker = self;
 
388
                sl->sl_lock_count++;
 
389
        }
 
390
        return r;
 
391
}
 
392
 
 
393
xtPublic void xt_sl_unlock(XTThreadPtr self, XTSortedListPtr sl)
 
394
{
 
395
        ASSERT(!self || sl->sl_locker == self);
 
396
        ASSERT(sl->sl_lock_count > 0);
 
397
 
 
398
        sl->sl_lock_count--;
 
399
        if (!sl->sl_lock_count) {
 
400
                sl->sl_locker = NULL;
 
401
                xt_unlock_mutex(self, sl->sl_lock);
 
402
        }
 
403
}
 
404
 
 
405
xtPublic void xt_sl_lock_ns(XTSortedListPtr sl, XTThreadPtr thread)
 
406
{
 
407
        if (!thread || sl->sl_locker != thread) {
 
408
                xt_lock_mutex_ns(sl->sl_lock);
 
409
                ASSERT_NS(sl->sl_locker == NULL);
 
410
                sl->sl_locker = thread;
 
411
        }
 
412
        sl->sl_lock_count++;
 
413
}
 
414
 
 
415
xtPublic void xt_sl_unlock_ns(XTSortedListPtr sl)
 
416
{
 
417
        ASSERT_NS(!sl->sl_locker || sl->sl_locker == xt_get_self());
 
418
        ASSERT_NS(sl->sl_lock_count > 0);
 
419
 
 
420
        sl->sl_lock_count--;
 
421
        if (!sl->sl_lock_count) {
 
422
                sl->sl_locker = NULL;
 
423
                xt_unlock_mutex_ns(sl->sl_lock);
 
424
        }
 
425
}
 
426
 
 
427
xtPublic void xt_sl_wait(XTThreadPtr self, XTSortedListPtr sl)
 
428
{
 
429
        xt_wait_cond(self, sl->sl_cond, sl->sl_lock);
 
430
}
 
431
 
 
432
xtPublic xtBool xt_sl_signal(XTThreadPtr self, XTSortedListPtr sl)
 
433
{
 
434
        return xt_signal_cond(self, sl->sl_cond);
 
435
}
 
436
 
 
437
xtPublic void xt_sl_broadcast(XTThreadPtr self, XTSortedListPtr sl)
 
438
{
 
439
        xt_broadcast_cond(self, sl->sl_cond);
 
440
}
 
441
 
 
442
/*
 
443
 * -----------------------------------------------------------------------
 
444
 * Pointer list
 
445
 */
 
446
 
 
447
void XTPointerList::pl_init(XTThreadPtr self)
 
448
{
 
449
        if (!pl_init_ns())
 
450
                xt_throw(self);
 
451
}
 
452
 
 
453
void XTPointerList::pl_exit()
 
454
{
 
455
        xt_clear_sortedlist(&pl_sortedlist);
 
456
}
 
457
 
 
458
static int sl_cmp_ptr(struct XTThread *XT_UNUSED(self), register const void *XT_UNUSED(thunk), register const void *a, register const void *b)
 
459
{
 
460
        void **b_ptr = (void **) b;
 
461
 
 
462
        if (a == *b_ptr)
 
463
                return 0;
 
464
        if (a < *b_ptr)
 
465
                return -1;
 
466
        return 1;
 
467
}
 
468
 
 
469
xtBool XTPointerList::pl_init_ns()
 
470
{
 
471
        return xt_init_sortedlist_ns(&pl_sortedlist, sizeof(void *), 2, 4, sl_cmp_ptr, NULL, NULL, FALSE, FALSE);
 
472
}
 
473
 
 
474
/*
 
475
 * Same as init, but cannot fail because nothing is allocated.
 
476
 */
 
477
void XTPointerList::pl_setup_ns()
 
478
{
 
479
        xt_init_sortedlist_ns(&pl_sortedlist, sizeof(void *), 0, 4, sl_cmp_ptr, NULL, NULL, FALSE, FALSE);
 
480
}
 
481
 
 
482
xtBool XTPointerList::pl_add_pointer(void *ptr)
 
483
{
 
484
        return xt_sl_insert(NULL, &pl_sortedlist, ptr, &ptr);
 
485
}
 
486
 
 
487
/*
 
488
 * Return TRUE of the pointer was on the list.
 
489
 */
 
490
xtBool XTPointerList::pl_remove_pointer(void *ptr)
 
491
{
 
492
        return xt_sl_delete(NULL, &pl_sortedlist, ptr);
 
493
}
 
494
 
 
495
/*
 
496
 * Return NULL if the index is out of range.
 
497
 */
 
498
void *XTPointerList::pl_get_pointer(u_int index)
 
499
{
 
500
        void **p_ptr;
 
501
        
 
502
        if ((p_ptr = (void **) xt_sl_item_at(&pl_sortedlist, index)))
 
503
                return *p_ptr;
 
504
        return NULL;
 
505
}
 
506
 
 
507
void XTPointerList::pl_clear()
 
508
{
 
509
        pl_sortedlist.sl_usage_count = 0;
 
510
}
 
511
 
 
512
u_int XTPointerList::pl_size()
 
513
{
 
514
        return pl_sortedlist.sl_usage_count;
 
515
}
 
516
 
 
517
xtBool XTPointerList::pl_is_empty()
 
518
{
 
519
        return pl_sortedlist.sl_usage_count == 0;
 
520
}
 
521