← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/pbms/src/cslib/CSStorage.cc

Added the PBMS daemon plugin.

(Augen zu und durch!)

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/pbms/src/cslib/CSStorage.cc
 
1
/* Copyright (c) 2008 PrimeBase Technologies GmbH, Germany
 
2
 *
 
3
 * PrimeBase Media Stream for MySQL
 
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
 * Original author: Paul McCullagh (H&G2JCtL)
 
20
 * Continued development: Barry Leslie
 
21
 *
 
22
 * 2007-06-15
 
23
 *
 
24
 * CORE SYSTEM STORAGE
 
25
 * Basic storage structures.
 
26
 *
 
27
 */
 
28
 
 
29
#include "CSConfig.h"
 
30
 
 
31
#include <assert.h>
 
32
#include <string.h>
 
33
 
 
34
#include "CSMemory.h"
 
35
#include "CSUTF8.h"
 
36
#include "CSStorage.h"
 
37
#include "CSGlobal.h"
 
38
 
 
39
/*
 
40
 * ---------------------------------------------------------------
 
41
 * HASH TABLE
 
42
 */
 
43
 
 
44
CSHashTable::~CSHashTable()
 
45
{
 
46
        clear();
 
47
        iSize = 0;
 
48
        if (iTable) {
 
49
                cs_free(iTable);
 
50
                iTable = NULL;
 
51
        }
 
52
 
 
53
}
 
54
 
 
55
void CSHashTable::setSize(u_int size)
 
56
{
 
57
        enter_();
 
58
        cs_realloc((void **) &iTable, sizeof(CSObject *) * size);
 
59
        iSize = size;
 
60
        exit_();
 
61
}
 
62
 
 
63
void CSHashTable::add(CSObject *item)
 
64
{
 
65
        u_int h = item->hashKey();
 
66
 
 
67
        remove(item->getKey());
 
68
        item->setHashLink(iTable[h % iSize]);
 
69
        iTable[h % iSize] = item;
 
70
}
 
71
 
 
72
CSObject *CSHashTable::find(CSObject *key)
 
73
{
 
74
        u_int h = key->hashKey();
 
75
        CSObject *item;
 
76
        
 
77
        item = iTable[h % iSize];
 
78
        while (item) {
 
79
                if (item->hashKey() == h && item->compareKey(key) == 0)
 
80
                        return item;
 
81
                item = item->getHashLink();
 
82
        }
 
83
        return NULL;
 
84
}
 
85
 
 
86
void CSHashTable::remove(CSObject *key)
 
87
{
 
88
        u_int h = key->hashKey();
 
89
        CSObject *item, *prev_item;
 
90
 
 
91
        prev_item = NULL;
 
92
        item = iTable[h % iSize];
 
93
        while (item) {
 
94
                if (item->hashKey() == h &&  item->compareKey(key) == 0) {
 
95
                        /* Remove the object: */
 
96
                        if (prev_item)
 
97
                                prev_item->setHashLink(item->getHashLink());
 
98
                        else
 
99
                                iTable[h % iSize] = item->getHashLink();
 
100
                        item->release();
 
101
                        break;
 
102
                }
 
103
                prev_item = item;
 
104
                item = item->getHashLink();
 
105
        }
 
106
}
 
107
 
 
108
void CSHashTable::clear()
 
109
{
 
110
        CSObject *item, *tmp_item;
 
111
 
 
112
        for (u_int i=0; i<iSize; i++) {
 
113
                item = iTable[i];
 
114
                while ((tmp_item = item)) {
 
115
                        item = tmp_item->getHashLink();
 
116
                        tmp_item->release();
 
117
                }
 
118
        }
 
119
}
 
120
 
 
121
/*
 
122
 * ---------------------------------------------------------------
 
123
 * SORTED LIST
 
124
 */
 
125
 
 
126
void CSSortedList::clear()
 
127
{
 
128
        if (iList) {
 
129
                for (u_int i=0; i<iInUse; i++)
 
130
                        iList[i]->release();
 
131
                cs_free(iList);
 
132
                iList = NULL;
 
133
        }
 
134
        iInUse = 0;
 
135
        iListSize = 0;
 
136
}
 
137
 
 
138
void CSSortedList::add(CSObject *item)
 
