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