src/ptserver/map.c

   1 /*
   2  *      bit map routines (in-core).
   3  */
   4 /*
   5  * Copyright (c) 1995, 1996 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. All advertising materials mentioning features or use of this software
  16  *    must display the following acknowledgement:
  17  *      This product includes software developed by Marcus D. Watts.
  18  * 4. The name of the developer may not be used to endorse or promote
  19  *    products derived from this software without specific prior written
  20  *    permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  23  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  24  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
  25  * MARCUS D. WATTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  28  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  29  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  30  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  31  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <afsconfig.h>
  35 #include <afs/param.h>
  36
  37 RCSID
  38     ("$Header$");
  39
  40 #ifdef SUPERGROUPS
  41 #include <errno.h>
  42 #include "map.h"
  43 char *malloc();
  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     long m_data[MDATA];
  56 };
  57
  58 #define MAP(p)  ((struct bitmap*)((long)(p)&~1))
  59 #define NEGMAP(p)       (((int)(p))&1)
  60 #define POSMAP(p)       (!NEGMAP(p))
  61 #define NOT_MAP(mp)     ((struct map *) (((long)(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, long node)
  74 {
  75     struct bitmap *map;
  76     long 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=%ld -> p=%d x=%d b=%d -> %ld, %ld, %ld = %ld\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, long node)
 133 {
 134     struct bitmap *map;
 135     long 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         bzero((char *)map->m_data, 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 (map->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     *rightmp = right;
 229     return left;
 230 }
 231
 232 struct bitmap *
 233 and_bitmap(struct bitmap *left, struct bitmap *right)
 234 {
 235     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
 236     int i;
 237     long sig;
 238     for (leftmp = &left; lmap = *leftmp;) {
 239         sig = 0;
 240         for (rightmp = &right; rmap = *rightmp; rightmp = &rmap->m_next)
 241             if (rmap->m_page == lmap->m_page) {
 242                 for (i = 0; i < MDATA; ++i)
 243                     sig |= (lmap->m_data[i] &= rmap->m_data[i]);
 244                 *rightmp = rmap->m_next;
 245                 free((char *)rmap);
 246                 break;
 247             }
 248         if (rmap && sig) {
 249             leftmp = &lmap->m_next;
 250         } else {
 251             *leftmp = lmap->m_next;
 252             free((char *)lmap);
 253         }
 254     }
 255     free_map((struct map *)right);
 256     return simplify_bitmap(left);
 257 }
 258
 259 /* bit set in left, but not in right */
 260 struct bitmap *
 261 bic_bitmap(struct bitmap *left, struct bitmap *right)
 262 {
 263     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
 264     int i;
 265     long sig;
 266 #ifdef MAP_DEBUG
 267     if (Mflag) {
 268         printf("bic_bitmap: left=%#lx right=%#lx\n", left, right);
 269     }
 270 #endif
 271     for (leftmp = &left; lmap = *leftmp;) {
 272         sig = 0;
 273         for (rightmp = &right; rmap = *rightmp; rightmp = &rmap->m_next)
 274             if (rmap->m_page == lmap->m_page) {
 275                 for (i = 0; i < MDATA; ++i)
 276                     sig |= (lmap->m_data[i] &= ~rmap->m_data[i]);
 277                 *rightmp = rmap->m_next;
 278                 free((char *)rmap);
 279                 break;
 280             }
 281         if (!rmap || sig) {
 282             leftmp = &lmap->m_next;
 283         } else {
 284             *leftmp = lmap->m_next;
 285             free((char *)lmap);
 286         }
 287     }
 288     free_map((struct map *)right);
 289     left = simplify_bitmap(left);
 290 #ifdef MAP_DEBUG
 291     if (Mflag) {
 292         printf("bic_bitmap: result=%#lx\n", left);
 293     }
 294 #endif
 295     return left;
 296 }
 297
 298 struct map *
 299 and_map(struct map *mp1, struct map *mp2)
 300 {
 301 #ifdef MAP_DEBUG
 302     if (Mflag) {
 303         printf("Anding maps");
 304         print_map(mp1);
 305         printf(" and");
 306         print_map(mp2);
 307     }
 308 #endif
 309     if (POSMAP(mp1))
 310         if (POSMAP(mp2))
 311             mp1 = (struct map *)and_bitmap(mp1, mp2);
 312         else
 313             mp1 = (struct map *)bic_bitmap(mp1, MAP(mp2));
 314     else if (POSMAP(mp2))
 315         mp1 = (struct map *)bic_bitmap(mp2, MAP(mp1));
 316     else
 317         mp1 = NOT_MAP(or_bitmap(MAP(mp1), MAP(mp2)));
 318 #ifdef MAP_DEBUG
 319     if (Mflag) {
 320         printf(" ->");
 321         print_map(mp1);
 322         printf("\n");
 323     }
 324 #endif
 325     return mp1;
 326 }
 327
 328 struct map *
 329 or_map(struct map *mp1, struct map *mp2)
 330 {
 331 #ifdef MAP_DEBUG
 332     if (Mflag) {
 333         printf("Oring maps");
 334         print_map(mp1);
 335         printf(" and");
 336         print_map(mp2);
 337     }
 338 #endif
 339     if (POSMAP(mp1))
 340         if (POSMAP(mp2))
 341             mp1 = (struct map *)or_bitmap(mp1, mp2);
 342         else
 343             mp1 = NOT_MAP(bic_bitmap(MAP(mp2), mp1));
 344     else if (POSMAP(mp2))
 345         mp1 = NOT_MAP(bic_bitmap(MAP(mp1), 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 long
 404 count_map(struct map *parm)
 405 {
 406     long nf;
 407     struct bitmap *map;
 408     register 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             else if (!~map->m_data[i])
 415                 nf += (1 << LSHIFT);
 416             else
 417                 for (j = 0; j < (1L << LSHIFT); ++j)
 418                     if (map->m_data[i] & (1L << j))
 419                         ++nf;
 420         }
 421     }
 422     if (NEGMAP(parm))
 423         nf = ~nf;               /* note 1's complement */
 424 #ifdef MAP_DEBUG
 425     if (Mflag) {
 426         printf("countmap:");
 427         print_map(parm);
 428         printf(" -> %d\n", nf);
 429     }
 430 #endif
 431     return nf;
 432 }
 433
 434 long
 435 next_map(struct map *parm, long node)
 436 {
 437     struct bitmap *map, *lowest;
 438     long bit, mask;
 439     int x, page;
 440     int best;
 441     int i;
 442     int bn;
 443
 444 #ifdef MAP_DEBUG
 445     if (Aflag) {
 446         printf("next_map: selecting next after %d from", node);
 447         print_map(parm);
 448     }
 449 #endif
 450     if (NEGMAP(parm)) {
 451 #ifdef MAP_DEBUG
 452         if (Aflag)
 453             printf("next_map failed; negative map\n");
 454 #endif
 455         return -1;
 456     }
 457
 458     ++node;
 459     bit = NUMBERTOBIT(node);
 460     x = NUMBERTOINDEX(node);
 461     page = NUMBERTOPAGE(node);
 462     bit = 1L << bit;
 463     best = -1;
 464     lowest = 0;
 465     for (map = MAP(parm); map; map = map->m_next)
 466         if (map->m_page >= page && (!lowest || lowest->m_page > map->m_page)) {
 467             i = 0;
 468             mask = ~0;
 469             if (page == map->m_page)
 470                 i = x, mask = -bit;
 471             for (; i < MDATA; ++i, mask = ~0)
 472                 if (map->m_data[i] & mask)
 473                     break;
 474             if (i < MDATA) {
 475                 for (bn = 0; bn < (1 << LSHIFT); ++bn)
 476                     if (map->m_data[i] & mask & (1L << bn)) {
 477                         break;
 478                     }
 479 #ifdef MAP_DEBUG
 480                 if (Aflag) {
 481                     if (bn == (1 << LSHIFT)) {
 482                         printf
 483                             ("next_map: botch; pageno %d index %d data %#lx mask %#lx x,bit %d,%#lx\n",
 484                              map->m_page, i, map->m_data[i], mask, x, bit);
 485                         continue;
 486                     }
 487                 }
 488 #endif
 489                 best = bn + ((i + ((map->m_page) << MSHIFT)
 490                              ) << LSHIFT);
 491                 lowest = map;
 492             }
 493         }
 494 #ifdef MAP_DEBUG
 495     if (Aflag) {
 496         printf(" -> %d\n", best);
 497         if (best >= 0 && !in_map((struct map *)parm, best)) {
 498             printf("next_map: botch; %d not in map\n", best);
 499             return -1;
 500         }
 501     }
 502 #endif
 503     return best;
 504 }
 505
 506 long
 507 first_map(struct map *parm)
 508 {
 509     return next_map(parm, -9999);
 510 }
 511
 512 long
 513 prev_map(struct map *parm, long node)
 514 {
 515     struct bitmap *map, *lowest;
 516     long bit, mask;
 517     int x, page;
 518     int best;
 519     int i;
 520     int bn;
 521
 522 #ifdef MAP_DEBUG
 523     if (Aflag) {
 524         printf("prev_map: selecting previous before %d from", node);
 525         print_map(parm);
 526     }
 527 #endif
 528     if (NEGMAP(parm)) {
 529 #ifdef MAP_DEBUG
 530         if (Aflag)
 531             printf("prev_map failed; negative map\n");
 532 #endif
 533         return -1;
 534     }
 535
 536     if (node < 0)
 537         node = ((unsigned long)~0) >> 1;
 538
 539     --node;
 540     bit = NUMBERTOBIT(node);
 541     x = NUMBERTOINDEX(node);
 542     page = NUMBERTOPAGE(node);
 543     bit = 1L << bit;
 544     best = -1;
 545     lowest = 0;
 546     for (map = MAP(parm); map; map = map->m_next)
 547         if (map->m_page <= page && (!lowest || lowest->m_page < map->m_page)) {
 548             i = MDATA - 1;
 549             mask = ~0;
 550             if (page == map->m_page)
 551                 i = x, mask = (bit << 1) - 1;
 552             for (; i >= 0; --i, mask = ~0)
 553                 if (map->m_data[i] & mask)
 554                     break;
 555             if (i >= 0) {
 556                 for (bn = (1 << LSHIFT) - 1; bn >= 0; --bn)
 557                     if (map->m_data[i] & mask & (1L << bn)) {
 558                         break;
 559                     }
 560 #ifdef MAP_DEBUG
 561                 if (Aflag) {
 562                     if (bn < 0) {
 563                         printf
 564                             ("prev_map: botch; pageno %d index %d data %#lx mask %#lx x,bit %d,%#lx\n",
 565                              map->m_page, i, map->m_data[i], mask, x, bit);
 566                         continue;
 567                     }
 568                 }
 569 #endif
 570                 best = bn + ((i + ((map->m_page) << MSHIFT)
 571                              ) << LSHIFT);
 572                 lowest = map;
 573             }
 574         }
 575 #ifdef MAP_DEBUG
 576     if (Aflag) {
 577         printf(" -> %d\n", best);
 578         if (best >= 0 && !in_map(parm, best)) {
 579             printf("prev_map: botch; %d not in map\n", best);
 580             return -1;
 581         }
 582     }
 583 #endif
 584     return best;
 585 }
 586
 587 long
 588 last_map(struct map *parm)
 589 {
 590     return prev_map(parm, 0x7fffffff);
 591 }
 592
 593 struct map *
 594 negative_map(struct map *map)
 595 {
 596     return (struct map *)NEGMAP(map);
 597 }
 598
 599 struct map *
 600 bic_map(struct map *mp1, struct map *mp2)
 601 {
 602 #ifdef MAP_DEBUG
 603     if (Mflag) {
 604         printf("Bic maps");
 605         print_map(mp1);
 606         printf(" minus");
 607         print_map(mp2);
 608     }
 609 #endif
 610     mp1 = and_map(mp1, NOT_MAP(mp2));
 611 #ifdef MAP_DEBUG
 612     if (Mflag) {
 613         printf(" ->");
 614         print_map(mp1);
 615         printf("\n");
 616     }
 617 #endif
 618     return mp1;
 619 }
 620
 621 #ifdef PRINT_MAP_ERROR
 622 void
 623 print_map(struct map *parm)
 624 {
 625     struct bitmap *map;
 626     int i, j;
 627     int bitno, firstbitno, lastbitno;
 628     if (NEGMAP(parm)) {
 629         printf(" NOT");
 630     }
 631     map = MAP(parm);
 632     if (!map)
 633         printf(" nil(%lx)", parm);
 634     else
 635         printf(" %lx", parm);
 636     lastbitno = -100;
 637     firstbitno = -100;
 638     for (; map; map = map->m_next)
 639         for (i = 0; i < MDATA; ++i)
 640             if (map->m_data[i])
 641                 for (j = 0; j < (1 << LSHIFT); ++j) {
 642                     bitno =
 643                         j + (i << LSHIFT) +
 644                         ((map->m_page) << (LSHIFT + MSHIFT));
 645                     if (map->m_data[i] & (1 << j)) {
 646                         if (bitno == lastbitno + 1) {
 647                             ++lastbitno;
 648                             continue;
 649                         }
 650                         if (bitno != (lastbitno + 1)) {
 651                             if (firstbitno >= 0 && firstbitno != lastbitno)
 652                                 printf("-%d", lastbitno);
 653                             firstbitno = -100;
 654                         }
 655                         printf(" %d", bitno);
 656                         firstbitno = lastbitno = bitno;
 657                     } else {
 658                         if (firstbitno >= 0 && firstbitno != lastbitno)
 659                             printf("-%d", lastbitno);
 660                         firstbitno = -100;
 661                     }
 662                 }
 663     if (firstbitno >= 0 && firstbitno != lastbitno)
 664         printf("-%d", lastbitno);
 665 }
 666 #endif
 667
 668 #ifdef NEED_READ_WRITE
 669 struct map *
 670 read_map(int (*f) (), char *arg)
 671 {
 672     struct bitmap *map, *result, **mp;
 673     int page;
 674     int bitno, lastno, thisno, prevno;
 675     int i, j;
 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             bzero((char *)map->m_data, 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) (), 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