139
{
 
140
        CSObject        *old_item;
 
141
        u_int           idx;
 
142
 
 
143
        enter_();
 
144
        if ((old_item = search(item->getKey(), idx))) {
 
145
                iList[idx] = item;
 
146
                old_item->release();
 
147
        }
 
148
        else {
 
149
                if (iInUse == iListSize) {
 
150
                        push_(item);
 
151
                        cs_realloc((void **) &iList, (iListSize + SC_SORT_LIST_INC_SIZE) * sizeof(CSObject *));
 
152
                        pop_(item);
 
153
                        iListSize += SC_SORT_LIST_INC_SIZE;
 
154
                }
 
155
                memmove(&iList[idx+1], &iList[idx], (iInUse - idx) * sizeof(CSObject *));
 
156
                iInUse++;
 
157
                iList[idx] = item;
 
158
        }
 
159
        exit_();
 
160
}
 
161
 
 
162
CSObject *CSSortedList::find(CSObject *key)
 
163
{
 
164
        u_int idx;
 
165
 
 
166
        return search(key, idx);
 
167
}
 
168
 
 
169
CSObject *CSSortedList::itemAt(u_int idx)
 
170
{
 
171
        if (idx >= iInUse)
 
172
                return NULL;
 
173
        return iList[idx];
 
174
}
 
175
 
 
176
CSObject *CSSortedList::takeItemAt(u_int idx)
 
177
{
 
178
        CSObject        *item;
 
179
 
 
180
        if (idx >= iInUse)
 
181
                return NULL;
 
182
                
 
183
        item =  iList[idx];
 
184
        
 
185
        memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSObject *));
 
186
        iInUse--;
 
187
        return item;
 
188
}
 
189
 
 
190
void CSSortedList::remove(CSObject *key)
 
191
{
 
192
        CSObject        *item;
 
193
        u_int           idx;
 
194
 
 
195
        if ((item = search(key, idx))) {
 
196
                memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSObject *));
 
197
                iInUse--;
 
198
                item->release();
 
199
        }
 
200
}
 
201
 
 
202
CSObject *CSSortedList::search(CSObject *key, u_int& idx)
 
203
{
 
204
        register u_int          count = iInUse;
 
205
        register u_int          i;
 
206
        register u_int          guess;
 
207
        register int            r;
 
208
 
 
209
        i = 0;
 
210
        while (i < count) {
 
211
                guess = (i + count - 1) >> 1;
 
212
                r = iList[guess]->compareKey(key);
 
213
                if (r == 0) {
 
214
                        idx = guess;
 
215
                        return iList[guess];
 
216
                }
 
217
                if (r < 0)
 
218
                        count = guess;
 
219
                else
 
220
                        i = guess + 1;
 
221
        }
 
222
 
 
223
        idx = i;
 
224
        return NULL;
 
225
}
 
226
 
 
227
/*
 
228
 * ---------------------------------------------------------------
 
229
 * LINK ITEM
 
230
 */
 
231
 
 
232
/*
 
233
 * ---------------------------------------------------------------
 
234
 * LINK LIST
 
235
 */
 
236
 
 
237
void CSLinkedList::clear()
 
238
{
 
239
        while (iListFront)
 
240
                remove(iListFront);
 
241
}
 
242
 
 
243
void CSLinkedList::addFront(CSObject *item)
 
244
{
 
245
        if (iListFront != item) {
 
246
                remove(item);
 
247
                item->setNextLink(NULL);
 
248
                item->setPrevLink(iListFront);
 
249
                if (iListFront)
 
250
                        iListFront->setNextLink(item);
 
251
                else
 
252
                        iListBack = item;
 
253
                iListFront = item;
 
254
                iSize++;
 
255
        }
 
256
        else
 
257
                /* Must do this or I will have one reference too
 
258
                 * many!
 
259
                 * The input object was given to me referenced,
 
260
                 * but I already have the object on my list, and
 
261
                 * referenced!
 
262
                 */
 
263
                item->release();
 
264
}
 
265
 
 
266
bool CSLinkedList::remove(CSObject *item)
 
267
{
 
268
        bool on_list = false;
 
269
 
 
270
        if (item->getNextLink()) {
 
271
                item->getNextLink()->setPrevLink(item->getPrevLink());
 
272
                on_list = true;
 
273
        }
 
274
        if (item->getPrevLink()) {
 
275
                item->getPrevLink()->setNextLink(item->getNextLink());
 
276
                on_list = true;
 
277
        }
 
278
        if (iListFront == item) {
 
279
                iListFront = item->getPrevLink();
 
280
                on_list = true;
 
281
        }
 
282
        if (iListBack == item) {
 
283
                iListBack = item->getNextLink();
 
284
                on_list = true;
 
285
        }
 
286
        item->setNextLink(NULL);
 
287
        item->setPrevLink(NULL);
 
288
        if (on_list) {
 
289
                item->release();
 
290
                iSize--;
 
291
                return true;
 
292
        }
 
293
        return false;
 
294
}
 
