emirpasic / gods

GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more
Other
16.3k stars 1.77k forks source link

Is Iterator share state? #186

Closed shindanai-midas closed 2 years ago

shindanai-midas commented 2 years ago

My code have to process with the iterator concurrently

Example

import (
    rbt "github.com/emirpasic/gods/trees/redblacktree"
)

type OrderList struct {
    Name string
    Mu   *sync.Mutex
    List *rbt.Tree // List based on Red Black Tree
}

func (ol *OrderList) GetIterator() rbt.Iterator {
    ol.Mu.Lock()
    defer ol.Mu.Unlock()
    return ol.List.Iterator()
}

Here is my question

it1 := ol.GetIterator()
it2 := ol.GetIterator()

works := []Work{ { It:it1 }, { It:it2 }}

for _, w := range works {
   go func(it rbt.Iterator) {
           for it.Begine(); it.Next(); {
               // Process
        }
  }(w.It)
}

Would it share the same state of the Iterator? Would it make iterator wrong running?

emirpasic commented 2 years ago

@shindanai-midas the mutex is unnecessary here in the GetIterator function. You can generate as many iterators as you want and they are not shared among each other, so mutex here is irrelevant. A new iterator is generated each time you call the Iterator() function and each iterator is independent of one another. An iterator is simply a pointer to the underlying data structure to provide some traversal mechanism.

So I am not sure what it is that you would like to achieve here? To protect the underlying data structure or protect access to the same iterator by multiple go routines?

shindanai-midas commented 2 years ago

@emirpasic I want to protect access to the iterator by multiple goroutines. At first I'm not sure that if I get multiple iterators from the same tree will affected each other while they're traversing concurrently, especially calling Next() function. And as you said

"A new iterator is generated each time you call the Iterator() function and each iterator is independent of one another"

so I knew that it's ok to use iterators concurrently even if it came from the same tree.

Thank you