michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2011, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street,
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: #include <cassert>
michael@0: #include "inc/Sparse.h"
michael@0: #include "inc/bits.h"
michael@0: 
michael@0: using namespace graphite2;
michael@0: 
michael@0: sparse::chunk sparse::empty_chunk = {0,0};
michael@0: 
michael@0: sparse::~sparse() throw()
michael@0: {
michael@0:     if (m_array.map == &empty_chunk) return;
michael@0:     free(m_array.values);
michael@0: }
michael@0: 
michael@0: 
michael@0: sparse::mapped_type sparse::operator [] (const key_type k) const throw()
michael@0: {
michael@0:     mapped_type         g = key_type(k/SIZEOF_CHUNK - m_nchunks) >> (sizeof k*8 - 1);
michael@0:     const chunk &       c = m_array.map[g*k/SIZEOF_CHUNK];
michael@0:     const mask_t        m = c.mask >> (SIZEOF_CHUNK - 1 - (k%SIZEOF_CHUNK));
michael@0:     g *= m & 1;
michael@0: 
michael@0:     return g*m_array.values[g*(c.offset + bit_set_count(m >> 1))];
michael@0: }
michael@0: 
michael@0: 
michael@0: size_t sparse::capacity() const throw()
michael@0: {
michael@0:     size_t n = m_nchunks,
michael@0:            s = 0;
michael@0: 
michael@0:     for (const chunk *ci=m_array.map; n; --n, ++ci)
michael@0:         s += bit_set_count(ci->mask);
michael@0: 
michael@0:     return s;
michael@0: }