libs/uniquenames.h

   1 /*
   2    Copyright (C) 2001-2006, William Joseph.
   3    All Rights Reserved.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22 #if !defined( INCLUDED_UNIQUENAMES_H )
  23 #define INCLUDED_UNIQUENAMES_H
  24
  25 #include "debugging/debugging.h"
  26 #include <map>
  27 #include "string/string.h"
  28 #include "generic/static.h"
  29
  30 #if 1
  31 class Postfix
  32 {
  33 unsigned int m_value;
  34 public:
  35 Postfix( const char* postfix ) : m_value( atoi( postfix ) ){
  36 }
  37 unsigned int number() const {
  38         return m_value;
  39 }
  40 void write( char* buffer ) const {
  41         sprintf( buffer, "%u", m_value );
  42 }
  43 Postfix& operator++(){
  44         ++m_value;
  45         return *this;
  46 }
  47 bool operator<( const Postfix& other ) const {
  48         return m_value < other.m_value;
  49 }
  50 bool operator==( const Postfix& other ) const {
  51         return m_value == other.m_value;
  52 }
  53 bool operator!=( const Postfix& other ) const {
  54         return !operator==( other );
  55 }
  56 };
  57
  58 #else
  59 class Postfix
  60 {
  61 std::pair<unsigned int, unsigned int> m_value;
  62 public:
  63 Postfix( unsigned int number, unsigned int leading_zeros )
  64         : m_value( leading_zeros, number ){
  65 }
  66 Postfix( const char* postfix )
  67         : m_value( number_count_leading_zeros( postfix ), atoi( postfix ) ){
  68 }
  69 unsigned int number() const {
  70         return m_value.second;
  71 }
  72 unsigned int leading_zeros() const {
  73         return m_value.first;
  74 }
  75 void write( char* buffer ){
  76         for ( unsigned int count = 0; count < m_value.first; ++count, ++buffer )
  77                 *buffer = '0';
  78         sprintf( buffer, "%u", m_value.second );
  79 }
  80 Postfix& operator++(){
  81         ++m_value.second;
  82         if ( m_value.first != 0 && m_value.second % 10 == 0 ) {
  83                 --m_value.first;
  84         }
  85         return *this;
  86 }
  87 bool operator<( const Postfix& other ) const {
  88         return m_value < other.m_value;
  89 }
  90 bool operator==( const Postfix& other ) const {
  91         return m_value == other.m_value;
  92 }
  93 bool operator!=( const Postfix& other ) const {
  94         return !operator==( other );
  95 }
  96 };
  97
  98 #endif
  99
 100 typedef std::pair<CopiedString, Postfix> name_t;
 101
 102 inline void name_write( char* buffer, name_t name ){
 103         strcpy( buffer, name.first.c_str() );
 104         name.second.write( buffer + strlen( name.first.c_str() ) );
 105 }
 106
 107 inline name_t name_read( const char* name ){
 108         const char* end = name + strlen( name );
 109
 110 #if GDEF_OS_MACOS
 111         /* HACK: Apple shipped a clang built for macOS with an optimization enabled
 112         that is not available on macOS. This compiler error may then be faced:
 113
 114           ld: Undefined symbols:
 115             _memrchr, referenced from:
 116                 name_read(char const*) in map.cpp.o
 117
 118         This is a compiler error:
 119
 120         > On Mac OSX (macOS version 12.4, sdk version 12.1) llvm can replace call
 121         > to strrchr() with call to memrchr() when string length is known at
 122         > compile time. This results in link error, because memrchr is not present
 123         > in libSystem.
 124         > -- https://github.com/llvm/llvm-project/issues/62254
 125
 126         We workaround this by making the string length not known at build time
 127         on macOS to avoid triggering the unavailable compiler optimization. */
 128
 129         const char* volatile numbers = "1234567890";
 130 #else
 131         const char* numbers = "1234567890";
 132 #endif
 133
 134         for ( const char* p = end; end != name; --p )
 135         {
 136                 if ( strrchr( numbers, *p ) == NULL ) {
 137                         break;
 138                 }
 139                 end = p;
 140         }
 141
 142         return name_t( CopiedString( StringRange( name, end ) ), Postfix( end ) );
 143 }
 144
 145
 146 class PostFixes
 147 {
 148 public:
 149 typedef std::map<Postfix, unsigned int> postfixes_t;
 150 postfixes_t m_postfixes;
 151
 152 private:
 153 Postfix find_first_empty() const {
 154         Postfix postfix( "1" );
 155         for ( postfixes_t::const_iterator i = m_postfixes.find( postfix ); i != m_postfixes.end(); ++i, ++postfix )
 156         {
 157                 if ( ( *i ).first != postfix ) {
 158                         break;
 159                 }
 160         }
 161         return postfix;
 162 }
 163
 164 public:
 165 Postfix make_unique( Postfix postfix ) const {
 166         postfixes_t::const_iterator i = m_postfixes.find( postfix );
 167         if ( i == m_postfixes.end() ) {
 168                 return postfix;
 169         }
 170         else
 171         {
 172                 return find_first_empty();
 173         }
 174 }
 175
 176 void insert( Postfix postfix ){
 177         postfixes_t::iterator i = m_postfixes.find( postfix );
 178         if ( i == m_postfixes.end() ) {
 179                 m_postfixes.insert( postfixes_t::value_type( postfix, 1 ) );
 180         }
 181         else
 182         {
 183                 ++( *i ).second;
 184         }
 185 }
 186
 187 void erase( Postfix postfix ){
 188         postfixes_t::iterator i = m_postfixes.find( postfix );
 189         if ( i == m_postfixes.end() ) {
 190                 // error
 191         }
 192         else
 193         {
 194                 if ( --( *i ).second == 0 ) {
 195                         m_postfixes.erase( i );
 196                 }
 197         }
 198 }
 199
 200 bool empty() const {
 201         return m_postfixes.empty();
 202 }
 203 };
 204
 205
 206 class UniqueNames
 207 {
 208 typedef std::map<CopiedString, PostFixes> names_t;
 209 names_t m_names;
 210 public:
 211 name_t make_unique( const name_t& name ) const {
 212         char buf[80];
 213         name_t r( "","" );
 214         name_write( buf, name );
 215         #ifdef _DEBUG
 216         globalErrorStream() << "find unique name for " << buf << "\n";
 217         globalErrorStream() << "> currently registered names:\n";
 218         #endif
 219         for ( names_t::const_iterator i = m_names.begin(); i != m_names.end(); ++i )
 220         {
 221                 #ifdef _DEBUG
 222                 globalErrorStream() << ">> " << i->first.c_str() << ": ";
 223                 #endif
 224                 for ( PostFixes::postfixes_t::const_iterator j = i->second.m_postfixes.begin(); j != i->second.m_postfixes.end(); ++j )
 225                 {
 226                         j->first.write( buf );
 227                         #ifdef _DEBUG
 228                         globalErrorStream() << " '" << buf << "'";
 229                         #endif
 230                 }
 231                 #ifdef _DEBUG
 232                 globalErrorStream() << "\n";
 233                 #endif
 234         }
 235         names_t::const_iterator i = m_names.find( name.first );
 236         if ( i == m_names.end() ) {
 237                 r = name;
 238         }
 239         else
 240         {
 241                 r = name_t( name.first, ( *i ).second.make_unique( name.second ) );
 242         }
 243         name_write( buf, r );
 244         #ifdef _DEBUG
 245         globalErrorStream() << "> unique name is " << buf << "\n";
 246         #endif
 247         return r;
 248 }
 249
 250 void insert( const name_t& name ){
 251         m_names[name.first].insert( name.second );
 252 }
 253
 254 void erase( const name_t& name ){
 255         names_t::iterator i = m_names.find( name.first );
 256         if ( i == m_names.end() ) {
 257                 ASSERT_MESSAGE( true, "erase: name not found" );
 258         }
 259         else
 260         {
 261                 ( *i ).second.erase( name.second );
 262                 if ( ( *i ).second.empty() ) {
 263                         m_names.erase( i );
 264                 }
 265         }
 266 }
 267
 268 bool empty() const {
 269         return m_names.empty();
 270 }
 271 };
 272
 273
 274
 275 #if 0
 276
 277 #undef ERROR_MESSAGE
 278 #define ERROR_MESSAGE( message )
 279
 280 class TestUniqueName
 281 {
 282 void name_check_equal( const name_t& name, const char* string, unsigned int postfix ){
 283         ASSERT_MESSAGE( strcmp( name.first.c_str(), string ) == 0
 284                                         && name.second.number() == postfix,
 285                                         "test failed!" );
 286 }
 287 void test_refcount(){
 288         Names names;
 289
 290         names.insert( name_t( "func_bleh_", "100" ) );
 291         names.insert( name_t( "func_bleh_", "100" ) );
 292         names.insert( name_t( "func_bleh_", "100" ) );
 293
 294
 295         names.erase( name_t( "func_bleh_", "100" ) );
 296         names.erase( name_t( "func_bleh_", "100" ) );
 297         names.erase( name_t( "func_bleh_", "100" ) );
 298
 299         ASSERT_MESSAGE( names.empty(), "test failed!" );
 300 }
 301
 302 void test_make_unique(){
 303         Names names;
 304
 305         {
 306                 name_t name( names.make_unique( name_t( "func_bleh_", "01" ) ) );
 307                 name_check_equal( name, "func_bleh_", 1 );
 308                 names.insert( name );
 309         }
 310         {
 311                 name_t name( names.make_unique( name_t( "func_bleh_", "04" ) ) );
 312                 name_check_equal( name, "func_bleh_", 4 );
 313                 names.insert( name );
 314         }
 315         {
 316                 name_t name( names.make_unique( name_t( "func_bleh_", "04" ) ) );
 317                 name_check_equal( name, "func_bleh_", 2 );
 318                 names.insert( name );
 319         }
 320         {
 321                 name_t name( names.make_unique( name_t( "func_bleh_", "1" ) ) );
 322                 name_check_equal( name, "func_bleh_", 3 );
 323                 names.insert( name );
 324         }
 325         {
 326                 name_t name( names.make_unique( name_t( "func_bleh_", "2" ) ) );
 327                 name_check_equal( name, "func_bleh_", 5 );
 328                 names.insert( name );
 329         }
 330         {
 331                 name_t name( names.make_unique( name_t( "func_bleh_", "3" ) ) );
 332                 name_check_equal( name, "func_bleh_", 6 );
 333                 names.insert( name );
 334         }
 335
 336         names.erase( name_t( "func_bleh_", "1" ) );
 337         names.erase( name_t( "func_bleh_", "2" ) );
 338         names.erase( name_t( "func_bleh_", "3" ) );
 339         names.erase( name_t( "func_bleh_", "4" ) );
 340         names.erase( name_t( "func_bleh_", "5" ) );
 341         names.erase( name_t( "func_bleh_", "6" ) );
 342
 343         ASSERT_MESSAGE( names.empty(), "test failed!" );
 344 }
 345 public:
 346 TestUniqueName(){
 347         test_refcount();
 348         test_make_unique();
 349 }
 350 };
 351
 352 const TestUniqueName g_testuniquename;
 353
 354 #endif
 355
 356
 357 #endif