static uint32_t linearCheck()

in hfs/btree.c [267:375]
84 lines of code
17 McCabe index (conditional complexity)

static uint32_t linearCheck(uint32_t* heightTable, unsigned char* map, BTree* tree, uint32_t *errCount) {
  uint8_t i;
  uint8_t j;
  uint32_t node;
  
  uint32_t count;
  uint32_t leafRecords;
  
  BTNodeDescriptor* descriptor;
  
  uint32_t prevNode;
  
  off_t recordOffset;
  BTKey* key;
  BTKey* previousKey;
  
  count = 0;
  
  leafRecords = 0;
  
  for(i = 0; i <= tree->headerRec->treeDepth; i++) {
    node = heightTable[i];
    if(node != 0) {
      descriptor = readBTNodeDescriptor(node, tree);
      while(descriptor->bLink != 0) {
        node = descriptor->bLink;
        free(descriptor);
        descriptor = readBTNodeDescriptor(node, tree);
      }
      free(descriptor);
      
      prevNode = 0;
      previousKey = NULL;
      
      if(i == 1) {
        if(node != tree->headerRec->firstLeafNode) {
          printf("BTREE CONSISTENCY ERROR: First leaf node (%d) is not correct. Should be: %d\n", tree->headerRec->firstLeafNode, node);
          (*errCount)++;
        }
      }
      
      while(node != 0) {
        descriptor = readBTNodeDescriptor(node, tree);
        if(descriptor->bLink != prevNode) {
          printf("BTREE CONSISTENCY ERROR: Node %d is not properly linked with previous node %d\n", node, prevNode);
          (*errCount)++;
        }
        
        if(descriptor->height != i) {
          printf("BTREE CONSISTENCY ERROR: Node %d (%d) is not properly linked with nodes of the same height %d\n", node, descriptor->height, i);
          (*errCount)++;
        }
        
        if((map[node / 8] & (1 << (7 - (node % 8)))) == 0) {
          printf("BTREE CONSISTENCY ERROR: Node %d not marked allocated\n", node);
          (*errCount)++;
        }
        
        /*if(descriptor->kind == kBTIndexNode && descriptor->numRecords < 2) {
          printf("BTREE CONSISTENCY ERROR: Node %d does not have at least two children\n", node);
          (*errCount)++;
        }*/
        
        for(j = 0; j < descriptor->numRecords; j++) {
          recordOffset = getRecordOffset(j, node, tree);
          key = READ_KEY(tree, recordOffset, tree->io);
          if(previousKey != NULL) {
            if(COMPARE(tree, key, previousKey) < 0) {
              printf("BTREE CONSISTENCY ERROR: Ordering not preserved during linear check for record %d node %d: ", j, node);
              (*errCount)++;
              tree->keyPrint(previousKey);
              printf(" < ");
              tree->keyPrint(key);
              printf("\n");
            }
            free(previousKey);
          }
          
          if(i == 1) {
            leafRecords++;
          }
          previousKey = key;
        }
        
        count++;
        
        prevNode = node;
        node = descriptor->fLink;
        free(descriptor);
      }
      
      if(i == 1) {
        if(prevNode != tree->headerRec->lastLeafNode) {
          printf("BTREE CONSISTENCY ERROR: Last leaf node (%d) is not correct. Should be: %d\n", tree->headerRec->lastLeafNode, node);
          (*errCount)++;
        }
      }
      
      free(previousKey);
    }
  }
  
  if(leafRecords != tree->headerRec->leafRecords) {
    printf("BTREE CONSISTENCY ERROR: leafRecords (%d) is not correct. Should be: %d\n", tree->headerRec->leafRecords, leafRecords);
    (*errCount)++;
  }
  
  return count;
}