src/ptserver/map.c

   1 /*
   2  *      bit map routines (in-core).
   3  */
   4 /*
   5  * Copyright (c) 1995, 1996, 2007 Marcus D. Watts  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. The name of the developer may not be used to endorse or promote
  16  *    products derived from this software without specific prior written
  17  *    permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  21  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
  22  * MARCUS D. WATTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  24  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  25  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  27  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  28  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include <afsconfig.h>
  32 #include <afs/param.h>
  33
  34
  35 #ifdef SUPERGROUPS
  36 #include <errno.h>
  37 #include <string.h>
  38 #include "map.h"
  39 #ifdef STDLIB_HAS_MALLOC_PROTOS
  40 #include <stdlib.h>
  41 #else
  42 #include "malloc.h"
  43 #endif
  44
  45 #undef PRINT_MAP_ERROR
  46 /* #define MAP_DEBUG */
  47 /* #define NEED_READ_WRITE */
  48
  49 #define LSHIFT 5
  50 #define MSHIFT 8                /* XXX make this 8 in the production version... */
  51 #define MDATA (1<<MSHIFT)
  52 struct bitmap {
  53     struct bitmap *m_next;
  54     int m_page;
  55     int m_data[MDATA];
  56 };
  57
  58 #define MAP(p)  ((struct bitmap*)((int)(p)&~1))
  59 #define NEGMAP(p)       (((int)(p))&1)
  60 #define POSMAP(p)       (!NEGMAP(p))
  61 #define NOT_MAP(mp)     ((struct map *) (((int)(mp)) ^ 1))
  62
  63 #define NUMBERTOBIT(n)  ((n) & ((1<<LSHIFT)-1))
  64 #define NUMBERTOINDEX(n)        ((n>>LSHIFT) & ((1<<MSHIFT)-1))
  65 #define NUMBERTOPAGE(n) ((n>>(LSHIFT+MSHIFT)))
  66 #define TONUMBER(p,x,b) ((b) + ((x)<<LSHIFT) + ((p)<<((LSHIFT+MSHIFT))))
  67
  68 #define Mflag   (debug_mask & (1L<<('Y'-'@')))
  69 #define Aflag   (debug_mask & (1L<<('Z'-'@')))
  70 extern int debug_mask;
  71
  72 int
  73 in_map(struct map *parm, int node)
  74 {
  75     struct bitmap *map;
  76     int bit;
  77     int x, page;
  78     int result;
  79
  80 #ifdef MAP_DEBUG
  81     if (Aflag) {
  82         printf("in_map: is %d in [", node);
  83         print_map(parm);
  84         printf(" ]");
  85     }
  86 #endif
  87     bit = NUMBERTOBIT(node);
  88     x = NUMBERTOINDEX(node);
  89     page = NUMBERTOPAGE(node);
  90 #ifdef MAP_DEBUG
  91     if (Aflag)
  92         if (TONUMBER(page, x, bit) != node) {
  93             printf
  94                 ("bxp mixup: node=%d -> p=%d x=%d b=%d -> %d, %d, %d = %d\n",
  95                  node, page, x, bit, TONUMBER(page, 0, 0), TONUMBER(0, x, 0),
  96                  TONUMBER(0, 0, bit), TONUMBER(page, x, bit));
  97         }
  98 #endif
  99     bit = 1L << bit;;
 100
 101     for (map = MAP(parm); map; map = map->m_next)
 102         if (map->m_page == page)
 103             return NEGMAP(parm) ^ (!!(map->m_data[x] & bit));
 104     result = !POSMAP(parm);
 105 #ifdef MAP_DEBUG
 106     if (Aflag)
 107         printf(" -> %s\n", result ? "yes" : "no");
 108 #endif
 109     return result;
 110 }
 111
 112 void
 113 free_map(struct map *parm)
 114 {
 115     struct bitmap *map, *next;
 116 #ifdef MAP_DEBUG
 117     if (Aflag) {
 118         printf("Freeing map");
 119         print_map(parm);
 120         printf("\n");
 121     }
 122 #endif
 123     map = MAP(parm);
 124     while (map) {
 125         next = map->m_next;
 126         free(map);
 127         map = next;
 128     }
 129 }
 130
 131 struct map *
 132 add_map(struct map *parm, int node)
 133 {
 134     struct bitmap *map;
 135     int bit;
 136     int x, page;
 137
 138 #ifdef MAP_DEBUG
 139     if (Aflag) {
 140         printf("add_map: adding %d to [", node);
 141         print_map(parm);
 142         printf(" ] ");
 143     }
 144 #endif
 145     bit = NUMBERTOBIT(node);
 146     x = NUMBERTOINDEX(node);
 147     page = NUMBERTOPAGE(node);
 148
 149     bit = 1L << bit;;
 150
 151     for (map = MAP(parm); map; map = map->m_next)
 152         if (map->m_page == page)
 153             break;
 154     if (!map) {
 155         map = (struct bitmap *)malloc(sizeof *map);
 156         if (!map) {
 157 #ifdef PRINT_MAP_ERROR
 158             printf("No memory!\n");
 159 #endif
 160             free_map((struct map *)map);
 161             return 0;
 162         }
 163         map->m_page = page;
 164         memset( map->m_data, 0, sizeof map->m_data);
 165         if (NEGMAP(parm)) {
 166             int i;
 167             for (i = 0; i < MDATA; ++i)
 168                 map->m_data[i] = ~0;
 169         }
 170         map->m_next = MAP(parm);
 171         if (POSMAP(parm))
 172             parm = (struct map *)map;
 173         else
 174             parm = NOT_MAP(map);
 175     }
 176     if (POSMAP(parm))
 177         map->m_data[x] |= bit;
 178     else
 179         map->m_data[x] &= ~bit;
 180 #ifdef MAP_DEBUG
 181     if (Aflag) {
 182         printf(" ->");
 183         print_map(parm);
 184         printf("\n");
 185     }
 186 #endif
 187     return (struct map *)parm;
 188 }
 189
 190 struct bitmap *
 191 simplify_bitmap(struct bitmap *map)
 192 {
 193     struct bitmap **mpp, *mp2;
 194     int i;
 195     for (mpp = &map; (mp2 = *mpp);) {
 196         for (i = 0; i < MDATA; ++i)
 197             if (mp2->m_data[i])
 198                 break;
 199         if (i == MDATA) {
 200 #ifdef PRINT_MAP_ERROR
 201             printf("simplify_bitmap: failed to eliminate zero page %d\n",
 202                    mp2->m_page);
 203 #endif
 204             *mpp = mp2->m_next;
 205             free((char *)mp2);
 206         } else
 207             mpp = &mp2->m_next;
 208     }
 209     return map;
 210 }
 211
 212 struct bitmap *
 213 or_bitmap(struct bitmap *left, struct bitmap *right)
 214 {
 215     struct bitmap **rightmp, *lmap, *rmap;
 216     int i;
 217     for (lmap = left; lmap; lmap = lmap->m_next) {
 218         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
 219             if (rmap->m_page == lmap->m_page) {
 220                 for (i = 0; i < MDATA; ++i)
 221                     lmap->m_data[i] |= rmap->m_data[i];
 222                 *rightmp = rmap->m_next;
 223                 free((char *)rmap);
 224                 break;
 225             }
 226     }
 227     for (rightmp = &left; *rightmp; rightmp = &(*rightmp)->m_next)
 228         ;
 229     *rightmp = right;
 230     return left;
 231 }
 232
 233 struct bitmap *
 234 and_bitmap(struct bitmap *left, struct bitmap *right)
 235 {
 236     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
 237     int i;
 238     int sig;
 239     for (leftmp = &left; (lmap = *leftmp);) {
 240         sig = 0;
 241         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
 242             if (rmap->m_page == lmap->m_page) {
 243                 for (i = 0; i < MDATA; ++i)
 244                     sig |= (lmap->m_data[i] &= rmap->m_data[i]);
 245                 *rightmp = rmap->m_next;
 246                 free((char *)rmap);
 247                 break;
 248             }
 249         if (rmap && sig) {
 250             leftmp = &lmap->m_next;
 251         } else {
 252             *leftmp = lmap->m_next;
 253             free((char *)lmap);
 254         }
 255     }
 256     free_map((struct map *)right);
 257     return simplify_bitmap(left);
 258 }
 259
 260 /* bit set in left, but not in right */
 261 struct bitmap *
 262 bic_bitmap(struct bitmap *left, struct bitmap *right)
 263 {
 264     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
 265     int i;
 266     int sig;
 267 #ifdef MAP_DEBUG
 268     if (Mflag) {
 269         printf("bic_bitmap: left=%#lx right=%#lx\n", (long)left, (long)right);
 270     }
 271 #endif
 272     for (leftmp = &left; (lmap = *leftmp);) {
 273         sig = 0;
 274         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
 275             if (rmap->m_page == lmap->m_page) {
 276                 for (i = 0; i < MDATA; ++i)
 277                     sig |= (lmap->m_data[i] &= ~rmap->m_data[i]);
 278                 *rightmp = rmap->m_next;
 279                 free((char *)rmap);
 280                 break;
 281             }
 282         if (!rmap || sig) {
 283             leftmp = &lmap->m_next;
 284         } else {
 285             *leftmp = lmap->m_next;
 286             free((char *)lmap);
 287         }
 288     }
 289     free_map((struct map *)right);
 290     left = simplify_bitmap(left);
 291 #ifdef MAP_DEBUG
 292     if (Mflag) {
 293         printf("bic_bitmap: result=%#lx\n", (long) left);
 294     }
 295 #endif
 296     return left;
 297 }
 298
 299 struct map *
 300 and_map(struct map *mp1, struct map *mp2)
 301 {
 302 #ifdef MAP_DEBUG
 303     if (Mflag) {
 304         printf("Anding maps");
 305         print_map(mp1);
 306         printf(" and");
 307         print_map(mp2);
 308     }
 309 #endif
 310     if (POSMAP(mp1))
 311         if (POSMAP(mp2))
 312             mp1 = (struct map *)and_bitmap((struct bitmap *) mp1,
 313                 (struct bitmap *) mp2);
 314         else
 315             mp1 = (struct map *)bic_bitmap((struct bitmap *) mp1, MAP(mp2));
 316     else if (POSMAP(mp2))
 317         mp1 = (struct map *)bic_bitmap((struct bitmap *) mp2, MAP(mp1));
 318     else
 319         mp1 = NOT_MAP(or_bitmap(MAP(mp1), MAP(mp2)));
 320 #ifdef MAP_DEBUG
 321     if (Mflag) {
 322         printf(" ->");
 323         print_map(mp1);
 324         printf("\n");
 325     }
 326 #endif
 327     return mp1;
 328 }
 329
 330 struct map *
 331 or_map(struct map *mp1, struct map *mp2)
 332 {
 333 #ifdef MAP_DEBUG
 334     if (Mflag) {
 335         printf("Oring maps");
 336         print_map(mp1);
 337         printf(" and");
 338         print_map(mp2);
 339     }
 340 #endif
 341     if (POSMAP(mp1))
 342         if (POSMAP(mp2))
 343             mp1 = (struct map *)or_bitmap((struct bitmap *) mp1,
 344                 (struct bitmap *) mp2);
 345         else
 346             mp1 = NOT_MAP(bic_bitmap(MAP(mp2), (struct bitmap *) mp1));
 347     else if (POSMAP(mp2))
 348         mp1 = NOT_MAP(bic_bitmap(MAP(mp1), (struct bitmap *) mp2));
 349     else
 350         mp1 = NOT_MAP(and_bitmap(MAP(mp1), MAP(mp2)));
 351 #ifdef MAP_DEBUG
 352     if (Mflag) {
 353         printf(" ->");
 354         print_map(mp1);
 355         printf("\n");
 356     }
 357 #endif
 358     return mp1;
 359 }
 360
 361 struct map *
 362 not_map(struct map *map)
 363 {
 364 #ifdef MAP_DEBUG
 365     if (Mflag) {
 366         printf("Notting map");
 367         print_map(map);
 368         printf("\n");
 369     }
 370 #endif
 371     return NOT_MAP(map);
 372 }
 373
 374 struct map *
 375 copy_map(struct map *parm)
 376 {
 377     struct bitmap *result, **mpp, *map;
 378 #ifdef MAP_DEBUG
 379     if (Mflag) {
 380         printf("copymap:");
 381         print_map(parm);
 382         printf("\n");
 383     }
 384 #endif
 385     map = MAP(parm);
 386     for (mpp = &result; (*mpp = 0), map; map = map->m_next) {
 387         *mpp = (struct bitmap *)malloc(sizeof **mpp);
 388         if (!*mpp) {
 389 #ifdef MAP_DEBUG
 390             if (Mflag)
 391                 printf("copy_map: out of memory\n");
 392 #endif
 393             free_map((struct map *)result);
 394             result = 0;
 395             break;
 396         }
 397         **mpp = *map;
 398         mpp = &(*mpp)->m_next;
 399     }
 400     if (NEGMAP(parm))
 401         return NOT_MAP(result);
 402     else
 403         return (struct map *)result;
 404 }
 405
 406 int
 407 count_map(struct map *parm)
 408 {
 409     int nf;
 410     struct bitmap *map;
 411     int i, j;
 412
 413     nf = 0;
 414     for (map = MAP(parm); map; map = map->m_next) {
 415         for (i = 0; i < MDATA; ++i) {
 416             if (!map->m_data[i])
 417                 ;
 418             else if (!~map->m_data[i])
 419                 nf += (1 << LSHIFT);
 420             else
 421                 for (j = 0; j < (1L << LSHIFT); ++j)
 422                     if (map->m_data[i] & (1L << j))
 423                         ++nf;
 424         }
 425     }
 426     if (NEGMAP(parm))
 427         nf = ~nf;               /* note 1's complement */
 428 #ifdef MAP_DEBUG
 429     if (Mflag) {
 430         printf("countmap:");
 431         print_map(parm);
 432         printf(" -> %d\n", nf);
 433     }
 434 #endif
 435     return nf;
 436 }
 437
 438 int
 439 next_map(struct map *parm, int node)
 440 {
 441     struct bitmap *map, *lowest;
 442     int bit, mask;
 443     int x, page;
 444     int best;
 445     int i;
 446     int bn;
 447
 448 #ifdef MAP_DEBUG
 449     if (Aflag) {
 450         printf("next_map: selecting next after %d from", node);
 451         print_map(parm);
 452     }
 453 #endif
 454     if (NEGMAP(parm)) {
 455 #ifdef MAP_DEBUG
 456         if (Aflag)
 457             printf("next_map failed; negative map\n");
 458 #endif
 459         return -1;
 460     }
 461
 462     ++node;
 463     bit = NUMBERTOBIT(node);
 464     x = NUMBERTOINDEX(node);
 465     page = NUMBERTOPAGE(node);
 466     bit = 1L << bit;
 467     best = -1;
 468     lowest = 0;
 469     for (map = MAP(parm); map; map = map->m_next)
 470         if (map->m_page >= page && (!lowest || lowest->m_page > map->m_page)) {
 471             i = 0;
 472             mask = ~0;
 473             if (page == map->m_page)
 474                 i = x, mask = -bit;
 475             for (; i < MDATA; ++i, mask = ~0)
 476                 if (map->m_data[i] & mask)
 477                     break;
 478             if (i < MDATA) {
 479                 for (bn = 0; bn < (1 << LSHIFT); ++bn)
 480                     if (map->m_data[i] & mask & (1L << bn)) {
 481                         break;
 482                     }
 483 #ifdef MAP_DEBUG
 484                 if (Aflag) {
 485                     if (bn == (1 << LSHIFT)) {
 486                         printf
 487                             ("next_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
 488                              map->m_page, i, map->m_data[i], mask, x, bit);
 489                         continue;
 490                     }
 491                 }
 492 #endif
 493                 best = bn + ((i + ((map->m_page) << MSHIFT)
 494                              ) << LSHIFT);
 495                 lowest = map;
 496             }
 497         }
 498 #ifdef MAP_DEBUG
 499     if (Aflag) {
 500         printf(" -> %d\n", best);
 501         if (best >= 0 && !in_map(parm, best)) {
 502             printf("next_map: botch; %d not in map\n", best);
 503             return -1;
 504         }
 505     }
 506 #endif
 507     return best;
 508 }
 509
 510 int
 511 first_map(struct map *parm)
 512 {
 513     return next_map(parm, -9999);
 514 }
 515
 516 int
 517 prev_map(struct map *parm, int node)
 518 {
 519     struct bitmap *map, *lowest;
 520     int bit, mask;
 521     int x, page;
 522     int best;
 523     int i;
 524     int bn;
 525
 526 #ifdef MAP_DEBUG
 527     if (Aflag) {
 528         printf("prev_map: selecting previous before %d from", node);
 529         print_map(parm);
 530     }
 531 #endif
 532     if (NEGMAP(parm)) {
 533 #ifdef MAP_DEBUG
 534         if (Aflag)
 535             printf("prev_map failed; negative map\n");
 536 #endif
 537         return -1;
 538     }
 539
 540     if (node < 0)
 541         node = ((unsigned int)~0) >> 1;
 542
 543     --node;
 544     bit = NUMBERTOBIT(node);
 545     x = NUMBERTOINDEX(node);
 546     page = NUMBERTOPAGE(node);
 547     bit = 1L << bit;
 548     best = -1;
 549     lowest = 0;
 550     for (map = MAP(parm); map; map = map->m_next)
 551         if (map->m_page <= page && (!lowest || lowest->m_page < map->m_page)) {
 552             i = MDATA - 1;
 553             mask = ~0;
 554             if (page == map->m_page)
 555                 i = x, mask = (bit << 1) - 1;
 556             for (; i >= 0; --i, mask = ~0)
 557                 if (map->m_data[i] & mask)
 558                     break;
 559             if (i >= 0) {
 560                 for (bn = (1 << LSHIFT) - 1; bn >= 0; --bn)
 561                     if (map->m_data[i] & mask & (1L << bn)) {
 562                         break;
 563                     }
 564 #ifdef MAP_DEBUG
 565                 if (Aflag) {
 566                     if (bn < 0) {
 567                         printf
 568                             ("prev_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
 569                              map->m_page, i, map->m_data[i], mask, x, bit);
 570                         continue;
 571                     }
 572                 }
 573 #endif
 574                 best = bn + ((i + ((map->m_page) << MSHIFT)
 575                              ) << LSHIFT);
 576                 lowest = map;
 577             }
 578         }
 579 #ifdef MAP_DEBUG
 580     if (Aflag) {
 581         printf(" -> %d\n", best);
 582         if (best >= 0 && !in_map(parm, best)) {
 583             printf("prev_map: botch; %d not in map\n", best);
 584             return -1;
 585         }
 586     }
 587 #endif
 588     return best;
 589 }
 590
 591 int
 592 last_map(struct map *parm)
 593 {
 594     return prev_map(parm, 0x7fffffff);
 595 }
 596
 597 struct map *
 598 negative_map(struct map *map)
 599 {
 600     return (struct map *)NEGMAP(map);
 601 }
 602
 603 struct map *
 604 bic_map(struct map *mp1, struct map *mp2)
 605 {
 606 #ifdef MAP_DEBUG
 607     if (Mflag) {
 608         printf("Bic maps");
 609         print_map(mp1);
 610         printf(" minus");
 611         print_map(mp2);
 612     }
 613 #endif
 614     mp1 = and_map(mp1, NOT_MAP(mp2));
 615 #ifdef MAP_DEBUG
 616     if (Mflag) {
 617         printf(" ->");
 618         print_map(mp1);
 619         printf("\n");
 620     }
 621 #endif
 622     return mp1;
 623 }
 624
 625 #ifdef PRINT_MAP_ERROR
 626 void
 627 print_map(struct map *parm)
 628 {
 629     struct bitmap *map;
 630     int i, j;
 631     int bitno, firstbitno, lastbitno;
 632     if (NEGMAP(parm)) {
 633         printf(" NOT");
 634     }
 635     map = MAP(parm);
 636     if (!map)
 637         printf(" nil(%lx)", (long)parm);
 638     else
 639         printf(" %lx", (long)parm);
 640     lastbitno = -100;
 641     firstbitno = -100;
 642     for (; map; map = map->m_next)
 643         for (i = 0; i < MDATA; ++i)
 644             if (map->m_data[i])
 645                 for (j = 0; j < (1 << LSHIFT); ++j) {
 646                     bitno =
 647                         j + (i << LSHIFT) +
 648                         ((map->m_page) << (LSHIFT + MSHIFT));
 649                     if (map->m_data[i] & (1 << j)) {
 650                         if (bitno == lastbitno + 1) {
 651                             ++lastbitno;
 652                             continue;
 653                         }
 654                         if (bitno != (lastbitno + 1)) {
 655                             if (firstbitno >= 0 && firstbitno != lastbitno)
 656                                 printf("-%d", lastbitno);
 657                             firstbitno = -100;
 658                         }
 659                         printf(" %d", bitno);
 660                         firstbitno = lastbitno = bitno;
 661                     } else {
 662                         if (firstbitno >= 0 && firstbitno != lastbitno)
 663                             printf("-%d", lastbitno);
 664                         firstbitno = -100;
 665                     }
 666                 }
 667     if (firstbitno >= 0 && firstbitno != lastbitno)
 668         printf("-%d", lastbitno);
 669 }
 670 #endif
 671
 672 #ifdef NEED_READ_WRITE
 673 struct map *
 674 read_map(int (*f) (void *), char *arg)
 675 {
 676     struct bitmap *map, *result, **mp;
 677     int page;
 678     int bitno, lastno;
 679     int data;
 680
 681 /* count, then startbitno, then bits. */
 682     lastno = ((*f) (arg));
 683     if (lastno == -1)
 684         return 0;
 685     if (lastno & ((1 << LSHIFT) - 1)) {
 686 #ifdef PRINT_MAP_ERROR
 687         printf("read_map: bad count\n");
 688 #endif
 689         return 0;
 690     }
 691     bitno = ((*f) (arg));
 692     if (bitno & ((1 << LSHIFT) - 1)) {
 693 #ifdef PRINT_MAP_ERROR
 694         printf("read_map: bad start\n");
 695 #endif
 696         return 0;
 697     }
 698     lastno += bitno;
 699     map = result = 0;
 700     for (; bitno < lastno; bitno += (1 << LSHIFT)) {
 701         data = (*f) (arg);
 702         if (!data)
 703             continue;
 704         page = NUMBERTOPAGE(bitno);
 705         if (!map || map->m_page != page)
 706             for (mp = &result; (map = *mp); mp = &map->m_next)
 707                 if (map->m_page == page)
 708                     break;
 709         if (!map) {
 710             map = (struct bitmap *)malloc(sizeof *map);
 711             if (!map) {
 712 #ifdef PRINT_MAP_ERROR
 713                 printf("No memory!\n");
 714 #endif
 715                 if (result)
 716                     free_map((struct map *)result);
 717                 return 0;
 718             }
 719             memset( map->m_data, 0, sizeof map->m_data);
 720             map->m_page = page;
 721             map->m_next = 0;
 722             *mp = map;
 723         }
 724         map->m_data[NUMBERTOINDEX(bitno)] = data;
 725     }
 726     return (struct map *)result;
 727 }
 728
 729 int
 730 write_map(struct map *parm, int (*f) (void *, int), char *arg)
 731 {
 732     struct bitmap *map;
 733     int page;
 734     int bitno, lastno, thisno, prevno;
 735     int i, j;
 736
 737     bitno = first_map(parm);
 738     bitno &= ~((1 << LSHIFT) - 1);
 739
 740     lastno = last_map(parm);
 741     lastno -= bitno;
 742     lastno += ((1 << LSHIFT));
 743     lastno &= ~((1 << LSHIFT) - 1);
 744 /* count, then startbitno, then bits. */
 745     if ((*f) (arg, lastno) == -1)
 746         return -1;
 747     /* word: number of bits */
 748     if ((*f) (arg, bitno) == -1)
 749         return -1;
 750     lastno += bitno;
 751     prevno = bitno;
 752     for (bitno = first_map(parm); bitno >= 0; bitno = next_map(parm, bitno)) {
 753         page = NUMBERTOPAGE(bitno);
 754         for (map = MAP(parm); map; map = map->m_next)
 755             if (map->m_page == page)
 756                 break;
 757         if (!map) {
 758 #ifdef PRINT_MAP_ERROR
 759             printf("write_map: botch #1: can't find page %d\n", page);
 760 #endif
 761             continue;
 762         }
 763         for (i = 0; i < MDATA; ++i) {
 764             if (!map->m_data[i])
 765                 continue;
 766             thisno = TONUMBER(page, i, 0);
 767             for (j = thisno - prevno; j > 0; j -= (1 << LSHIFT))
 768                 if ((*f) (arg, 0) == -1)
 769                     return -1;
 770             prevno = thisno;
 771             for (;;) {
 772                 if ((*f) (arg, map->m_data[i]) == -1)
 773                     return -1;
 774                 prevno += (1 << LSHIFT);
 775                 ++i;
 776                 if (i >= MDATA || !map->m_data[i])
 777                     break;
 778             }
 779             --i;
 780         }
 781         bitno = TONUMBER(page, i, 0) - 1;
 782     }
 783 #ifdef PRINT_MAP_ERROR
 784     if (prevno != lastno)
 785         printf("write_map: botch #2: bitno=%d prevno=%d lastno=%d\n", bitno,
 786                prevno, lastno);
 787 #endif
 788     return 0;
 789 }
 790 #endif
 791
 792 #endif