package km;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/* JADX INFO: Access modifiers changed from: package-private */
/* loaded from: classes3.dex */
public final class r extends AbstractMap implements Serializable {

    /* renamed from: x, reason: collision with root package name */
    private static final Comparator f25962x = new a();

    /* renamed from: p, reason: collision with root package name */
    Comparator f25963p;

    /* renamed from: q, reason: collision with root package name */
    g[] f25964q;

    /* renamed from: r, reason: collision with root package name */
    final g f25965r;

    /* renamed from: s, reason: collision with root package name */
    int f25966s;

    /* renamed from: t, reason: collision with root package name */
    int f25967t;

    /* renamed from: u, reason: collision with root package name */
    int f25968u;

    /* renamed from: v, reason: collision with root package name */
    private d f25969v;

    /* renamed from: w, reason: collision with root package name */
    private e f25970w;

    /* loaded from: classes3.dex */
    class a implements Comparator {
        a() {
        }

        @Override // java.util.Comparator
        /* renamed from: a, reason: merged with bridge method [inline-methods] */
        public int compare(Comparable comparable, Comparable comparable2) {
            return comparable.compareTo(comparable2);
        }
    }

    /* JADX INFO: Access modifiers changed from: package-private */
    /* loaded from: classes3.dex */
    public static final class b {

        /* renamed from: a, reason: collision with root package name */
        private g f25971a;

        /* renamed from: b, reason: collision with root package name */
        private int f25972b;

        /* renamed from: c, reason: collision with root package name */
        private int f25973c;

        /* renamed from: d, reason: collision with root package name */
        private int f25974d;

        b() {
        }

        void a(g gVar) {
            gVar.f25986r = null;
            gVar.f25984p = null;
            gVar.f25985q = null;
            gVar.f25992x = 1;
            int i10 = this.f25972b;
            if (i10 > 0) {
                int i11 = this.f25974d;
                if ((i11 & 1) == 0) {
                    this.f25974d = i11 + 1;
                    this.f25972b = i10 - 1;
                    this.f25973c++;
                }
            }
            gVar.f25984p = this.f25971a;
            this.f25971a = gVar;
            int i12 = this.f25974d + 1;
            this.f25974d = i12;
            int i13 = this.f25972b;
            if (i13 > 0 && (i12 & 1) == 0) {
                this.f25974d = i12 + 1;
                this.f25972b = i13 - 1;
                this.f25973c++;
            }
            int i14 = 4;
            while (true) {
                int i15 = i14 - 1;
                if ((this.f25974d & i15) != i15) {
                    return;
                }
                int i16 = this.f25973c;
                if (i16 == 0) {
                    g gVar2 = this.f25971a;
                    g gVar3 = gVar2.f25984p;
                    g gVar4 = gVar3.f25984p;
                    gVar3.f25984p = gVar4.f25984p;
                    this.f25971a = gVar3;
                    gVar3.f25985q = gVar4;
                    gVar3.f25986r = gVar2;
                    gVar3.f25992x = gVar2.f25992x + 1;
                    gVar4.f25984p = gVar3;
                    gVar2.f25984p = gVar3;
                } else if (i16 == 1) {
                    g gVar5 = this.f25971a;
                    g gVar6 = gVar5.f25984p;
                    this.f25971a = gVar6;
                    gVar6.f25986r = gVar5;
                    gVar6.f25992x = gVar5.f25992x + 1;
                    gVar5.f25984p = gVar6;
                    this.f25973c = 0;
                } else if (i16 == 2) {
                    this.f25973c = 0;
                }
                i14 *= 2;
            }
        }

        void b(int i10) {
            this.f25972b = ((Integer.highestOneBit(i10) * 2) - 1) - i10;
            this.f25974d = 0;
            this.f25973c = 0;
            this.f25971a = null;
        }

        g c() {
            g gVar = this.f25971a;
            if (gVar.f25984p == null) {
                return gVar;
            }
            throw new IllegalStateException();
        }
    }

    /* JADX INFO: Access modifiers changed from: package-private */
    /* loaded from: classes3.dex */
    public static class c {

        /* renamed from: a, reason: collision with root package name */
        private g f25975a;

        c() {
        }

        public g a() {
            g gVar = this.f25975a;
            if (gVar == null) {
                return null;
            }
            g gVar2 = gVar.f25984p;
            gVar.f25984p = null;
            g gVar3 = gVar.f25986r;
            while (true) {
                g gVar4 = gVar2;
                gVar2 = gVar3;
                if (gVar2 == null) {
                    this.f25975a = gVar4;
                    return gVar;
                }
                gVar2.f25984p = gVar4;
                gVar3 = gVar2.f25985q;
            }
        }

