static uint32_t removeRecord()

in hfs/btree.c [1374:1540]
130 lines of code
22 McCabe index (conditional complexity)

static uint32_t removeRecord(BTree* tree, uint32_t root, BTKey* searchKey, int* callAgain, int* gone) {
  BTNodeDescriptor* descriptor;
  int length;
  int i;
  int res;
  
  uint32_t newNode;
  uint32_t nodeToTraverse;
  uint32_t newNodeBigEndian;
  
  BTKey* key;
  off_t recordOffset;
  off_t recordDataOffset;
  off_t lastRecordDataOffset;
  
  int childGone;
  int checkForChangedKey  ;
  
  size_t freeSpace;
  
  descriptor = readBTNodeDescriptor(root, tree);
  
  freeSpace = getFreeSpace(root, descriptor, tree);
  
  nodeToTraverse = 0;
  lastRecordDataOffset = 0;
  newNode = 0;
  
  (*gone) = FALSE;
  checkForChangedKey = FALSE;
    
  for(i = 0; i < descriptor->numRecords; i++) {
    recordOffset = getRecordOffset(i, root, tree);
    key = READ_KEY(tree, recordOffset, tree->io);
    recordDataOffset = recordOffset + key->keyLength + sizeof(key->keyLength);
    
    res = COMPARE(tree, key, searchKey);
    if(res == 0) {
      free(key);
      
      if(descriptor->kind == kBTLeafNode) {
        if(i != (descriptor->numRecords - 1)) {
          length = getRecordOffset(i + 1, root, tree) - recordOffset;
          moveRecordsDown(tree, descriptor, i + 1, root, -length, -1);
        } // don't need to do that if we're the last record, because our old offset pointer will be the new free space pointer
               
        descriptor->numRecords--;
        tree->headerRec->leafRecords--;
        ASSERT(writeBTNodeDescriptor(descriptor, root, tree), "writeBTNodeDescriptor");
        ASSERT(writeBTHeaderRec(tree), "writeBTHeaderRec");
        
        if(descriptor->numRecords >= 1) {
          free(descriptor);
          return 0;
        } else {
          free(descriptor);
          removeNode(tree, root);
          (*gone) = TRUE;
          return 0;
        }
      } else {
        nodeToTraverse = getNodeNumberFromPointerRecord(recordDataOffset, tree->io);
        checkForChangedKey = TRUE;
        break;
      }
    } else if(res > 0) {
      free(key);
      
      if(lastRecordDataOffset == 0 || descriptor->kind == kBTLeafNode) {
        // not found;
        free(descriptor);
        return 0;
      } else {
        nodeToTraverse = getNodeNumberFromPointerRecord(lastRecordDataOffset, tree->io);
        break;
      }
    }
    
    lastRecordDataOffset = recordDataOffset;
    
    free(key);
  }
  
  if(nodeToTraverse == 0) {
    nodeToTraverse = getNodeNumberFromPointerRecord(lastRecordDataOffset, tree->io);
  }
  
  if(i == descriptor->numRecords) {
    i = descriptor->numRecords - 1;
  }
  
  newNode = removeRecord(tree, nodeToTraverse, searchKey, callAgain, &childGone);
  
  if(childGone) {
    if(i != (descriptor->numRecords - 1)) {
      length = getRecordOffset(i + 1, root, tree) - recordOffset;
      moveRecordsDown(tree, descriptor, i + 1, root, -length, -1);
    } // don't need to do that if we're the last record, because our old offset pointer will be the new free space pointer
           
    descriptor->numRecords--;
    ASSERT(writeBTNodeDescriptor(descriptor, root, tree), "writeBTNodeDescriptor");
  } else {
    if(checkForChangedKey) {
      // we will remove the first item in the child node, so our index has to change
      
      key = READ_KEY(tree, getRecordOffset(0, nodeToTraverse, tree), tree->io);
      
      if(searchKey->keyLength != key->keyLength) {
        if(key->keyLength > searchKey->keyLength && freeSpace < (key->keyLength - searchKey->keyLength)) {
          // very unlikely. We need to split this node before we can resize the key of this index. Do that first, and tell them to call again.
          *callAgain = TRUE;
          return splitNode(root, descriptor, tree);
        }
        
        moveRecordsDown(tree, descriptor, i + 1, root, key->keyLength - searchKey->keyLength, 0);
      }
      
      ASSERT(WRITE_KEY(tree, recordOffset, key, tree->io), "WRITE_KEY");
      FLIPENDIAN(nodeToTraverse);
      ASSERT(WRITE(tree->io, recordOffset + sizeof(uint16_t) + key->keyLength, sizeof(uint32_t), &nodeToTraverse), "WRITE");
      FLIPENDIAN(nodeToTraverse);
      
      free(key);
    }
  }
  
  if(newNode == 0) {
    if(descriptor->numRecords == 0) {
      removeNode(tree, root);
      (*gone) = TRUE;
    }
    
    free(descriptor);
    return 0;
  } else {
    newNodeBigEndian = newNode;
    key = READ_KEY(tree, newNode * tree->headerRec->nodeSize + 14, tree->io);
    FLIPENDIAN(newNodeBigEndian);
    
    if(freeSpace < (sizeof(key->keyLength) + key->keyLength + sizeof(newNodeBigEndian) + sizeof(uint16_t))) {
      newNode = splitNode(root, descriptor, tree);
      
      if(i < descriptor->numRecords) {
        doAddRecord(tree, root, key, sizeof(newNodeBigEndian), (unsigned char*)(&newNodeBigEndian));
      } else {
        doAddRecord(tree, newNode, key, sizeof(newNodeBigEndian), (unsigned char*)(&newNodeBigEndian));
      }
      
      if(descriptor->numRecords == 0) {
        removeNode(tree, root);
        (*gone) = TRUE;
      }
      
      free(key);
      free(descriptor);
      return newNode;
    } else {
      doAddRecord(tree, root, key, sizeof(newNodeBigEndian), (unsigned char*)(&newNodeBigEndian));
           
      free(key);
      free(descriptor);
      return 0;
    }
  }
  
  return FALSE;
}