Merge "Reformat and remove STL reference from header"

7 files changed, 408 insertions, 126 deletions

diff --git a/cpu_ref/rsCpuScriptGroup2.cpp b/cpu_ref/rsCpuScriptGroup2.cpp
index 18c9f73b..80c46a03 100644
--- a/cpu_ref/rsCpuScriptGroup2.cpp
+++ b/cpu_ref/rsCpuScriptGroup2.cpp
@@ -31,7 +31,7 @@ const size_t DefaultKernelArgCount = 2;
 
 void groupRoot(const RsExpandKernelParams *kparams, uint32_t xstart,
                uint32_t xend, uint32_t outstep) {
-    const list<CPUClosure*>& closures = *(list<CPUClosure*>*)kparams->usr;
+    const List<CPUClosure*>& closures = *(List<CPUClosure*>*)kparams->usr;
     RsExpandKernelParams *mutable_kparams = (RsExpandKernelParams *)kparams;
     const void **oldIns  = kparams->ins;
     uint32_t *oldStrides = kparams->inEStrides;
@@ -45,7 +45,8 @@ void groupRoot(const RsExpandKernelParams *kparams, uint32_t xstart,
         auto in_iter = ins.begin();
         auto stride_iter = strides.begin();
 
-        for (const auto& arg : closure->mArgs) {
+        for (size_t i = 0; i < closure->mNumArg; i++) {
+            const void* arg = closure->mArgs[i];
             const Allocation* a = (const Allocation*)arg;
             const uint32_t eStride = a->mHal.state.elementSizeBytes;
             const uint8_t* ptr = (uint8_t*)(a->mHal.drvState.lod[0].mallocPtr) +
@@ -91,42 +92,39 @@ Batch::~Batch() {
     }
 }
 
-bool Batch::conflict(CPUClosure* closure) const {
+bool Batch::conflict(CPUClosure* cpuClosure) const {
     if (mClosures.empty()) {
         return false;
     }
 
-    if (closure->mClosure->mKernelID.get() == nullptr ||
+    const Closure* closure = cpuClosure->mClosure;
+
+    if (closure->mKernelID.get() == nullptr ||
         mClosures.front()->mClosure->mKernelID.get() == nullptr) {
         // An invoke should be in a batch by itself, so it conflicts with any other
         // closure.
         return true;
     }
 
-    for (const auto &p : closure->mClosure->mGlobalDeps) {
-        const Closure* dep = p.first;
-        for (CPUClosure* c : mClosures) {
-            if (c->mClosure == dep) {
-                ALOGV("ScriptGroup2: closure %p conflicting with closure %p via its global",
-                      closure, dep);
-                return true;
-            }
+    const auto& globalDeps = closure->mGlobalDeps;
+    const auto& argDeps = closure->mArgDeps;
+
+    for (CPUClosure* c : mClosures) {
+        const Closure* batched = c->mClosure;
+        if (globalDeps.find(batched) != globalDeps.end()) {
+            return true;
         }
-    }
-    for (const auto &p : closure->mClosure->mArgDeps) {
-        const Closure* dep = p.first;
-        for (CPUClosure* c : mClosures) {
-            if (c->mClosure == dep) {
-                for (const auto &p1 : *p.second) {
-                    if (p1.second->get() != nullptr) {
-                        ALOGV("ScriptGroup2: closure %p conflicting with closure %p via its arg",
-                              closure, dep);
-                        return true;
-                    }
+        const auto& it = argDeps.find(batched);
+        if (it != argDeps.end()) {
+            const auto& args = (*it).second;
+            for (const auto &p1 : *args) {
+                if (p1.second->get() != nullptr) {
+                    return true;
                 }
             }
         }
     }
+
     return false;
 }
 
@@ -166,7 +164,7 @@ CpuScriptGroup2Impl::CpuScriptGroup2Impl(RsdCpuReferenceImpl *cpuRefImpl,
 
 #ifndef RS_COMPATIBILITY_LIB
     for (Batch* batch : mBatches) {
-        batch->tryToCreateFusedKernel(mGroup->mCacheDir.c_str());
+        batch->tryToCreateFusedKernel(mGroup->mCacheDir);
     }
 #endif
 }
@@ -356,6 +354,9 @@ void Batch::setGlobalsForBatch() {
                 // which a kernel later reads.
                 continue;
             }
+            rsAssert(p.first != nullptr);
+            ALOGV("Evaluating closure %p, setting field %p (Script %p, slot: %d)",
+                  closure, p.first, p.first->mScript, p.first->mSlot);
             // We use -1 size to indicate an ObjectBase rather than a primitive type
             if (size < 0) {
                 s->setVarObj(p.first->mSlot, (ObjectBase*)value);
@@ -373,8 +374,8 @@ void Batch::run() {
         const CPUClosure* lastCpuClosure = mClosures.back();
 
         firstCpuClosure->mSi->forEachMtlsSetup(
-                (const Allocation**)&firstCpuClosure->mClosure->mArgs[0],
-                firstCpuClosure->mClosure->mArgs.size(),
+                (const Allocation**)firstCpuClosure->mClosure->mArgs,
+                firstCpuClosure->mClosure->mNumArg,
                 lastCpuClosure->mClosure->mReturnValue,
                 nullptr, 0, nullptr, &mtls);
 
@@ -383,8 +384,8 @@ void Batch::run() {
         mtls.kernel = mExecutable->getForEachFunction(0);
 
         mGroup->getCpuRefImpl()->launchThreads(
-                (const Allocation**)&firstCpuClosure->mClosure->mArgs[0],
-                firstCpuClosure->mClosure->mArgs.size(),
+                (const Allocation**)firstCpuClosure->mClosure->mArgs,
+                firstCpuClosure->mClosure->mNumArg,
                 lastCpuClosure->mClosure->mReturnValue,
                 nullptr, &mtls);
 
@@ -406,8 +407,8 @@ void Batch::run() {
         const Closure* closure = cpuClosure->mClosure;
         const ScriptKernelID* kernelID = closure->mKernelID.get();
         cpuClosure->mSi->preLaunch(kernelID->mSlot,
-                                   (const Allocation**)&closure->mArgs[0],
-                                   closure->mArgs.size(), closure->mReturnValue,
+                                   (const Allocation**)closure->mArgs,
+                                   closure->mNumArg, closure->mReturnValue,
                                    cpuClosure->mUsrPtr, cpuClosure->mUsrSize,
                                    nullptr);
     }
@@ -416,8 +417,8 @@ void Batch::run() {
     const Closure* closure = cpuClosure->mClosure;
     MTLaunchStruct mtls;
 
-    if (cpuClosure->mSi->forEachMtlsSetup((const Allocation**)&closure->mArgs[0],
-                                          closure->mArgs.size(),
+    if (cpuClosure->mSi->forEachMtlsSetup((const Allocation**)closure->mArgs,
+                                          closure->mNumArg,
                                           closure->mReturnValue,
                                           nullptr, 0, nullptr, &mtls)) {
 
@@ -432,8 +433,8 @@ void Batch::run() {
         const Closure* closure = cpuClosure->mClosure;
         const ScriptKernelID* kernelID = closure->mKernelID.get();
         cpuClosure->mSi->postLaunch(kernelID->mSlot,
-                                    (const Allocation**)&closure->mArgs[0],
-                                    closure->mArgs.size(), closure->mReturnValue,
+                                    (const Allocation**)closure->mArgs,
+                                    closure->mNumArg, closure->mReturnValue,
                                     nullptr, 0, nullptr);
     }
 }
diff --git a/cpu_ref/rsCpuScriptGroup2.h b/cpu_ref/rsCpuScriptGroup2.h
index 6b816dcd..9ff16c47 100644
--- a/cpu_ref/rsCpuScriptGroup2.h
+++ b/cpu_ref/rsCpuScriptGroup2.h
@@ -1,11 +1,8 @@
 #ifndef CPU_REF_CPUSCRIPTGROUP2IMPL_H_
 #define CPU_REF_CPUSCRIPTGROUP2IMPL_H_
 
-#include <list>
-
 #include "rsd_cpu.h"
-
-using std::list;
+#include "rsList.h"
 
 namespace android {
 namespace renderscript {
@@ -61,7 +58,7 @@ public:
     CpuScriptGroup2Impl* mGroup;
     ScriptExecutable* mExecutable;
     void* mScriptObj;
-    list<CPUClosure*> mClosures;
+    List<CPUClosure*> mClosures;
 };
 
 class CpuScriptGroup2Impl : public RsdCpuReference::CpuScriptGroup2 {
@@ -77,7 +74,7 @@ public:
 private:
     RsdCpuReferenceImpl* mCpuRefImpl;
     const ScriptGroup2* mGroup;
-    list<Batch*> mBatches;
+    List<Batch*> mBatches;
 };
 
 }  // namespace renderscript
diff --git a/rsClosure.cpp b/rsClosure.cpp
index 7aa0acbf..ece92d5a 100644
--- a/rsClosure.cpp
+++ b/rsClosure.cpp
@@ -16,15 +16,15 @@ RsClosure rsi_ClosureCreate(Context* context, RsScriptKernelID kernelID,
                             RsClosure* depClosures, size_t depClosures_length,
                             RsScriptFieldID* depFieldIDs,
                             size_t depFieldIDs_length) {
-  rsAssert(fieldIDs_length == values_length && values_length == sizes_length &&
-           sizes_length == depClosures_length &&
-           depClosures_length == depFieldIDs_length);
-
-  return (RsClosure)(new Closure(
-      context, (const ScriptKernelID*)kernelID, (Allocation*)returnValue,
-      fieldIDs_length, (const ScriptFieldID**)fieldIDs, (const void**)values,
-      sizes, (const Closure**)depClosures,
-      (const ScriptFieldID**)depFieldIDs));
+    rsAssert(fieldIDs_length == values_length && values_length == sizes_length &&
+             sizes_length == depClosures_length &&
+             depClosures_length == depFieldIDs_length);
+
+    return (RsClosure)(new Closure(
+        context, (const ScriptKernelID*)kernelID, (Allocation*)returnValue,
+        fieldIDs_length, (const ScriptFieldID**)fieldIDs, (const void**)values,
+        sizes, (const Closure**)depClosures,
+        (const ScriptFieldID**)depFieldIDs));
 }
 
 RsClosure rsi_InvokeClosureCreate(Context* context, RsScriptInvokeID invokeID,
@@ -39,9 +39,11 @@ RsClosure rsi_InvokeClosureCreate(Context* context, RsScriptInvokeID invokeID,
         sizes));
 }
 
+#if 0
 void rsi_ClosureEval(Context* rsc, RsClosure closure) {
     ((Closure*)closure)->eval();
 }
+#endif
 
 void rsi_ClosureSetArg(Context* rsc, RsClosure closure, uint32_t index,
                        uintptr_t value, size_t size) {
@@ -67,47 +69,59 @@ Closure::Closure(Context* context,
     ObjectBase(context), mContext(context), mKernelID((ScriptKernelID*)kernelID),
     mInvokeID(nullptr), mReturnValue(returnValue), mParams(nullptr),
     mParamLength(0) {
-  size_t i;
+    size_t i;
 
-  for (i = 0; i < (size_t)numValues && fieldIDs[i] == nullptr; i++);
+    for (i = 0; i < (size_t)numValues && fieldIDs[i] == nullptr; i++);
 
-  vector<const void*> args(values, values + i);
-  mArgs.swap(args);
+    mNumArg = i;
+    mArgs = new const void*[mNumArg];
+    memcpy(mArgs, values, sizeof(const void*) * mNumArg);
 
-  for (; i < (size_t)numValues; i++) {
-    mGlobals[fieldIDs[i]] = std::make_pair(values[i], sizes[i]);
-  }
+    for (; i < (size_t)numValues; i++) {
+        rsAssert(fieldIDs[i] != nullptr);
+        mGlobals[fieldIDs[i]] = make_pair(values[i], sizes[i]);
+        ALOGV("Creating closure %p, binding field %p (Script %p, slot: %d)",
+              this, fieldIDs[i], fieldIDs[i]->mScript, fieldIDs[i]->mSlot);
+    }
 
-  mDependences.insert(depClosures, depClosures + numValues);
+    size_t j = mNumArg;
+    for (const auto& p : mGlobals) {
+        rsAssert(p.first == fieldIDs[j]);
+        rsAssert(p.second.first == values[j]);
+        rsAssert(p.second.second == sizes[j]);
+        j++;
+    }
 
-  for (i = 0; i < mArgs.size(); i++) {
-    const Closure* dep = depClosures[i];
-    if (dep != nullptr) {
-      auto mapping = mArgDeps[dep];
-      if (mapping == nullptr) {
-        mapping = new map<int, const ObjectBaseRef<ScriptFieldID>*>();
-        mArgDeps[dep] = mapping;
-      }
-      (*mapping)[i] = new ObjectBaseRef<ScriptFieldID>(
-          const_cast<ScriptFieldID*>(depFieldIDs[i]));
+    // mDependences.insert(depClosures, depClosures + numValues);
+
+    for (i = 0; i < mNumArg; i++) {
+        const Closure* dep = depClosures[i];
+        if (dep != nullptr) {
+            auto mapping = mArgDeps[dep];
+            if (mapping == nullptr) {
+                mapping = new Map<int, const ObjectBaseRef<ScriptFieldID>*>();
+                mArgDeps[dep] = mapping;
+            }
+            (*mapping)[i] = new ObjectBaseRef<ScriptFieldID>(
+                const_cast<ScriptFieldID*>(depFieldIDs[i]));
+        }
     }
-  }
-
-  for (; i < (size_t)numValues; i++) {
-    const Closure* dep = depClosures[i];
-    if (dep != nullptr) {
-      auto mapping = mGlobalDeps[dep];
-      if (mapping == nullptr) {
-        mapping = new map<const ObjectBaseRef<ScriptFieldID>*,
-            const ObjectBaseRef<ScriptFieldID>*>();
-        mGlobalDeps[dep] = mapping;
-      }
-      (*mapping)[new ObjectBaseRef<ScriptFieldID>(
-          const_cast<ScriptFieldID*>(fieldIDs[i]))] =
-          new ObjectBaseRef<ScriptFieldID>(
-              const_cast<ScriptFieldID*>(depFieldIDs[i]));
+
+    for (; i < (size_t)numValues; i++) {
+        const Closure* dep = depClosures[i];
+        if (dep != nullptr) {
+            auto mapping = mGlobalDeps[dep];
+            if (mapping == nullptr) {
+                mapping = new Map<const ObjectBaseRef<ScriptFieldID>*,
+                                  const ObjectBaseRef<ScriptFieldID>*>();
+                mGlobalDeps[dep] = mapping;
+            }
+            (*mapping)[new ObjectBaseRef<ScriptFieldID>(
+                const_cast<ScriptFieldID*>(fieldIDs[i]))] =
+                    new ObjectBaseRef<ScriptFieldID>(
+                        const_cast<ScriptFieldID*>(depFieldIDs[i]));
+        }
     }
-  }
 }
 
 Closure::Closure(Context* context, const ScriptInvokeID* invokeID,
@@ -117,7 +131,7 @@ Closure::Closure(Context* context, const ScriptInvokeID* invokeID,
     ObjectBase(context), mContext(context), mKernelID(nullptr), mInvokeID(invokeID),
     mReturnValue(nullptr), mParams(params), mParamLength(paramLength) {
     for (size_t i = 0; i < numValues; i++) {
-        mGlobals[fieldIDs[i]] = std::make_pair(values[i], sizes[i]);
+        mGlobals[fieldIDs[i]] = make_pair(values[i], sizes[i]);
     }
 }
 
@@ -138,24 +152,8 @@ Closure::~Closure() {
         }
         delete p.second;
     }
-}
-
-void Closure::eval() {
-    Script *s = mKernelID->mScript;
-
-    for (const auto& p : mGlobals) {
-        const void* value = p.second.first;
-        int size = p.second.second;
-        // We use -1 size to indicate an ObjectBase rather than a primitive type
-        if (size < 0) {
-            s->setVarObj(p.first->mSlot, (ObjectBase*)value);
-        } else {
-            s->setVar(p.first->mSlot, (const void*)&value, size);
-        }
-    }
 
-    s->runForEach(mContext, mKernelID->mSlot, (const Allocation **)(&mArgs[0]),
-                  mArgs.size(), mReturnValue, nullptr, 0, nullptr);
+    delete[] mArgs;
 }
 
 void Closure::setArg(const uint32_t index, const void* value, const size_t size) {
@@ -164,7 +162,7 @@ void Closure::setArg(const uint32_t index, const void* value, const size_t size)
 
 void Closure::setGlobal(const ScriptFieldID* fieldID, const void* value,
                         const size_t size) {
-    mGlobals[fieldID] = std::make_pair(value, size);
+    mGlobals[fieldID] = make_pair(value, size);
 }
 
 }  // namespace renderscript
diff --git a/rsClosure.h b/rsClosure.h
index 7f99a570..b14c2aae 100644
--- a/rsClosure.h
+++ b/rsClosure.h
@@ -1,21 +1,13 @@
 #ifndef ANDROID_RENDERSCRIPT_CLOSURE_H_
 #define ANDROID_RENDERSCRIPT_CLOSURE_H_
 
-#include <map>
-#include <set>
-#include <vector>
-
 #include "rsDefines.h"
+#include "rsMap.h"
 #include "rsObjectBase.h"
 
 namespace android {
 namespace renderscript {
 
-using std::map;
-using std::pair;
-using std::set;
-using std::vector;
-
 class Allocation;
 class Context;
 class ObjectBase;
@@ -50,8 +42,6 @@ class Closure : public ObjectBase {
 
     virtual RsA3DClassID getClassId() const { return RS_A3D_CLASS_ID_CLOSURE; }
 
-    void eval();
-
     void setArg(const uint32_t index, const void* value, const size_t size);
     void setGlobal(const ScriptFieldID* fieldID, const void* value,
                    const size_t size);
@@ -68,24 +58,24 @@ class Closure : public ObjectBase {
     // Values referrenced in arguments and globals cannot be futures. They must be
     // either a known value or unbound value.
     // For now, all arguments should be Allocations.
-    vector<const void*> mArgs;
+    const void** mArgs;
+    size_t mNumArg;
 
-    // A global could be allocation or any other data type, including primitive
-    // data types.
-    map<const ScriptFieldID*, pair<const void*, int>> mGlobals;
+    // A global could be allocation or any primitive data type.
+    Map<const ScriptFieldID*, Pair<const void*, size_t>> mGlobals;
 
     Allocation* mReturnValue;
 
     // All the other closures that this closure depends on
-    set<const Closure*> mDependences;
+    // set<const Closure*> mDependences;
 
     // All the other closures which this closure depends on for one of its
     // arguments, and the fields which it depends on.
-    map<const Closure*, map<int, const ObjectBaseRef<ScriptFieldID>*>*> mArgDeps;
+    Map<const Closure*, Map<int, const ObjectBaseRef<ScriptFieldID>*>*> mArgDeps;
 
     // All the other closures that this closure depends on for one of its fields,
     // and the fields that it depends on.
-    map<const Closure*, map<const ObjectBaseRef<ScriptFieldID>*,
+    Map<const Closure*, Map<const ObjectBaseRef<ScriptFieldID>*,
             const ObjectBaseRef<ScriptFieldID>*>*> mGlobalDeps;
 
     const void* mParams;
diff --git a/rsList.h b/rsList.h
new file mode 100644
index 00000000..24720a26
--- /dev/null
+++ b/rsList.h
@@ -0,0 +1,130 @@
+#ifndef ANDROID_RENDERSCRIPT_LIST_H
+#define ANDROID_RENDERSCRIPT_LIST_H
+
+namespace android {
+namespace renderscript {
+
+namespace {
+
+constexpr size_t BUFFER_SIZE = 64;
+
+}  // anonymous namespace
+
+template <class T>
+class List {
+private:
+    class LinkedBuffer {
+    public:
+        LinkedBuffer() : next(nullptr) {}
+
+        union {
+            char raw[BUFFER_SIZE - sizeof(LinkedBuffer*)];
+            T typed;
+        } data;
+        LinkedBuffer* next;
+    };
+
+public:
+    class iterator;
+
+    List() : last(nullptr), first(&firstBuffer.data.typed),
+             beginIterator(this, &firstBuffer, const_cast<T*>(first)),
+             _size(0) {
+        current = const_cast<T*>(first);
+        currentBuffer = &firstBuffer;
+    }
+
+    template <class InputIterator>
+    List(InputIterator first, InputIterator last) : List() {
+        for (InputIterator it = first; it != last; ++it) {
+            push_back(*it);
+        }
+    }
+
+    ~List() {
+        LinkedBuffer* p = firstBuffer.next;
+        LinkedBuffer* next;
+        while (p != nullptr) {
+            next = p->next;
+            delete p;
+            p = next;
+        }
+    }
+
+    void push_back(const T& value) {
+        last = current;
+        *current++ = value;
+        _size++;
+        if ((void*)current >= (void*)&currentBuffer->next) {
+            LinkedBuffer* newBuffer = new LinkedBuffer();
+            currentBuffer->next = newBuffer;
+            currentBuffer = newBuffer;
+            current = &currentBuffer->data.typed;
+        }
+    }
+
+    class iterator {
+        friend class List;
+    public:
+        iterator& operator++() {
+            p++;
+            if ((void*)p >= (void*)&buffer->next) {
+                buffer = buffer->next;
+                if (buffer != nullptr) {
+                    p = &buffer->data.typed;
+                } else {
+                    p = nullptr;
+                }
+            }
+            return *this;
+        }
+
+        bool operator==(const iterator& other) const {
+            return p == other.p && buffer == other.buffer && list == other.list;
+        }
+
+        bool operator!=(const iterator& other) const {
+            return p != other.p || buffer != other.buffer || list != other.list;
+        }
+
+        const T& operator*() const { return *p; }
+
+        T* operator->() { return p; }
+
+    protected:
+        iterator(const List* list_) : list(list_) {}
+        iterator(const List* list_, LinkedBuffer* buffer_, T* p_) :
+            p(p_), buffer(buffer_), list(list_) {}
+
+    private:
+        T* p;
+        LinkedBuffer* buffer;
+        const List* list;
+    };
+
+    const iterator& begin() const { return beginIterator; }
+
+    iterator end() const { return iterator(this, currentBuffer, current); }
+
+    bool empty() const { return current == first; }
+
+    T& front() const { return *const_cast<T*>(first); }
+
+    T& back() const { return *last; }
+
+    size_t size() const { return _size; }
+
+private:
+    T* current;
+    T* last;
+    LinkedBuffer* currentBuffer;
+    LinkedBuffer firstBuffer;
+    const T* first;
+    const iterator beginIterator;
+    size_t _size;
+};
+
+}  // namespace renderscript
+}  // namespace android
+
+#endif  //  ANDROID_RENDERSCRIPT_LIST_H
diff --git a/rsMap.h b/rsMap.h
new file mode 100644
index 00000000..f68b8514
--- /dev/null
+++ b/rsMap.h
@@ -0,0 +1,167 @@
+#ifndef ANDOID_RENDERSCRIPT_MAP_H
+#define ANDOID_RENDERSCRIPT_MAP_H
+
+#include <stddef.h>
+
+namespace android {
+namespace renderscript {
+
+template <class T1, class T2>
+class Pair {
+public:
+    Pair() {}
+    Pair(T1 f1, T2 f2) : first(f1), second(f2) {}
+
+    T1 first;
+    T2 second;
+};
+
+template <class T1, class T2>
+Pair<T1, T2> make_pair(T1 first, T2 second) {
+    return Pair<T1, T2>(first, second);
+}
+
+#define MAP_LOG_NUM_BUCKET 8
+#define MAP_NUM_BUCKET (1 << MAP_LOG_NUM_BUCKET)
+#define MAP_NUM_BUCKET_MASK (MAP_NUM_BUCKET - 1)
+
+template <class KeyType, class ValueType>
+class Map {
+private:
+    typedef Pair<KeyType, ValueType> MapEntry;
+
+    struct LinkNode {
+        MapEntry entry;
+        LinkNode* next;
+    };
+
+public:
+    Map() : endIterator(MAP_NUM_BUCKET, nullptr, this) {
+        for (size_t i = 0; i < MAP_NUM_BUCKET; i++) { bucket[i] = nullptr; }
+    }
+
+    ~Map() {
+        for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
+            LinkNode* p = bucket[i];
+            LinkNode* next;
+            while (p != nullptr) {
+                next = p->next;
+                delete p;
+                p = next;
+            }
+        }
+    }
+
+    ValueType& operator[](const KeyType& key) {
+        const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
+        LinkNode* node = bucket[index];
+        LinkNode* prev = nullptr;
+
+        while (node != nullptr) {
+            if (node->entry.first == key) {
+                return node->entry.second;
+            }
+            prev = node;
+            node = node->next;
+        }
+
+        node = new LinkNode();
+        node->entry.first = key;
+        node->next = nullptr;
+        if (prev == nullptr) {
+            bucket[index] = node;
+        } else {
+            prev->next = node;
+        }
+        return node->entry.second;
+    }
+
+    class iterator {
+        friend class Map;
+    public:
+        iterator& operator++() {
+            LinkNode* next;
+
+            next = node->next;
+            if (next != nullptr) {
+                node = next;
+                return *this;
+            }
+
+            while (++bucket_index < MAP_NUM_BUCKET) {
+                next = map->bucket[bucket_index];
+                if (next != nullptr) {
+                    node = next;
+                    return *this;
+                }
+            }
+
+            node = nullptr;
+            return *this;
+        }
+
+        bool operator==(const iterator& other) const {
+            return node == other.node && bucket_index == other.bucket_index &&
+                    map == other.map;
+        }
+
+        bool operator!=(const iterator& other) const {
+            return node != other.node || bucket_index != other.bucket_index ||
+                    map != other.map;
+        }
+
+        const MapEntry& operator*() const {
+            return node->entry;
+        }
+
+    protected:
+        iterator(size_t index, LinkNode* n, const Map* m) : bucket_index(index), node(n), map(m) {}
+
+    private:
+        size_t bucket_index;
+        LinkNode* node;
+        const Map* map;
+    };
+
+    iterator begin() const {
+        for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
+            LinkNode* node = bucket[i];
+            if (node != nullptr) {
+                return iterator(i, node, this);
+            }
+        }
+
+        return end();
+    }
+
+    const iterator& end() const { return endIterator; }
+
+    iterator begin() { return ((const Map*)this)->begin(); }
+
+    const iterator& end() { return endIterator; }
+
+    iterator find(const KeyType& key) const {
+        const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
+        LinkNode* node = bucket[index];
+
+        while (node != nullptr) {
+            if (node->entry.first == key) {
+                return iterator(index, node, this);
+            }
+            node = node->next;
+        }
+
+        return end();
+    }
+
+private:
+    size_t hash(const KeyType& key) const { return ((size_t)key) >> 4; }
+
+    LinkNode* bucket[MAP_NUM_BUCKET];
+    const iterator endIterator;
+};
+
+}  // namespace renderscript
+}  // namespace android
+
+#endif  // ANDOID_RENDERSCRIPT_MAP_H
diff --git a/rsScriptGroup2.h b/rsScriptGroup2.h
index d4a64a08..92a0f100 100644
--- a/rsScriptGroup2.h
+++ b/rsScriptGroup2.h
@@ -3,8 +3,7 @@
 
 #include "rsScriptGroupBase.h"
 
-#include <list>
-#include <string>
+#include "rsList.h"
 
 namespace android {
 namespace renderscript {
@@ -23,15 +22,15 @@ class ScriptGroup2 : public ScriptGroupBase {
     */
     ScriptGroup2(Context* rsc, const char* cacheDir, Closure** closures,
                  size_t numClosures) :
-        ScriptGroupBase(rsc), mCacheDir(cacheDir),
-        mClosures(closures, closures + numClosures) {}
+        ScriptGroupBase(rsc), mClosures(closures, closures + numClosures),
+        mCacheDir(cacheDir) {}
     virtual ~ScriptGroup2() {}
 
     virtual SG_API_Version getApiVersion() const { return SG_V2; }
     virtual void execute(Context* rsc);
 
-    const std::string mCacheDir;
-    std::list<Closure*> mClosures;
+    List<Closure*> mClosures;
+    const char* mCacheDir;
 };
 
 }  // namespace renderscript