From 91601deb844848dc02959679fd41e1441a76aff4 Mon Sep 17 00:00:00 2001 From: Aaron Seigo Date: Sun, 14 Dec 2014 12:30:27 +0100 Subject: the all-in-one-file version of unqlite --- common/unqlite/bitvec.c | 222 ------------------------------------------------ 1 file changed, 222 deletions(-) delete mode 100644 common/unqlite/bitvec.c (limited to 'common/unqlite/bitvec.c') diff --git a/common/unqlite/bitvec.c b/common/unqlite/bitvec.c deleted file mode 100644 index 5b78430..0000000 --- a/common/unqlite/bitvec.c +++ /dev/null @@ -1,222 +0,0 @@ -/* - * Symisc unQLite: An Embeddable NoSQL (Post Modern) Database Engine. - * Copyright (C) 2012-2013, Symisc Systems http://unqlite.org/ - * Version 1.1.6 - * For information on licensing, redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES - * please contact Symisc Systems via: - * legal@symisc.net - * licensing@symisc.net - * contact@symisc.net - * or visit: - * http://unqlite.org/licensing.html - */ - /* $SymiscID: bitvec.c v1.0 Win7 2013-02-27 15:16 stable $ */ -#ifndef UNQLITE_AMALGAMATION -#include "unqliteInt.h" -#endif - -/** This file implements an object that represents a dynmaic -** bitmap. -** -** A bitmap is used to record which pages of a database file have been -** journalled during a transaction, or which pages have the "dont-write" -** property. Usually only a few pages are meet either condition. -** So the bitmap is usually sparse and has low cardinality. -*/ -/* - * Actually, this is not a bitmap but a simple hashtable where page - * number (64-bit unsigned integers) are used as the lookup keys. - */ -typedef struct bitvec_rec bitvec_rec; -struct bitvec_rec -{ - pgno iPage; /* Page number */ - bitvec_rec *pNext,*pNextCol; /* Collison link */ -}; -struct Bitvec -{ - SyMemBackend *pAlloc; /* Memory allocator */ - sxu32 nRec; /* Total number of records */ - sxu32 nSize; /* Table size */ - bitvec_rec **apRec; /* Record table */ - bitvec_rec *pList; /* List of records */ -}; -/* - * Allocate a new bitvec instance. -*/ -UNQLITE_PRIVATE Bitvec * unqliteBitvecCreate(SyMemBackend *pAlloc,pgno iSize) -{ - bitvec_rec **apNew; - Bitvec *p; - - p = (Bitvec *)SyMemBackendAlloc(pAlloc,sizeof(*p) ); - if( p == 0 ){ - SXUNUSED(iSize); /* cc warning */ - return 0; - } - /* Zero the structure */ - SyZero(p,sizeof(Bitvec)); - /* Allocate a new table */ - p->nSize = 64; /* Must be a power of two */ - apNew = (bitvec_rec **)SyMemBackendAlloc(pAlloc,p->nSize * sizeof(bitvec_rec *)); - if( apNew == 0 ){ - SyMemBackendFree(pAlloc,p); - return 0; - } - /* Zero the new table */ - SyZero((void *)apNew,p->nSize * sizeof(bitvec_rec *)); - /* Fill-in */ - p->apRec = apNew; - p->pAlloc = pAlloc; - return p; -} -/* - * Check if the given page number is already installed in the table. - * Return true if installed. False otherwise. - */ -UNQLITE_PRIVATE int unqliteBitvecTest(Bitvec *p,pgno i) -{ - bitvec_rec *pRec; - /* Point to the desired bucket */ - pRec = p->apRec[i & (p->nSize - 1)]; - for(;;){ - if( pRec == 0 ){ break; } - if( pRec->iPage == i ){ - /* Page found */ - return 1; - } - /* Point to the next entry */ - pRec = pRec->pNextCol; - - if( pRec == 0 ){ break; } - if( pRec->iPage == i ){ - /* Page found */ - return 1; - } - /* Point to the next entry */ - pRec = pRec->pNextCol; - - - if( pRec == 0 ){ break; } - if( pRec->iPage == i ){ - /* Page found */ - return 1; - } - /* Point to the next entry */ - pRec = pRec->pNextCol; - - - if( pRec == 0 ){ break; } - if( pRec->iPage == i ){ - /* Page found */ - return 1; - } - /* Point to the next entry */ - pRec = pRec->pNextCol; - } - /* No such entry */ - return 0; -} -/* - * Install a given page number in our bitmap (Actually, our hashtable). - */ -UNQLITE_PRIVATE int unqliteBitvecSet(Bitvec *p,pgno i) -{ - bitvec_rec *pRec; - sxi32 iBuck; - /* Allocate a new instance */ - pRec = (bitvec_rec *)SyMemBackendPoolAlloc(p->pAlloc,sizeof(bitvec_rec)); - if( pRec == 0 ){ - return UNQLITE_NOMEM; - } - /* Zero the structure */ - SyZero(pRec,sizeof(bitvec_rec)); - /* Fill-in */ - pRec->iPage = i; - iBuck = i & (p->nSize - 1); - pRec->pNextCol = p->apRec[iBuck]; - p->apRec[iBuck] = pRec; - pRec->pNext = p->pList; - p->pList = pRec; - p->nRec++; - if( p->nRec >= (p->nSize * 3) && p->nRec < 100000 ){ - /* Grow the hashtable */ - sxu32 nNewSize = p->nSize << 1; - bitvec_rec *pEntry,**apNew; - sxu32 n; - apNew = (bitvec_rec **)SyMemBackendAlloc(p->pAlloc, nNewSize * sizeof(bitvec_rec *)); - if( apNew ){ - sxu32 iBucket; - /* Zero the new table */ - SyZero((void *)apNew, nNewSize * sizeof(bitvec_rec *)); - /* Rehash all entries */ - n = 0; - pEntry = p->pList; - for(;;){ - /* Loop one */ - if( n >= p->nRec ){ - break; - } - pEntry->pNextCol = 0; - /* Install in the new bucket */ - iBucket = pEntry->iPage & (nNewSize - 1); - pEntry->pNextCol = apNew[iBucket]; - apNew[iBucket] = pEntry; - /* Point to the next entry */ - pEntry = pEntry->pNext; - n++; - } - /* Release the old table and reflect the change */ - SyMemBackendFree(p->pAlloc,(void *)p->apRec); - p->apRec = apNew; - p->nSize = nNewSize; - } - } - return UNQLITE_OK; -} -/* - * Destroy a bitvec instance. Reclaim all memory used. - */ -UNQLITE_PRIVATE void unqliteBitvecDestroy(Bitvec *p) -{ - bitvec_rec *pNext,*pRec = p->pList; - SyMemBackend *pAlloc = p->pAlloc; - - for(;;){ - if( p->nRec < 1 ){ - break; - } - pNext = pRec->pNext; - SyMemBackendPoolFree(pAlloc,(void *)pRec); - pRec = pNext; - p->nRec--; - - if( p->nRec < 1 ){ - break; - } - pNext = pRec->pNext; - SyMemBackendPoolFree(pAlloc,(void *)pRec); - pRec = pNext; - p->nRec--; - - - if( p->nRec < 1 ){ - break; - } - pNext = pRec->pNext; - SyMemBackendPoolFree(pAlloc,(void *)pRec); - pRec = pNext; - p->nRec--; - - - if( p->nRec < 1 ){ - break; - } - pNext = pRec->pNext; - SyMemBackendPoolFree(pAlloc,(void *)pRec); - pRec = pNext; - p->nRec--; - } - SyMemBackendFree(pAlloc,(void *)p->apRec); - SyMemBackendFree(pAlloc,p); -} -- cgit v1.2.3