295
 
 
296
CSObject *CSLinkedList::removeBack()
 
297
{
 
298
        CSObject *item = iListBack;
 
299
        
 
300
        if (item) {
 
301
                /* Removing dereferences the object! */
 
302
                remove(RETAIN(item));
 
303
        }
 
304
        return item;
 
305
}
 
306
 
 
307
CSObject *CSLinkedList::getBack()
 
308
{
 
309
        return iListBack;
 
310
}
 
311
 
 
312
CSObject *CSLinkedList::removeFront()
 
313
{
 
314
        CSObject *item = iListFront;
 
315
        
 
316
        if (item) {
 
317
                /* Removing dereferences the object! */
 
318
                remove(RETAIN(item));
 
319
        }
 
320
        return item;
 
321
}
 
322
 
 
323
CSObject *CSLinkedList::getFront()
 
324
{
 
325
        return iListFront;
 
326
}
 
327
 
 
328
/*
 
329
 * ---------------------------------------------------------------
 
330
 * VECTOR
 
331
 */
 
332
 
 
333
void CSVector::free()
 
334
{
 
335
        clear();
 
336
        iMaxSize = 0;
 
337
        if (iArray) {
 
338
                cs_free(iArray);
 
339
                iArray = NULL;
 
340
        }
 
341
}
 
342
 
 
343
void CSVector::clear()
 
344
{
 
345
        u_int i = iUsage;
 
346
 
 
347
        for (;;) {
 
348
                if (i == 0)
 
349
                        break;
 
350
                i--;
 
351
                if (iArray[i]) {
 
352
                        CSObject *obj;
 
353
                        
 
354
                        obj = iArray[i];
 
355
                        iArray[i] = NULL;
 
356
                        obj->release();
 
357
                }
 
358
        }
 
359
        iUsage = 0;
 
360
}
 
361
 
 
362
CSObject *CSVector::take(u_int idx)
 
363
{
 
364
        CSObject *obj;
 
365
 
 
366
        if (idx >= iUsage)
 
367
                return NULL;
 
368
 
 
369
        obj = iArray[idx];
 
370
        iUsage--;
 
371
        memmove(&iArray[idx], &iArray[idx+1], (iUsage - idx) * sizeof(CSObject *));
 
372
        return obj;
 
373
}
 
374
 
 
375
void CSVector::remove(u_int idx)
 
376
{
 
377
        CSObject *obj;
 
378
 
 
379
        if (idx >= iUsage)
 
380
                return;
 
381
 
 
382
        obj = iArray[idx];
 
383
        iUsage--;
 
384
        memmove(&iArray[idx], &iArray[idx+1], (iUsage - idx) * sizeof(CSObject *));
 
385
        obj->release();
 
386
}
 
387
 
 
388
CSObject *CSVector::get(u_int idx)
 
389
{
 
390
        if (idx >= iUsage)
 
391
                return NULL;
 
392
        return iArray[idx];
 
393
}
 
394
 
 
395
void CSVector::set(u_int idx, CSObject *val)
 
396
{
 
397
        enter_();
 
398
        if (idx >= iMaxSize) {
 
399
                push_(val);
 
400
                cs_realloc((void **) &iArray, sizeof(CSObject *) * (idx + iGrowSize - 1));
 
401
                pop_(val);
 
402
                iMaxSize = idx + iGrowSize - 1;
 
403
        }
 
404
        if (idx >= iUsage) {
 
405
                if (idx > iUsage)
 
406
                        memset(&iArray[iUsage], 0, sizeof(CSObject *) * (idx - iUsage));
 
407
                iUsage = idx + 1;
 
408
        }
 
409
        else if (iArray[idx]) {
 
410
                push_(val);
 
411
                iArray[idx]->release();
 
412
                pop_(val);
 
413
        }
 
414
        iArray[idx] = val;
 
415
        exit_();
 
416
}
 
417
 
 
418
void CSVector::add(CSObject *obj)
 
419
{
 
420
        enter_();
 
421
        if (iUsage == iMaxSize) {
 
422
                try_(a) {
 
423
                        cs_realloc((void **) &iArray, sizeof(CSObject *) * (iMaxSize + iGrowSize));
 
424
                }
 
425
                catch_(a) {
 
426
                        obj->release();
 
427
                        throw_();
 
428
                }
 
429
                cont_(a);
 
430
                iMaxSize += iGrowSize;
 
431
        }
 
432
        iArray[iUsage] = obj;
 
433
        iUsage++;
 
434
        exit_();
 
435
}
 
