static uint32_t traverseNode()

in hfs/btree.c [377:527]
117 lines of code
26 McCabe index (conditional complexity)

static uint32_t traverseNode(uint32_t nodeNum, BTree* tree, unsigned char* map, int parentHeight, BTKey** firstKey, BTKey** lastKey,
                                  uint32_t* heightTable, uint32_t* errCount, int displayTree) {
  BTNodeDescriptor* descriptor;
  BTKey* key;
  BTKey* previousKey;
  BTKey* retFirstKey;
  BTKey* retLastKey;
  int i, j;
  
  int res;
  
  uint32_t count;
  
  off_t recordOffset;
  off_t recordDataOffset;
  
  off_t lastrecordDataOffset;
  
  descriptor = readBTNodeDescriptor(nodeNum, tree);
  
  previousKey = NULL;
  
  count = 1;
  
  if(displayTree) {
    for(i = 0; i < descriptor->height; i++) {
      printf("  ");
    }
  }
  
  if(descriptor->kind == kBTLeafNode) {
    if(displayTree)
      printf("Leaf %d: %d", nodeNum, descriptor->numRecords);
    
    if(descriptor->height != 1) {
      printf("BTREE CONSISTENCY ERROR: Leaf node %d does not have height 1\n", nodeNum); fflush(stdout);
      (*errCount)++;
    }    
  } else if(descriptor->kind == kBTIndexNode) {
    if(displayTree)
      printf("Index %d: %d", nodeNum, descriptor->numRecords);

  } else {
    printf("BTREE CONSISTENCY ERROR: Unexpected node %d has kind %d\n", nodeNum, descriptor->kind); fflush(stdout);
    (*errCount)++;
  }
  
  if(displayTree) {
    printf("\n"); fflush(stdout);
  }
  
  if((map[nodeNum / 8] & (1 << (7 - (nodeNum % 8)))) == 0) {
    printf("BTREE CONSISTENCY ERROR: Node %d not marked allocated\n", nodeNum); fflush(stdout);
    (*errCount)++;
  }
  
  if(nodeNum == tree->headerRec->rootNode) {
    if(descriptor->height != tree->headerRec->treeDepth) {
      printf("BTREE CONSISTENCY ERROR: Root node %d (%d) does not have the proper height (%d)\n", nodeNum,
                    descriptor->height, tree->headerRec->treeDepth); fflush(stdout);
      (*errCount)++;
    }
  } else {
    if(descriptor->height != (parentHeight - 1)) {
      printf("BTREE CONSISTENCY ERROR: Node %d does not have the proper height\n", nodeNum); fflush(stdout);
      (*errCount)++;
    }
  }
  
  /*if(descriptor->kind == kBTIndexNode && descriptor->numRecords < 2) {
    printf("BTREE CONSISTENCY ERROR: Node %d does not have at least two children\n", nodeNum);
    (*errCount)++;
  }*/
  
  heightTable[descriptor->height] = nodeNum;
  lastrecordDataOffset = 0;
   
  for(i = 0; i < descriptor->numRecords; i++) {
    recordOffset = getRecordOffset(i, nodeNum, tree);
    key = READ_KEY(tree, recordOffset, tree->io);
    recordDataOffset = recordOffset + key->keyLength + sizeof(key->keyLength);
    
    if((recordDataOffset - (nodeNum * tree->headerRec->nodeSize)) > (tree->headerRec->nodeSize - (sizeof(uint16_t) * (descriptor->numRecords + 1)))) {
      printf("BTREE CONSISTENCY ERROR: Record data extends past offsets in node %d record %d\n", nodeNum, i); fflush(stdout);
      (*errCount)++;
    }

    if(i == 0) {
      *firstKey = READ_KEY(tree, recordOffset, tree->io);
    }
    
    if(i == (descriptor->numRecords - 1)) {
      *lastKey = READ_KEY(tree, recordOffset, tree->io);
    }
    
    if(previousKey != NULL) {
      res = COMPARE(tree, key, previousKey);
      if(res < 0) {
        printf("BTREE CONSISTENCY ERROR(traverse): Ordering between records within node not preserved in record %d node %d for ", i, nodeNum);
        (*errCount)++;
        tree->keyPrint(previousKey);
        printf(" < ");
        tree->keyPrint(key);
        printf("\n"); fflush(stdout);
      }
      free(previousKey);
      previousKey = NULL;
    }
    
    if(displayTree) {
      for(j = 0; j < (descriptor->height - 1); j++) {
        printf("  ");
      }
      tree->keyPrint(key);
      printf("\n");
    }
    
    if(descriptor->kind == kBTIndexNode) {
      count += traverseNode(getNodeNumberFromPointerRecord(recordDataOffset, tree->io),
                              tree, map, descriptor->height, &retFirstKey, &retLastKey, heightTable, errCount, displayTree);
                              
      if(COMPARE(tree, retFirstKey, key) != 0) {
        printf("BTREE CONSISTENCY ERROR: Index node key does not match first key in record %d node %d\n", i, nodeNum); fflush(stdout);
        (*errCount)++;
      }
      if(COMPARE(tree, retLastKey, key) < 0) {
        printf("BTREE CONSISTENCY ERROR: Last key is less than the index node key in record %d node %d\n", i, nodeNum); fflush(stdout);
        (*errCount)++;
      }
      free(retFirstKey);
      free(key);
      previousKey = retLastKey;
    } else {
      previousKey = key;
    }
    
    if(recordOffset < lastrecordDataOffset) {
      printf("BTREE CONSISTENCY ERROR: Record offsets are not in order in node %d starting at record %d\n", nodeNum, i); fflush(stdout);
      (*errCount)++;
    }
    
    lastrecordDataOffset = recordDataOffset;
  }
  
  if(previousKey != NULL) free(previousKey);

  free(descriptor);
  
  return count;
  
}