The Ecere SDK - sdk/blob - ecere/src/gfx/newFonts/cc/mmbitmap.c

   1 /* *****************************************************************************
   2  * Copyright (c) 2007-2014 Alexis Naveros.
   3  *
   4  * Ecere Corporation has unlimited/unrestricted rights.
   5  * *****************************************************************************/
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <stddef.h>
   9 #include <stdint.h>
  10 #include <string.h>
  11 #include <math.h>
  12
  13 #include "cpuconfig.h"
  14 #include "cc.h"
  15 #include "mm.h"
  16 #include "mmbitmap.h"
  17
  18
  19 /* Friendlier to cache on SMP systems */
  20 #define BP_BITMAP_PREWRITE_CHECK
  21
  22
  23 /*
  24 TODO
  25 If we don't have atomic instruction support somehow, we need a much better mutex locking mechanism!!
  26 */
  27
  28
  29 int mmBitMapInit( mmBitMap *bitmap, size_t entrycount, int initvalue )
  30 {
  31   size_t mapsize, index;
  32   long value;
  33 #ifdef MM_ATOMIC_SUPPORT
  34   mmAtomicL *map;
  35 #else
  36   long *map;
  37 #endif
  38
  39   mapsize = ( entrycount + CPUCONF_LONG_BITS - 1 ) >> CPUCONF_LONG_BITSHIFT;
  40   bitmap->map = 0;
  41   if( mapsize )
  42   {
  43     if( !( bitmap->map = malloc( mapsize * sizeof(mmAtomicL) ) ) )
  44       return 0;
  45   }
  46   bitmap->mapsize = mapsize;
  47   bitmap->entrycount = entrycount;
  48
  49   map = bitmap->map;
  50   value = ( initvalue & 0x1 ? ~0x0 : 0x0 );
  51 #ifdef MM_ATOMIC_SUPPORT
  52   for( index = 0 ; index < mapsize ; index++ )
  53     mmAtomicWriteL( &map[index], value );
  54 #else
  55   for( index = 0 ; index < mapsize ; index++ )
  56     map[index] = value;
  57   mtMutexInit( &bitmap->mutex );
  58 #endif
  59
  60   return 1;
  61 }
  62
  63 void mmBitMapReset( mmBitMap *bitmap, int resetvalue )
  64 {
  65   size_t index;
  66   long value;
  67 #ifdef MM_ATOMIC_SUPPORT
  68   mmAtomicL *map;
  69 #else
  70   long *map;
  71 #endif
  72
  73   map = bitmap->map;
  74   value = ( resetvalue & 0x1 ? ~(long)0x0 : (long)0x0 );
  75 #ifdef MM_ATOMIC_SUPPORT
  76   for( index = 0 ; index < bitmap->mapsize ; index++ )
  77     mmAtomicWriteL( &map[index], value );
  78 #else
  79   for( index = 0 ; index < bitmap->mapsize ; index++ )
  80     map[index] = value;
  81 #endif
  82
  83   return;
  84 }
  85
  86 void mmBitMapResetRange( mmBitMap *bitmap, int minimumentrycount, int resetvalue )
  87 {
  88   size_t index, entrycount;
  89   long value;
  90 #ifdef MM_ATOMIC_SUPPORT
  91   mmAtomicL *map;
  92 #else
  93   long *map;
  94 #endif
  95
  96   map = bitmap->map;
  97   value = ( resetvalue & 0x1 ? ~(long)0x0 : (long)0x0 );
  98   entrycount = ( minimumentrycount + CPUCONF_LONG_BITS - 1 ) >> CPUCONF_LONG_BITSHIFT;
  99 #ifdef MM_ATOMIC_SUPPORT
 100   for( index = 0 ; index < entrycount ; index++ )
 101     mmAtomicWriteL( &map[index], value );
 102 #else
 103   for( index = 0 ; index < entrycount ; index++ )
 104     map[index] = value;
 105 #endif
 106
 107   return;
 108 }
 109
 110 void mmBitMapFree( mmBitMap *bitmap )
 111 {
 112   free( bitmap->map );
 113   bitmap->map = 0;
 114   bitmap->mapsize = 0;
 115 #ifndef MM_ATOMIC_SUPPORT
 116   mtMutexDestroy( &bitmap->mutex );
 117 #endif
 118   return;
 119 }
 120
 121 /* TODO: Yeah... That code was written in one go, maybe I should test if it's working fine, just in case? */
 122 int mmBitMapFindSet( mmBitMap *bitmap, size_t entryindex, size_t entryindexlast, size_t *retentryindex )
 123 {
 124   unsigned long value;
 125   size_t index, shift, shiftbase, shiftmax, indexlast, shiftlast;
 126
 127   if( !( bitmap->entrycount ) )
 128     return 0;
 129
 130   indexlast = entryindexlast >> CPUCONF_LONG_BITSHIFT;
 131   shiftlast = entryindexlast & ( CPUCONF_LONG_BITS - 1 );
 132
 133   /* Leading bits search */
 134   index = entryindex >> CPUCONF_LONG_BITSHIFT;
 135   shiftbase = entryindex & ( CPUCONF_LONG_BITS - 1 );
 136 #ifdef MM_ATOMIC_SUPPORT
 137   value = mmAtomicReadL( &bitmap->map[index] );
 138 #else
 139   mtMutexLock( &bitmap->mutex );
 140   value = bitmap->map[index];
 141 #endif
 142   if( value != (unsigned long)0x0 )
 143   {
 144     shiftmax = CPUCONF_LONG_BITS-1;
 145     if( ( index == indexlast ) && ( shiftlast > shiftbase ) )
 146       shiftmax = shiftlast;
 147     value >>= shiftbase;
 148     for( shift = shiftbase ; shift <= shiftmax ; shift++, value >>= 1 )
 149     {
 150       if( !( value & 0x1 ) )
 151         continue;
 152       entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 153       if( entryindex >= bitmap->entrycount )
 154         break;
 155 #ifndef MM_ATOMIC_SUPPORT
 156       mtMutexUnlock( &bitmap->mutex );
 157 #endif
 158       *retentryindex = entryindex;
 159       return 1;
 160     }
 161   }
 162   if( ( index == indexlast ) && ( shiftlast > shiftbase ) )
 163   {
 164 #ifndef MM_ATOMIC_SUPPORT
 165     mtMutexUnlock( &bitmap->mutex );
 166 #endif
 167     return 0;
 168   }
 169
 170   /* Main search */
 171   for( ; ; )
 172   {
 173     index = ( index + 1 ) % bitmap->mapsize;
 174     if( index == indexlast )
 175       break;
 176 #ifdef MM_ATOMIC_SUPPORT
 177     value = mmAtomicReadL( &bitmap->map[index] );
 178 #else
 179     value = bitmap->map[index];
 180 #endif
 181     if( value != (unsigned long)0x0 )
 182     {
 183       for( shift = 0 ; ; shift++, value >>= 1 )
 184       {
 185         if( !( value & 0x1 ) )
 186           continue;
 187         entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 188         if( entryindex >= bitmap->entrycount )
 189           break;
 190 #ifndef MM_ATOMIC_SUPPORT
 191         mtMutexUnlock( &bitmap->mutex );
 192 #endif
 193         *retentryindex = entryindex;
 194         return 1;
 195       }
 196     }
 197   }
 198
 199   /* Trailing bits search */
 200   shiftlast = entryindexlast & ( CPUCONF_LONG_BITS - 1 );
 201 #ifdef MM_ATOMIC_SUPPORT
 202   value = mmAtomicReadL( &bitmap->map[index] );
 203 #else
 204   value = bitmap->map[index];
 205 #endif
 206   if( value != (unsigned long)0x0 )
 207   {
 208     for( shift = 0 ; shift < shiftlast ; shift++, value >>= 1 )
 209     {
 210       if( !( value & 0x1 ) )
 211         continue;
 212       entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 213       if( entryindex >= bitmap->entrycount )
 214         break;
 215 #ifndef MM_ATOMIC_SUPPORT
 216       mtMutexUnlock( &bitmap->mutex );
 217 #endif
 218       *retentryindex = entryindex;
 219       return 1;
 220     }
 221   }
 222 #ifndef MM_ATOMIC_SUPPORT
 223   mtMutexUnlock( &bitmap->mutex );
 224 #endif
 225
 226   return 0;
 227 }
 228
 229 int mmBitMapFindClear( mmBitMap *bitmap, size_t entryindex, size_t entryindexlast, size_t *retentryindex )
 230 {
 231   unsigned long value;
 232   size_t index, shift, shiftbase, shiftmax, indexlast, shiftlast;
 233
 234   if( !( bitmap->entrycount ) )
 235     return 0;
 236
 237   indexlast = entryindexlast >> CPUCONF_LONG_BITSHIFT;
 238   shiftlast = entryindexlast & ( CPUCONF_LONG_BITS - 1 );
 239
 240   /* Leading bits search */
 241   index = entryindex >> CPUCONF_LONG_BITSHIFT;
 242   shiftbase = entryindex & ( CPUCONF_LONG_BITS - 1 );
 243 #ifdef MM_ATOMIC_SUPPORT
 244   value = mmAtomicReadL( &bitmap->map[index] );
 245 #else
 246   mtMutexLock( &bitmap->mutex );
 247   value = bitmap->map[index];
 248 #endif
 249   if( value != ~(unsigned long)0x0 )
 250   {
 251     shiftmax = CPUCONF_LONG_BITS-1;
 252     if( ( index == indexlast ) && ( shiftlast > shiftbase ) )
 253       shiftmax = shiftlast;
 254     value >>= shiftbase;
 255     for( shift = shiftbase ; shift <= shiftmax ; shift++, value >>= 1 )
 256     {
 257       if( value & 0x1 )
 258         continue;
 259       entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 260       if( entryindex >= bitmap->entrycount )
 261         break;
 262 #ifndef MM_ATOMIC_SUPPORT
 263       mtMutexUnlock( &bitmap->mutex );
 264 #endif
 265       *retentryindex = entryindex;
 266       return 1;
 267     }
 268   }
 269   if( ( index == indexlast ) && ( shiftlast > shiftbase ) )
 270   {
 271 #ifndef MM_ATOMIC_SUPPORT
 272     mtMutexUnlock( &bitmap->mutex );
 273 #endif
 274     return 0;
 275   }
 276
 277   /* Main search */
 278   for( ; ; )
 279   {
 280     index = ( index + 1 ) % bitmap->mapsize;
 281     if( index == indexlast )
 282       break;
 283 #ifdef MM_ATOMIC_SUPPORT
 284     value = mmAtomicReadL( &bitmap->map[index] );
 285 #else
 286     value = bitmap->map[index];
 287 #endif
 288     if( value != ~(unsigned long)0x0 )
 289     {
 290       for( shift = 0 ; ; shift++, value >>= 1 )
 291       {
 292         if( value & 0x1 )
 293           continue;
 294         entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 295         if( entryindex >= bitmap->entrycount )
 296           break;
 297 #ifndef MM_ATOMIC_SUPPORT
 298         mtMutexUnlock( &bitmap->mutex );
 299 #endif
 300         *retentryindex = entryindex;
 301         return 1;
 302       }
 303     }
 304   }
 305
 306   /* Trailing bits search */
 307   shiftlast = entryindexlast & ( CPUCONF_LONG_BITS - 1 );
 308 #ifdef MM_ATOMIC_SUPPORT
 309   value = mmAtomicReadL( &bitmap->map[index] );
 310 #else
 311   value = bitmap->map[index];
 312 #endif
 313   if( value != ~(unsigned long)0x0 )
 314   {
 315     for( shift = 0 ; shift <= shiftlast ; shift++, value >>= 1 )
 316     {
 317       if( value & 0x1 )
 318         continue;
 319       entryindex = ( index << CPUCONF_LONG_BITSHIFT ) | shift;
 320       if( entryindex >= bitmap->entrycount )
 321         break;
 322 #ifndef MM_ATOMIC_SUPPORT
 323       mtMutexUnlock( &bitmap->mutex );
 324 #endif
 325       *retentryindex = entryindex;
 326       return 1;
 327     }
 328   }
 329 #ifndef MM_ATOMIC_SUPPORT
 330   mtMutexUnlock( &bitmap->mutex );
 331 #endif
 332
 333   return 0;
 334 }