| 1 | // Copyright (C) 2000 - 2002 Hewlett-Packard Company |
| 2 | // |
| 3 | // This program is free software; you can redistribute it and/or modify it |
| 4 | // under the term of the GNU Lesser General Public License as published by the |
| 5 | // Free Software Foundation; either version 2 of the License, or (at your |
| 6 | // option) any later version. |
| 7 | // |
| 8 | // This program is distributed in the hope that it will be useful, but WITHOUT |
| 9 | // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 10 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License |
| 11 | // for more details. |
| 12 | // |
| 13 | // You should have received a copy of the GNU Lesser General Public License |
| 14 | // along with this program; if not, write to the Free Software Foundation, |
| 15 | // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 16 | // _________________ |
| 17 | |
| 18 | // @(#) $Revision: 4.17 $ $Source: /judy/src/JudyCommon/JudyInsertBranch.c $ |
| 19 | |
| 20 | // BranchL insertion functions for Judy1 and JudyL. |
| 21 | // Compile with one of -DJUDY1 or -DJUDYL. |
| 22 | |
| 23 | #if (! (defined(JUDY1) || defined(JUDYL))) |
| 24 | #error: One of -DJUDY1 or -DJUDYL must be specified. |
| 25 | #endif |
| 26 | |
| 27 | #ifdef JUDY1 |
| 28 | #include "Judy1.h" |
| 29 | #else |
| 30 | #include "JudyL.h" |
| 31 | #endif |
| 32 | |
| 33 | #include "JudyPrivate1L.h" |
| 34 | |
| 35 | extern int j__udyCreateBranchL(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t); |
| 36 | |
| 37 | |
| 38 | // **************************************************************************** |
| 39 | // __ J U D Y I N S E R T B R A N C H |
| 40 | // |
| 41 | // Insert 2-element BranchL in between Pjp and Pjp->jp_Addr. |
| 42 | // |
| 43 | // Return -1 if out of memory, otherwise return 1. |
| 44 | |
| 45 | FUNCTION int j__udyInsertBranch( |
| 46 | Pjp_t Pjp, // JP containing narrow pointer. |
| 47 | Word_t Index, // outlier to Pjp. |
| 48 | Word_t BranchLevel, // of what JP points to, mapped from JP type. |
| 49 | Pjpm_t Pjpm) // for global accounting. |
| 50 | { |
| 51 | jp_t JP2 [2]; |
| 52 | jp_t JP; |
| 53 | Pjp_t PjpNull; |
| 54 | Word_t XorExp; |
| 55 | Word_t Inew, Iold; |
| 56 | Word_t DCDMask; // initially for original BranchLevel. |
| 57 | int Ret; |
| 58 | uint8_t Exp2[2]; |
| 59 | uint8_t DecodeByteN, DecodeByteO; |
| 60 | |
| 61 | // Get the current mask for the DCD digits: |
| 62 | |
| 63 | DCDMask = cJU_DCDMASK(BranchLevel); |
| 64 | |
| 65 | // Obtain Dcd bits that differ between Index and JP, shifted so the |
| 66 | // digit for BranchLevel is the LSB: |
| 67 | |
| 68 | XorExp = ((Index ^ JU_JPDCDPOP0(Pjp)) & (cJU_ALLONES >> cJU_BITSPERBYTE)) |
| 69 | >> (BranchLevel * cJU_BITSPERBYTE); |
| 70 | assert(XorExp); // Index must be an outlier. |
| 71 | |
| 72 | // Count levels between object under narrow pointer and the level at which |
| 73 | // the outlier diverges from it, which is always at least initial |
| 74 | // BranchLevel + 1, to end up with the level (JP type) at which to insert |
| 75 | // the new intervening BranchL: |
| 76 | |
| 77 | do { ++BranchLevel; } while ((XorExp >>= cJU_BITSPERBYTE)); |
| 78 | assert((BranchLevel > 1) && (BranchLevel < cJU_ROOTSTATE)); |
| 79 | |
| 80 | // Get the MSB (highest digit) that differs between the old expanse and |
| 81 | // the new Index to insert: |
| 82 | |
| 83 | DecodeByteO = JU_DIGITATSTATE(JU_JPDCDPOP0(Pjp), BranchLevel); |
| 84 | DecodeByteN = JU_DIGITATSTATE(Index, BranchLevel); |
| 85 | |
| 86 | assert(DecodeByteO != DecodeByteN); |
| 87 | |
| 88 | // Determine sorted order for old expanse and new Index digits: |
| 89 | |
| 90 | if (DecodeByteN > DecodeByteO) { Iold = 0; Inew = 1; } |
| 91 | else { Iold = 1; Inew = 0; } |
| 92 | |
| 93 | // Copy old JP into staging area for new Branch |
| 94 | JP2 [Iold] = *Pjp; |
| 95 | Exp2[Iold] = DecodeByteO; |
| 96 | Exp2[Inew] = DecodeByteN; |
| 97 | |
| 98 | // Create a 2 Expanse Linear branch |
| 99 | // |
| 100 | // Note: Pjp->jp_Addr is set by j__udyCreateBranchL() |
| 101 | |
| 102 | Ret = j__udyCreateBranchL(Pjp, JP2, Exp2, 2, Pjpm); |
| 103 | if (Ret == -1) return(-1); |
| 104 | |
| 105 | // Get Pjp to the NULL of where to do insert |
| 106 | PjpNull = ((P_JBL(Pjp->jp_Addr))->jbl_jp) + Inew; |
| 107 | |
| 108 | // Convert to a cJU_JPIMMED_*_01 at the correct level: |
| 109 | // Build JP and set type below to: cJU_JPIMMED_X_01 |
| 110 | JU_JPSETADT(PjpNull, 0, Index, cJU_JPIMMED_1_01 - 2 + BranchLevel); |
| 111 | |
| 112 | // Return pointer to Value area in cJU_JPIMMED_X_01 |
| 113 | JUDYLCODE(Pjpm->jpm_PValue = (Pjv_t) PjpNull;) |
| 114 | |
| 115 | // The old JP now points to a BranchL that is at higher level. Therefore |
| 116 | // it contains excess DCD bits (in the least significant position) that |
| 117 | // must be removed (zeroed); that is, they become part of the Pop0 |
| 118 | // subfield. Note that the remaining (lower) bytes in the Pop0 field do |
| 119 | // not change. |
| 120 | // |
| 121 | // Take from the old DCDMask, which went "down" to a lower BranchLevel, |
| 122 | // and zero any high bits that are still in the mask at the new, higher |
| 123 | // BranchLevel; then use this mask to zero the bits in jp_DcdPopO: |
| 124 | |
| 125 | // Set old JP to a BranchL at correct level |
| 126 | |
| 127 | Pjp->jp_Type = cJU_JPBRANCH_L2 - 2 + BranchLevel; |
| 128 | DCDMask ^= cJU_DCDMASK(BranchLevel); |
| 129 | DCDMask = ~DCDMask & JU_JPDCDPOP0(Pjp); |
| 130 | JP = *Pjp; |
| 131 | JU_JPSETADT(Pjp, JP.jp_Addr, DCDMask, JP.jp_Type); |
| 132 | |
| 133 | return(1); |
| 134 | |
| 135 | } // j__udyInsertBranch() |