Lines Matching defs:node
31 Contains: Single-node operations for the BTree Module.
62 macro. Only call CheckNode if the node came from disk.
67 <HFS3> 2/19/97 djb Changes to support big node cache.
76 that CheckNode failed if the node is all zeroes. This can happen
77 if the hint case if the fetched node has been deallocated
85 <16> 1/31/95 prp GetBlockProc interface uses a 64 bit node number.
95 <8> 5/21/93 gs Maintain statistical counters on Get/Release node routines.
115 // GetNode - Call FS Agent to get node
116 // GetNewNode - Call FS Agent to get a new node
117 // ReleaseNode - Call FS Agent to release node obtained by GetNode.
118 // UpdateNode - Mark a node as dirty and call FS Agent to release it.
120 // ClearNode - Clear a node to all zeroes.
122 // InsertRecord - Inserts a record into a BTree node.
123 // InsertKeyRecord - Inserts a key and record pair into a BTree node.
124 // DeleteRecord - Deletes a record from a BTree node.
129 // GetNodeDataSize - Return the amount of space used for data in the node.
130 // GetNodeFreeSize - Return the amount of free space in the node.
136 // InsertOffset - Inserts a new offset into a node.
137 // DeleteOffset - Deletes an offset from a node.
146 NodeDescPtr node,
150 NodeDescPtr node,
154 NodeDescPtr node,
159 NodeDescPtr node,
165 #define GetRecordOffset(btreePtr,node,index) (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize))
170 static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber);
178 Routine: GetNode - Call FS Agent to get node
180 Function: Gets an existing BTree node from FS Agent and verifies it.
183 nodeNum - number of node to request
185 Output: nodePtr - pointer to beginning of node (nil if error)
210 nodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
244 Routine: GetNewNode - Call FS Agent to get a new node
246 Function: Gets a new BTree node from FS Agent and initializes it to an empty
250 nodeNum - number of node to request
252 Output: returnNodePtr - pointer to beginning of node (nil if error)
263 NodeDescPtr node;
268 //////////////////////// get buffer for new node ////////////////////////////
270 returnNodePtr->blockSize = btreePtr->nodeSize; // indicate the size of a node
287 ////////////////////////// initialize the node //////////////////////////////
289 node = returnNodePtr->buffer;
291 ClearNode (btreePtr, node); // clear the node
293 pos = (char *)node + btreePtr->nodeSize - 2; // find address of last offset
304 Routine: ReleaseNode - Call FS Agent to release node obtained by GetNode.
306 Function: Informs the FS Agent that a BTree node may be released.
309 nodeNum - number of node to release
345 Routine: TrashNode - Call FS Agent to release node obtained by GetNode, and
348 Function: Informs the FS Agent that a BTree node may be released and thrown away.
351 nodeNum - number of node to release
386 Routine: UpdateNode - Mark a node as dirty and call FS Agent to release it.
388 Function: Marks a BTree node dirty and informs the FS Agent that it may be released.
391 nodeNum - number of node to release
392 transactionID - ID of transaction this node update is a part of
435 static void PrintNode(const NodeDescPtr node, u_int16_t nodeSize, u_int32_t nodeNumber)
444 PRINTIT("Dump of B-tree node #%ld ($%08lX)\n", nodeNumber, nodeNumber);
447 lp = (u_int32_t*) node;
458 Routine: ClearNode - Clear a node to all zeroes.
460 Function: Writes zeroes from beginning of node for nodeSize bytes.
463 node - pointer to node to clear
468 void ClearNode (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
470 ClearMemory( node, btreePtr->nodeSize );
475 Routine: InsertRecord - Inserts a record into a BTree node.
482 node - pointer to node to insert the record
491 NodeDescPtr node,
503 //// will new record fit in node?
505 freeSpace = GetNodeFreeSize (btreePtr, node);
515 indexOffset = GetRecordOffset (btreePtr, node, index);
516 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
518 src = ((Ptr) node) + indexOffset;
527 InsertOffset (btreePtr, node, index, recSize);
532 dst = ((Ptr) node) + indexOffset;
542 Routine: InsertKeyRecord - Inserts a record into a BTree node.
549 node - pointer to node to insert the record
561 NodeDescPtr node,
589 //// will new record fit in node?
591 freeSpace = GetNodeFreeSize (btreePtr, node);
601 indexOffset = GetRecordOffset (btreePtr, node, index);
602 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
604 src = ((u_int8_t *) node) + indexOffset;
613 InsertOffset (btreePtr, node, index, keySize + recSize);
618 dst = ((u_int8_t *) node) + indexOffset;
644 dst = ((u_int8_t *) node) + indexOffset + keySize;
654 Routine: DeleteRecord - Deletes a record from a BTree node.
659 node - pointer to node to insert the record
666 NodeDescPtr node,
677 indexOffset = GetRecordOffset (btreePtr, node, index);
678 nextOffset = GetRecordOffset (btreePtr, node, index + 1);
679 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
681 src = ((Ptr) node) + nextOffset;
682 dst = ((Ptr) node) + indexOffset;
688 DeleteOffset (btreePtr, node, index);
692 ClearMemory(GetRecordAddress(btreePtr, node, node->numRecords), bytesToMove);
709 node - pointer to node that contains the record
715 false - key did not match anything in node (index = insert index)
719 NodeDescPtr node,
732 upperBound = node->numRecords - 1;
733 offset = (u_int16_t *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - kOffsetSize);
738 trialKey = (KeyPtr) ((u_int8_t *)node + *(offset - index));
766 node - pointer to node that contains the record
777 NodeDescPtr node,
790 if (index >= node->numRecords)
794 offset = GetRecordOffset (btreePtr, node, index);
795 *keyPtr = (KeyPtr) ((Ptr)node + offset);
803 *dataPtr = (u_int8_t *) node + offset;
806 nextOffset = GetRecordOffset (btreePtr, node, index + 1);
816 Routine: GetNodeDataSize - Return the amount of space used for data in the node.
818 Function: Gets the size of the data currently contained in a node, excluding
819 the node header. (record data + offset overhead)
822 node - pointer to node that contains the record
824 Result: - number of bytes used for data and offsets in the node.
827 u_int16_t GetNodeDataSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
831 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords);
833 return freeOffset + (node->numRecords << 1) - sizeof (BTNodeDescriptor);
840 Routine: GetNodeFreeSize - Return the amount of free space in the node.
845 node - pointer to node that contains the record
847 Result: - number of bytes of free space in the node.
850 u_int16_t GetNodeFreeSize (BTreeControlBlockPtr btreePtr, NodeDescPtr node )
854 freeOffset = GetRecordOffset (btreePtr, node, node->numRecords); //�� inline?
856 return btreePtr->nodeSize - freeOffset - (node->numRecords << 1) - kOffsetSize;
868 node - pointer to node that contains the record
871 Result: - offset (in bytes) from beginning of node of record specified by index
876 NodeDescPtr node,
882 pos = (u_int8_t *)node + btreePtr->nodeSize - (index << 1) - kOffsetSize;
897 node - pointer to node that contains the record
905 NodeDescPtr node,
910 pos = (u_int8_t *)node + GetRecordOffset (btreePtr, node, index);
927 node - pointer to node that contains the record
934 NodeDescPtr node,
939 pos = (u_int16_t *) ((Ptr)node + btreePtr->nodeSize - (index << 1) - kOffsetSize);
952 node - pointer to node that contains the record
959 NodeDescPtr node,
964 pos = (Ptr)node + btreePtr->nodeSize - (index << 1) -2;
972 Routine: GetChildNodeNum - Return child node number from index record "index".
976 Assumes: The node is an Index Node.
980 node - pointer to node that contains the record
981 index - record to obtain child node number from
983 Result: - child node number from record "index".
1005 The number of records contained in the node is also incremented.
1008 node - pointer to node
1016 NodeDescPtr node,
1023 src = GetOffsetAddress (btreePtr, node, node->numRecords); // point to free offset
1025 numOffsets = node->numRecords++ - index; // subtract index & postincrement
1040 The number of records contained in the node is also decremented.
1043 node - pointer to node
1050 NodeDescPtr node,
1057 dst = GetOffsetAddress (btreePtr, node, index);
1060 numOffsets = --node->numRecords - index; // predecrement numRecords & subtract index