← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Brian Aker
  • Date: 2011-12-13 03:21:35 UTC
  • mto: This revision was merged to the branch mainline in revision 2475.
  • Revision ID: brian@tangent.org-20111213032135-8dta0336wn38uok9
Rmove PBMS (deprecated)

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