105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* A simple, memory-efficient bitset implementation. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2009-2012 Free Software Foundation, Inc. 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 505436638acc7c010349a69c3395f1a57c642dc62Ying Wang This file is part of Bison, the GNU Compiler Compiler. 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang it under the terms of the GNU General Public License as published by 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is distributed in the hope that it will be useful, 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang but WITHOUT ANY WARRANTY; without even the implied warranty of 1405436638acc7c010349a69c3395f1a57c642dc62Ying Wang MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1505436638acc7c010349a69c3395f1a57c642dc62Ying Wang GNU General Public License for more details. 1605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang You should have received a copy of the GNU General Public License 1805436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <config.h> 2105436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "system.h" 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "Sbitset.h" 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2505436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset 2605436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset__new (Sbitset__Index nbits) 2705436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 2805436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Some functions, like Sbitset__last_byte_mask, will fail if nbits = 0. */ 2905436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (nbits); 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang return xcalloc (1, Sbitset__nbytes (nbits)); 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3305436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset 3405436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset__new_on_obstack (Sbitset__Index nbits, struct obstack *obstackp) 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset result; 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset ptr; 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset end; 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (nbits); 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang result = obstack_alloc (obstackp, Sbitset__nbytes (nbits)); 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (ptr = result, end = result + Sbitset__nbytes (nbits); ptr < end; ++ptr) 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang *ptr = 0; 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang return result; 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 4705436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset__delete (Sbitset self) 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wang free (self); 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wangbool 5305436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset__isEmpty (Sbitset self, Sbitset__Index nbits) 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset last = self + Sbitset__nbytes (nbits) - 1; 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (; self < last; ++self) 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (*self != 0) 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang return false; 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang return ((*last) & Sbitset__last_byte_mask (nbits)) == 0; 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid 6305436638acc7c010349a69c3395f1a57c642dc62Ying WangSbitset__fprint(Sbitset self, Sbitset__Index nbits, FILE *file) 6405436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 6505436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset__Index i; 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang Sbitset itr; 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool first = true; 6805436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (file, 6905436638acc7c010349a69c3395f1a57c642dc62Ying Wang "nbits = %" SBITSET__INDEX__CONVERSION_SPEC ", set = {", 7005436638acc7c010349a69c3395f1a57c642dc62Ying Wang nbits); 7105436638acc7c010349a69c3395f1a57c642dc62Ying Wang SBITSET__FOR_EACH (self, nbits, itr, i) 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (first) 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wang first = false; 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (file, ","); 7705436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (file, " %" SBITSET__INDEX__CONVERSION_SPEC, i); 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wang fprintf (file, " }"); 8005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 81