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