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