436
 
 
437
/*
 
438
 * ---------------------------------------------------------------
 
439
 * SPARSE ARRAY
 
440
 */
 
441
 
 
442
void CSSparseArray::free()
 
443
{
 
444
        clear();
 
445
        iMaxSize = 0;
 
446
        if (iArray) {
 
447
                cs_free(iArray);
 
448
                iArray = NULL;
 
449
        }
 
450
}
 
451
 
 
452
void CSSparseArray::clear()
 
453
{
 
454
        u_int i = iUsage;
 
455
 
 
456
        for (;;) {
 
457
                if (i == 0)
 
458
                        break;
 
459
                i--;
 
460
                if (iArray[i].sa_object) {
 
461
                        CSObject *obj;
 
462
                        
 
463
                        obj = iArray[i].sa_object;
 
464
                        iArray[i].sa_object = NULL;
 
465
                        obj->release();
 
466
                }
 
467
        }
 
468
        iUsage = 0;
 
469
}
 
470
 
 
471
CSObject *CSSparseArray::take(u_int idx)
 
472
{
 
473
        u_int           pos;
 
474
        CSObject        *obj;
 
475
 
 
476
        if (!(obj = search(idx, pos)))
 
477
                return NULL;
 
478
        iUsage--;
 
479
        memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
480
        return obj;
 
481
}
 
482
 
 
483
void CSSparseArray::remove(u_int idx)
 
484
{
 
485
        u_int           pos;
 
486
        CSObject        *obj;
 
487
 
 
488
        if (!(obj = search(idx, pos)))
 
489
                return;
 
490
        iUsage--;
 
491
        memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
492
        obj->release();
 
493
}
 
494
 
 
495
CSObject *CSSparseArray::itemAt(u_int idx)
 
496
{
 
497
        if (idx >= iUsage)
 
498
                return NULL;
 
499
        return iArray[idx].sa_object;
 
500
}
 
501
 
 
502
CSObject *CSSparseArray::get(u_int idx)
 
503
{
 
504
        u_int pos;
 
505
 
 
506
        return search(idx, pos);
 
507
}
 
508
 
 
509
u_int CSSparseArray::getIndex(u_int idx)
 
510
{
 
511
        u_int pos;
 
512
 
 
513
        search(idx, pos);
 
514
        return pos;
 
515
}
 
516
 
 
517
void CSSparseArray::set(u_int idx, CSObject *val)
 