        void b(g gVar) {
            g gVar2 = null;
            while (gVar != null) {
                gVar.f25984p = gVar2;
                gVar2 = gVar;
                gVar = gVar.f25985q;
            }
            this.f25975a = gVar2;
        }
    }

    /* loaded from: classes3.dex */
    final class d extends AbstractSet {

        /* loaded from: classes3.dex */
        class a extends f {
            a() {
                super();
            }

            @Override // java.util.Iterator
            /* renamed from: b, reason: merged with bridge method [inline-methods] */
            public Map.Entry next() {
                return a();
            }
        }

        d() {
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public void clear() {
            r.this.clear();
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public boolean contains(Object obj) {
            return (obj instanceof Map.Entry) && r.this.e((Map.Entry) obj) != null;
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable, java.util.Set
        public Iterator iterator() {
            return new a();
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public boolean remove(Object obj) {
            g e10;
            if (!(obj instanceof Map.Entry) || (e10 = r.this.e((Map.Entry) obj)) == null) {
                return false;
            }
            r.this.h(e10, true);
            return true;
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public int size() {
            return r.this.f25966s;
        }
    }

    /* loaded from: classes3.dex */
    final class e extends AbstractSet {

        /* loaded from: classes3.dex */
        class a extends f {
            a() {
                super();
            }

            @Override // java.util.Iterator
            public Object next() {
                return a().f25989u;
            }
        }

        e() {
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public void clear() {
            r.this.clear();
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public boolean contains(Object obj) {
            return r.this.containsKey(obj);
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable, java.util.Set
        public Iterator iterator() {
            return new a();
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public boolean remove(Object obj) {
            return r.this.j(obj) != null;
        }

        @Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
        public int size() {
            return r.this.f25966s;
        }
    }

    /* JADX INFO: Access modifiers changed from: package-private */
    /* loaded from: classes3.dex */
    public abstract class f implements Iterator {

        /* renamed from: p, reason: collision with root package name */
        g f25980p;

        /* renamed from: q, reason: collision with root package name */
        g f25981q = null;

        /* renamed from: r, reason: collision with root package name */
        int f25982r;

        f() {
            this.f25980p = r.this.f25965r.f25987s;
            this.f25982r = r.this.f25967t;
        }

        final g a() {
            g gVar = this.f25980p;
            r rVar = r.this;
            if (gVar == rVar.f25965r) {
                throw new NoSuchElementException();
            }
            if (rVar.f25967t != this.f25982r) {
                throw new ConcurrentModificationException();
            }
            this.f25980p = gVar.f25987s;
            this.f25981q = gVar;
            return gVar;
        }

        @Override // java.util.Iterator
        public final boolean hasNext() {
            return this.f25980p != r.this.f25965r;
        }

        @Override // java.util.Iterator
        public final void remove() {
            g gVar = this.f25981q;
            if (gVar == null) {
                throw new IllegalStateException();
            }
            r.this.h(gVar, true);
            this.f25981q = null;
            this.f25982r = r.this.f25967t;
        }
    }

    /* JADX INFO: Access modifiers changed from: package-private */
    public r() {
        this(null);
    }

    private void a() {
        g[] b10 = b(this.f25964q);
        this.f25964q = b10;
        this.f25968u = (b10.length / 2) + (b10.length / 4);
    }

    static g[] b(g[] gVarArr) {
        int length = gVarArr.length;
        g[] gVarArr2 = new g[length * 2];
        c cVar = new c();
        b bVar = new b();
        b bVar2 = new b();
        for (int i10 = 0; i10 < length; i10++) {
            g gVar = gVarArr[i10];
            if (gVar != null) {
                cVar.b(gVar);
                int i11 = 0;
                int i12 = 0;
                while (true) {
                    g a10 = cVar.a();
                    if (a10 == null) {
                        break;
                    }
                    if ((a10.f25990v & length) == 0) {
                        i11++;
                    } else {
                        i12++;
                    }
                }
                bVar.b(i11);
                bVar2.b(i12);
                cVar.b(gVar);
                while (true) {
                    g a11 = cVar.a();
                    if (a11 == null) {
                        break;
                    }
                    if ((a11.f25990v & length) == 0) {
                        bVar.a(a11);
                    } else {
                        bVar2.a(a11);
                    }
                }
                gVarArr2[i10] = i11 > 0 ? bVar.c() : null;
                gVarArr2[i10 + length] = i12 > 0 ? bVar2.c() : null;
            }
        }
        return gVarArr2;
    }

    private boolean c(Object obj, Object obj2) {
        return obj == obj2 || (obj != null && obj.equals(obj2));
    }

    private void g(g gVar, boolean z10) {
        while (gVar != null) {
            g gVar2 = gVar.f25985q;
            g gVar3 = gVar.f25986r;
            int i10 = gVar2 != null ? gVar2.f25992x : 0;
            int i11 = gVar3 != null ? gVar3.f25992x : 0;
            int i12 = i10 - i11;
            if (i12 == -2) {
                g gVar4 = gVar3.f25985q;
                g gVar5 = gVar3.f25986r;
                int i13 = (gVar4 != null ? gVar4.f25992x : 0) - (gVar5 != null ? gVar5.f25992x : 0);
                if (i13 == -1 || (i13 == 0 && !z10)) {
                    p(gVar);
                } else {
                    r(gVar3);
                    p(gVar);
                }
                if (z10) {
                    return;
                }
            } else if (i12 == 2) {
                g gVar6 = gVar2.f25985q;
                g gVar7 = gVar2.f25986r;
                int i14 = (gVar6 != null ? gVar6.f25992x : 0) - (gVar7 != null ? gVar7.f25992x : 0);
                if (i14 == 1 || (i14 == 0 && !z10)) {
                    r(gVar);
                } else {
                    p(gVar2);
                    r(gVar);
                }
                if (z10) {
                    return;
                }
            } else if (i12 == 0) {
                gVar.f25992x = i10 + 1;
                if (z10) {
                    return;
                }
            } else {
                gVar.f25992x = Math.max(i10, i11) + 1;
                if (!z10) {
                    return;
                }
            }
            gVar = gVar.f25984p;
        }
    }

    private void m(g gVar, g gVar2) {
        g gVar3 = gVar.f25984p;
        gVar.f25984p = null;
        if (gVar2 != null) {
            gVar2.f25984p = gVar3;
        }
        if (gVar3 == null) {
            int i10 = gVar.f25990v;
            this.f25964q[i10 & (r2.length - 1)] = gVar2;
        } else if (gVar3.f25985q == gVar) {
            gVar3.f25985q = gVar2;
        } else {
            gVar3.f25986r = gVar2;
        }
    }

    private void p(g gVar) {
        g gVar2 = gVar.f25985q;
        g gVar3 = gVar.f25986r;
        g gVar4 = gVar3.f25985q;
        g gVar5 = gVar3.f25986r;
        gVar.f25986r = gVar4;
        if (gVar4 != null) {
            gVar4.f25984p = gVar;
        }
        m(gVar, gVar3);
        gVar3.f25985q = gVar;
        gVar.f25984p = gVar3;
        int max = Math.max(gVar2 != null ? gVar2.f25992x : 0, gVar4 != null ? gVar4.f25992x : 0) + 1;
        gVar.f25992x = max;
        gVar3.f25992x = Math.max(max, gVar5 != null ? gVar5.f25992x : 0) + 1;
    }

    private void r(g gVar) {
        g gVar2 = gVar.f25985q;
        g gVar3 = gVar.f25986r;
        g gVar4 = gVar2.f25985q;
        g gVar5 = gVar2.f25986r;
        gVar.f25985q = gVar5;
        if (gVar5 != null) {
            gVar5.f25984p = gVar;
        }
        m(gVar, gVar2);
        gVar2.f25986r = gVar;
        gVar.f25984p = gVar2;
        int max = Math.max(gVar3 != null ? gVar3.f25992x : 0, gVar5 != null ? gVar5.f25992x : 0) + 1;
        gVar.f25992x = max;
        gVar2.f25992x = Math.max(max, gVar4 != null ? gVar4.f25992x : 0) + 1;
    }

    private static int t(int i10) {
        int i11 = i10 ^ ((i10 >>> 20) ^ (i10 >>> 12));
        return (i11 >>> 4) ^ ((i11 >>> 7) ^ i11);
    }

    @Override // java.util.AbstractMap, java.util.Map
    public void clear() {
        Arrays.fill(this.f25964q, (Object) null);
        this.f25966s = 0;
        this.f25967t++;
        g gVar = this.f25965r;
        g gVar2 = gVar.f25987s;
        while (gVar2 != gVar) {
            g gVar3 = gVar2.f25987s;
            gVar2.f25988t = null;
            gVar2.f25987s = null;
            gVar2 = gVar3;
        }
        gVar.f25988t = gVar;
        gVar.f25987s = gVar;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public boolean containsKey(Object obj) {
        return f(obj) != null;
    }

    g d(Object obj, boolean z10) {
        int i10;
        g gVar;
        Comparator comparator = this.f25963p;
        g[] gVarArr = this.f25964q;
        int t10 = t(obj.hashCode());
        int length = (gVarArr.length - 1) & t10;
        g gVar2 = gVarArr[length];
        if (gVar2 != null) {
            Comparable comparable = comparator == f25962x ? (Comparable) obj : null;
            while (true) {
                i10 = comparable != null ? comparable.compareTo(gVar2.f25989u) : comparator.compare(obj, gVar2.f25989u);
                if (i10 == 0) {
                    return gVar2;
                }
                g gVar3 = i10 < 0 ? gVar2.f25985q : gVar2.f25986r;
                if (gVar3 == null) {
                    break;
                }
                gVar2 = gVar3;
            }
        } else {
            i10 = 0;
        }
        g gVar4 = gVar2;
        int i11 = i10;
        if (!z10) {
            return null;
        }
        g gVar5 = this.f25965r;
        if (gVar4 != null) {
            gVar = new g(gVar4, obj, t10, gVar5, gVar5.f25988t);
            if (i11 < 0) {
                gVar4.f25985q = gVar;
            } else {
                gVar4.f25986r = gVar;
            }
            g(gVar4, true);
        } else {
            if (comparator == f25962x && !(obj instanceof Comparable)) {
                throw new ClassCastException(obj.getClass().getName() + " is not Comparable");
            }
            gVar = new g(gVar4, obj, t10, gVar5, gVar5.f25988t);
            gVarArr[length] = gVar;
        }
        int i12 = this.f25966s;
        this.f25966s = i12 + 1;
        if (i12 > this.f25968u) {
            a();
        }
        this.f25967t++;
        return gVar;
    }

    g e(Map.Entry entry) {
        g f10 = f(entry.getKey());
        if (f10 != null && c(f10.f25991w, entry.getValue())) {
            return f10;
        }
        return null;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public Set entrySet() {
        d dVar = this.f25969v;
        if (dVar != null) {
            return dVar;
        }
        d dVar2 = new d();
        this.f25969v = dVar2;
        return dVar2;
    }

    g f(Object obj) {
        if (obj == null) {
            return null;
        }
        try {
            return d(obj, false);
        } catch (ClassCastException unused) {
            return null;
        }
    }

    @Override // java.util.AbstractMap, java.util.Map
    public Object get(Object obj) {
        g f10 = f(obj);
        if (f10 != null) {
            return f10.f25991w;
        }
        return null;
    }

    void h(g gVar, boolean z10) {
        int i10;
        if (z10) {
            g gVar2 = gVar.f25988t;
            gVar2.f25987s = gVar.f25987s;
            gVar.f25987s.f25988t = gVar2;
            gVar.f25988t = null;
            gVar.f25987s = null;
        }
        g gVar3 = gVar.f25985q;
        g gVar4 = gVar.f25986r;
        g gVar5 = gVar.f25984p;
        int i11 = 0;
        if (gVar3 == null || gVar4 == null) {
            if (gVar3 != null) {
                m(gVar, gVar3);
                gVar.f25985q = null;
            } else if (gVar4 != null) {
                m(gVar, gVar4);
                gVar.f25986r = null;
            } else {
                m(gVar, null);
            }
            g(gVar5, false);
            this.f25966s--;
            this.f25967t++;
            return;
        }
        g b10 = gVar3.f25992x > gVar4.f25992x ? gVar3.b() : gVar4.a();
        h(b10, false);
        g gVar6 = gVar.f25985q;
        if (gVar6 != null) {
            i10 = gVar6.f25992x;
            b10.f25985q = gVar6;
            gVar6.f25984p = b10;
            gVar.f25985q = null;
        } else {
            i10 = 0;
        }
        g gVar7 = gVar.f25986r;
        if (gVar7 != null) {
            i11 = gVar7.f25992x;
            b10.f25986r = gVar7;
            gVar7.f25984p = b10;
            gVar.f25986r = null;
        }
        b10.f25992x = Math.max(i10, i11) + 1;
        m(gVar, b10);
    }

    g j(Object obj) {
        g f10 = f(obj);
        if (f10 != null) {
            h(f10, true);
        }
        return f10;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public Set keySet() {
        e eVar = this.f25970w;
        if (eVar != null) {
            return eVar;
        }
        e eVar2 = new e();
        this.f25970w = eVar2;
        return eVar2;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public Object put(Object obj, Object obj2) {
        if (obj == null) {
            throw new NullPointerException("key == null");
        }
        g d10 = d(obj, true);
        Object obj3 = d10.f25991w;
        d10.f25991w = obj2;
        return obj3;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public Object remove(Object obj) {
        g j10 = j(obj);
        if (j10 != null) {
            return j10.f25991w;
        }
        return null;
    }

    @Override // java.util.AbstractMap, java.util.Map
    public int size() {
        return this.f25966s;
    }

    r(Comparator comparator) {
        this.f25966s = 0;
        this.f25967t = 0;
        this.f25963p = comparator == null ? f25962x : comparator;
        this.f25965r = new g();
        g[] gVarArr = new g[16];
        this.f25964q = gVarArr;
        this.f25968u = (gVarArr.length / 2) + (gVarArr.length / 4);
    }

    /* JADX INFO: Access modifiers changed from: package-private */
    /* loaded from: classes3.dex */
    public static final class g implements Map.Entry {

        /* renamed from: p, reason: collision with root package name */
        g f25984p;

        /* renamed from: q, reason: collision with root package name */
        g f25985q;

        /* renamed from: r, reason: collision with root package name */
        g f25986r;

        /* renamed from: s, reason: collision with root package name */
        g f25987s;

        /* renamed from: t, reason: collision with root package name */
        g f25988t;

        /* renamed from: u, reason: collision with root package name */
        final Object f25989u;

        /* renamed from: v, reason: collision with root package name */
        final int f25990v;

        /* renamed from: w, reason: collision with root package name */
        Object f25991w;

        /* renamed from: x, reason: collision with root package name */
        int f25992x;

        g() {
            this.f25989u = null;
            this.f25990v = -1;
            this.f25988t = this;
            this.f25987s = this;
        }

        public g a() {
            g gVar = this.f25985q;
            while (true) {
                g gVar2 = gVar;
                g gVar3 = this;
                this = gVar2;
                if (this == null) {
                    return gVar3;
                }
                gVar = this.f25985q;
            }
        }

        public g b() {
            g gVar = this.f25986r;
            while (true) {
                g gVar2 = gVar;
                g gVar3 = this;
                this = gVar2;
                if (this == null) {
                    return gVar3;
                }
                gVar = this.f25986r;
            }
        }

        @Override // java.util.Map.Entry
        public boolean equals(Object obj) {
            if (!(obj instanceof Map.Entry)) {
                return false;
            }
            Map.Entry entry = (Map.Entry) obj;
            Object obj2 = this.f25989u;
            if (obj2 == null) {
                if (entry.getKey() != null) {
                    return false;
                }
            } else if (!obj2.equals(entry.getKey())) {
                return false;
            }
            Object obj3 = this.f25991w;
            if (obj3 == null) {
                if (entry.getValue() != null) {
                    return false;
                }
            } else if (!obj3.equals(entry.getValue())) {
                return false;
            }
            return true;
        }

        @Override // java.util.Map.Entry
        public Object getKey() {
            return this.f25989u;
        }

        @Override // java.util.Map.Entry
        public Object getValue() {
            return this.f25991w;
        }

        @Override // java.util.Map.Entry
        public int hashCode() {
            Object obj = this.f25989u;
            int hashCode = obj == null ? 0 : obj.hashCode();
            Object obj2 = this.f25991w;
            return hashCode ^ (obj2 != null ? obj2.hashCode() : 0);
        }

        @Override // java.util.Map.Entry
        public Object setValue(Object obj) {
            Object obj2 = this.f25991w;
            this.f25991w = obj;
            return obj2;
        }

        public String toString() {
            return this.f25989u + "=" + this.f25991w;
        }

        g(g gVar, Object obj, int i10, g gVar2, g gVar3) {
            this.f25984p = gVar;
            this.f25989u = obj;
            this.f25990v = i10;
            this.f25992x = 1;
            this.f25987s = gVar2;
            this.f25988t = gVar3;
            gVar3.f25987s = this;
            gVar2.f25988t = this;
        }
    }
}
