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