518
{
 
519
        u_int           pos;
 
520
        CSObject        *obj;
 
521
 
 
522
        enter_();
 
523
        push_(val);
 
524
 
 
525
        if ((obj = search(idx, pos)))
 
526
                obj->release();
 
527
        else {
 
528
                if (iUsage == iMaxSize) {
 
529
                        cs_realloc((void **) &iArray, (iMaxSize + iGrowSize) * sizeof(CSSpareArrayItemRec));
 
530
                        iMaxSize += iGrowSize;
 
531
                }
 
532
                memmove(&iArray[pos+1], &iArray[pos], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
533
                iUsage++;
 
534
                iArray[pos].sa_index = idx;
 
535
        }
 
536
        pop_(val);
 
537
        iArray[pos].sa_object = val;
 
538
        exit_();
 
539
}
 
540
 
 
541
void CSSparseArray::removeFirst()
 
542
{
 
543
        if (iUsage > 0)
 
544
                remove(iArray[0].sa_index);
 
545
}
 
546
 
 
547
CSObject *CSSparseArray::first()
 
548
{
 
549
        if (iUsage == 0)
 
550
                return NULL;
 
551
        return iArray[0].sa_object;
 
552
}
 
553
 
 
554
CSObject *CSSparseArray::last()
 
555
{
 
556
        if (iUsage == 0)
 
557
                return NULL;
 
558
        return iArray[iUsage-1].sa_object;
 
559
}
 
560
 
 
561
CSObject *CSSparseArray::search(u_int idx, u_int& pos)
 
562
{
 
563
        register u_int  count = iUsage;
 
564
        register u_int  i;
 
565
        register u_int  guess;
 
566
 
 
567
        i = 0;
 
568
        while (i < count) {
 
569
                guess = (i + count - 1) >> 1;
 
570
                if (idx == iArray[guess].sa_index) {
 
571
                        pos = guess;
 
572
                        return iArray[guess].sa_object;
 
573
                }
 
574
                if (idx < iArray[guess].sa_index)
 
575
                        count = guess;
 
576
                else
 
577
                        i = guess + 1;
 
578
        }
 
579
 
 
580
        pos = i;
 
581
        return NULL;
 
582
}
 
583
 
 
584
/*
 
585
 * ---------------------------------------------------------------
 
586
 * ORDERED LIST
 
587
 */
 
588
 
 
589
void CSOrderedList::clear()
 
590
{
 
591
        if (iList) {
 
592
                for (u_int i=0; i<iInUse; i++) {
 
593
                        if (iList[i].li_key)
 
594
                                iList[i].li_key->release();
 
595
                        if (iList[i].li_item)
 
596
                                iList[i].li_item->release();
 
597
                }
 
598
                cs_free(iList);
 
599
                iList = NULL;
 
600
        }
 
601
        iInUse = 0;
 
602
        iListSize = 0;
 
603
}
 
604
 
 
605
CSObject *CSOrderedList::itemAt(u_int idx)
 
606
{
 
607
        if (idx >= iInUse)
 
608
                return NULL;
 
609
        return iList[idx].li_item;
 
610
}
 
611
 
 
612
 
 
613
void CSOrderedList::add(CSOrderKey *key, CSObject *item)
 
614
{
 
615
        CSOrderedListItemPtr    old_item;
 
616
        u_int                                   idx;
 
617
 
 
618
        enter_();
 
619
        if ((old_item = search(key, &idx))) {
 
620
                iList[idx].li_key = key;
 
621
                iList[idx].li_item = item;
 
622
                if (old_item->li_key)
 
623
                        old_item->li_key->release();
 
624
                if (old_item->li_item)
 
625
                        old_item->li_item->release();
 
626
        }
 
627
        else {
 
628
                if (iInUse == iListSize) {
 
629
                        push_(key);
 
630
                        push_(item);
 
631
                        cs_realloc((void **) &iList, (iListSize + SC_SORT_LIST_INC_SIZE) * sizeof(CSOrderedListItemRec));
 
632
                        pop_(item);
 
633
                        pop_(key);
 
634
                        iListSize += SC_SORT_LIST_INC_SIZE;
 
635
                }
 
636
                memmove(&iList[idx+1], &iList[idx], (iInUse - idx) * sizeof(CSOrderedListItemRec));
 
637
                iInUse++;
 
638
                iList[idx].li_key = key;
 
639
                iList[idx].li_item = item;
 
640
        }
 
641
        exit_();
 
642
}
 
643
 
 
644
CSObject *CSOrderedList::find(CSOrderKey *key)
 
645
{
 
646
        u_int                                   idx;
 
647
        CSOrderedListItemPtr    ptr;
 
648
 
 
649
        if ((ptr = search(key, &idx)))
 
650
                return ptr->li_item;
 
651
        return NULL;
 
652
}
 
653
 
 
654
void CSOrderedList::remove(CSOrderKey *key)
 
655
{
 
656
        CSOrderedListItemPtr    item;
 
657
        u_int                                   idx;
 
658
 
 
659
        if ((item = search(key, &idx))) {
 
660
                CSOrderedListItemRec ir;
 
661
 
 
662
                memcpy(&ir, item, sizeof(CSOrderedListItemRec));
 
663
                memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSOrderedListItemRec));
 
664
                iInUse--;
 
665
                if (ir.li_key)
 
666
                        ir.li_key->release();
 
667
                if (ir.li_item)
 
668
                        ir.li_item->release();
 
669
        }
 
670
}
 
671
 
 
672
CSOrderedListItemPtr CSOrderedList::search(CSOrderKey *key, u_int *idx)
 
673
{
 
674
        register u_int          count = iInUse;
 
675
        register u_int          i;
 
676
        register u_int          guess;
 
677
        register int            r;
 
678
 
 
679
        i = 0;
 
680
        while (i < count) {
 
681
                guess = (i + count - 1) >> 1;
 
682
                r = iList[guess].li_key->compareKey(key);
 
683
                if (r == 0) {
 
684
                        *idx = guess;
 
685
                        return &iList[guess];
 
686
                }
 
687
                if (r < 0)
 
688
                        count = guess;
 
689
                else
 
690
                        i = guess + 1;
 
691
        }
 
692
 
 
693
        *idx = i;
 
694
        return NULL;
 
695
}
 
696
 
 
697