← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-10-02 14:17:48 UTC
  • mfrom: (1.1.1 upstream)
  • mto: (2.1.17 sid)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20101002141748-m6vbfbfjhrw1153e
Tags: 2010.09.1802-1
* New upstream release.
* Removed pid-file argument hack.
* Updated GPL-2 address to be new address.
* Directly copy in drizzledump.1 since debian doesn't have sphinx 1.0 yet.
* Link to jquery from libjs-jquery. Add it as a depend.
* Add drizzled.8 symlink to the install files.

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(uint32_t 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
        uint32_t 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
        uint32_t 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
        uint32_t 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 (uint32_t 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 (uint32_t 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
        uint32_t                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
        uint32_t idx;
 
165
 
 
166
        return search(key, idx);
 
167
}
 
168
 
 
169
CSObject *CSSortedList::itemAt(uint32_t idx)
 
170
{
 
171
        if (idx >= iInUse)
 
172
                return NULL;
 
173
        return iList[idx];
 
174
}
 
175
 
 
176
CSObject *CSSortedList::takeItemAt(uint32_t 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
        uint32_t                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, uint32_t& idx)
 
203
{
 
204
        register uint32_t               count = iInUse;
 
205
        register uint32_t               i;
 
206
        register uint32_t               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
        uint32_t 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(uint32_t 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(uint32_t 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(uint32_t idx)
 
389
{
 
390
        if (idx >= iUsage)
 
391
                return NULL;
 
392
        return iArray[idx];
 
393
}
 
394
 
 
395
void CSVector::set(uint32_t 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
                push_(obj);
 
423
                cs_realloc((void **) &iArray, sizeof(CSObject *) * (iMaxSize + iGrowSize));
 
424
                pop_(obj);
 
425
                iMaxSize += iGrowSize;
 
426
        }
 
427
        iArray[iUsage] = obj;
 
428
        iUsage++;
 
429
        exit_();
 
430
}
 
431
 
 
432
/*
 
433
 * ---------------------------------------------------------------
 
434
 * SPARSE ARRAY
 
435
 */
 
436
 
 
437
void CSSparseArray::free()
 
438
{
 
439
        clear();
 
440
        iMaxSize = 0;
 
441
        if (iArray) {
 
442
                cs_free(iArray);
 
443
                iArray = NULL;
 
444
        }
 
445
}
 
446
 
 
447
void CSSparseArray::clear()
 
448
{
 
449
        uint32_t i = iUsage;
 
450
 
 
451
        for (;;) {
 
452
                if (i == 0)
 
453
                        break;
 
454
                i--;
 
455
                if (iArray[i].sa_object) {
 
456
                        CSObject *obj;
 
457
                        
 
458
                        obj = iArray[i].sa_object;
 
459
                        iArray[i].sa_object = NULL;
 
460
                        obj->release();
 
461
                }
 
462
        }
 
463
        iUsage = 0;
 
464
}
 
465
 
 
466
CSObject *CSSparseArray::take(uint32_t idx)
 
467
{
 
468
        uint32_t                pos;
 
469
        CSObject        *obj;
 
470
 
 
471
        if (!(obj = search(idx, pos)))
 
472
                return NULL;
 
473
        iUsage--;
 
474
        memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
475
        return obj;
 
476
}
 
477
 
 
478
void CSSparseArray::remove(uint32_t idx)
 
479
{
 
480
        uint32_t                pos;
 
481
        CSObject        *obj;
 
482
 
 
483
        if (!(obj = search(idx, pos)))
 
484
                return;
 
485
        iUsage--;
 
486
        memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
487
        obj->release();
 
488
}
 
489
 
 
490
CSObject *CSSparseArray::itemAt(uint32_t idx)
 
491
{
 
492
        if (idx >= iUsage)
 
493
                return NULL;
 
494
        return iArray[idx].sa_object;
 
495
}
 
496
 
 
497
CSObject *CSSparseArray::get(uint32_t idx)
 
498
{
 
499
        uint32_t pos;
 
500
 
 
501
        return search(idx, pos);
 
502
}
 
503
 
 
504
uint32_t CSSparseArray::getIndex(uint32_t idx)
 
505
{
 
506
        uint32_t pos;
 
507
 
 
508
        search(idx, pos);
 
509
        return pos;
 
510
}
 
511
 
 
512
void CSSparseArray::set(uint32_t idx, CSObject *val)
 
513
{
 
514
        uint32_t                pos;
 
515
        CSObject        *obj;
 
516
 
 
517
        enter_();
 
518
        push_(val);
 
519
 
 
520
        if ((obj = search(idx, pos)))
 
521
                obj->release();
 
522
        else {
 
523
                if (iUsage == iMaxSize) {
 
524
                        cs_realloc((void **) &iArray, (iMaxSize + iGrowSize) * sizeof(CSSpareArrayItemRec));
 
525
                        iMaxSize += iGrowSize;
 
526
                }
 
527
                memmove(&iArray[pos+1], &iArray[pos], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
 
528
                iUsage++;
 
529
                iArray[pos].sa_index = idx;
 
530
        }
 
531
        pop_(val);
 
532
        iArray[pos].sa_object = val;
 
533
        exit_();
 
534
}
 
535
 
 
536
void CSSparseArray::removeFirst()
 
537
{
 
538
        if (iUsage > 0)
 
539
                remove(iArray[0].sa_index);
 
540
}
 
541
 
 
542
CSObject *CSSparseArray::first()
 
543
{
 
544
        if (iUsage == 0)
 
545
                return NULL;
 
546
        return iArray[0].sa_object;
 
547
}
 
548
 
 
549
CSObject *CSSparseArray::last()
 
550
{
 
551
        if (iUsage == 0)
 
552
                return NULL;
 
553
        return iArray[iUsage-1].sa_object;
 
554
}
 
555
 
 
556
CSObject *CSSparseArray::search(uint32_t idx, uint32_t& pos)
 
557
{
 
558
        register uint32_t       count = iUsage;
 
559
        register uint32_t       i;
 
560
        register uint32_t       guess;
 
561
 
 
562
        i = 0;
 
563
        while (i < count) {
 
564
                guess = (i + count - 1) >> 1;
 
565
                if (idx == iArray[guess].sa_index) {
 
566
                        pos = guess;
 
567
                        return iArray[guess].sa_object;
 
568
                }
 
569
                if (idx < iArray[guess].sa_index)
 
570
                        count = guess;
 
571
                else
 
572
                        i = guess + 1;
 
573
        }
 
574
 
 
575
        pos = i;
 
576
        return NULL;
 
577
}
 
578
 
 
579
/*
 
580
 * ---------------------------------------------------------------
 
581
 * ORDERED LIST
 
582
 */
 
583
 
 
584
void CSOrderedList::clear()
 
585
{
 
586
        if (iList) {
 
587
                for (uint32_t i=0; i<iInUse; i++) {
 
588
                        if (iList[i].li_key)
 
589
                                iList[i].li_key->release();
 
590
                        if (iList[i].li_item)
 
591
                                iList[i].li_item->release();
 
592
                }
 
593
                cs_free(iList);
 
594
                iList = NULL;
 
595
        }
 
596
        iInUse = 0;
 
597
        iListSize = 0;
 
598
}
 
599
 
 
600
CSObject *CSOrderedList::itemAt(uint32_t idx)
 
601
{
 
602
        if (idx >= iInUse)
 
603
                return NULL;
 
604
        return iList[idx].li_item;
 
605
}
 
606
 
 
607
 
 
608
void CSOrderedList::add(CSOrderKey *key, CSObject *item)
 
609
{
 
610
        CSOrderedListItemPtr    old_item;
 
611
        uint32_t                                        idx;
 
612
 
 
613
        enter_();
 
614
        if ((old_item = search(key, &idx))) {
 
615
                iList[idx].li_key = key;
 
616
                iList[idx].li_item = item;
 
617
                if (old_item->li_key)
 
618
                        old_item->li_key->release();
 
619
                if (old_item->li_item)
 
620
                        old_item->li_item->release();
 
621
        }
 
622
        else {
 
623
                if (iInUse == iListSize) {
 
624
                        push_(key);
 
625
                        push_(item);
 
626
                        cs_realloc((void **) &iList, (iListSize + SC_SORT_LIST_INC_SIZE) * sizeof(CSOrderedListItemRec));
 
627
                        pop_(item);
 
628
                        pop_(key);
 
629
                        iListSize += SC_SORT_LIST_INC_SIZE;
 
630
                }
 
631
                memmove(&iList[idx+1], &iList[idx], (iInUse - idx) * sizeof(CSOrderedListItemRec));
 
632
                iInUse++;
 
633
                iList[idx].li_key = key;
 
634
                iList[idx].li_item = item;
 
635
        }
 
636
        exit_();
 
637
}
 
638
 
 
639
CSObject *CSOrderedList::find(CSOrderKey *key)
 
640
{
 
641
        uint32_t                                        idx;
 
642
        CSOrderedListItemPtr    ptr;
 
643
 
 
644
        if ((ptr = search(key, &idx)))
 
645
                return ptr->li_item;
 
646
        return NULL;
 
647
}
 
648
 
 
649
void CSOrderedList::remove(CSOrderKey *key)
 
650
{
 
651
        CSOrderedListItemPtr    item;
 
652
        uint32_t                                        idx;
 
653
 
 
654
        if ((item = search(key, &idx))) {
 
655
                CSOrderedListItemRec ir;
 
656
 
 
657
                memcpy(&ir, item, sizeof(CSOrderedListItemRec));
 
658
                memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSOrderedListItemRec));
 
659
                iInUse--;
 
660
                if (ir.li_key)
 
661
                        ir.li_key->release();
 
662
                if (ir.li_item)
 
663
                        ir.li_item->release();
 
664
        }
 
665
}
 
666
 
 
667
CSOrderedListItemPtr CSOrderedList::search(CSOrderKey *key, uint32_t *idx)
 
668
{
 
669
        register uint32_t               count = iInUse;
 
670
        register uint32_t               i;
 
671
        register uint32_t               guess;
 
672
        register int            r;
 
673
 
 
674
        i = 0;
 
675
        while (i < count) {
 
676
                guess = (i + count - 1) >> 1;
 
677
                r = iList[guess].li_key->compareKey(key);
 
678
                if (r == 0) {
 
679
                        *idx = guess;
 
680
                        return &iList[guess];
 
681
                }
 
682
                if (r < 0)
 
683
                        count = guess;
 
684
                else
 
685
                        i = guess + 1;
 
686
        }
 
687
 
 
688
        *idx = i;
 
689
        return NULL;
 
690
}
 
691
 
 
692