java - Implementing a swap method for an indexable concurrent skip list -

i'm implementing concurrent skip list map based on java's concurrentskiplistmap, differences being want list allow duplicates, , want list indexable (so finding nth element of list takes o(lg(n)) time, instead of o(n) time standard skip list). these modifications aren't presenting problem.

in addition, skip list's keys mutable. example, if list elements integers {0, 4, 7}, middle element's key can changed value in [0, 7] without prompting change list structure; if key changes (-inf, -1] or [8, +inf) element removed , re-added maintain list order. rather implementing removal followed o(lg(n)) insert, implement removal followed linear traversal followed o(1) insert (with expected runtime of o(1) - 99% of time node swapped adjacent node).

inserting new node rare (after startup), , deleting node (without re-adding it) never occurs; of operations elementat(i) retrieve element @ ith index, or operations swap nodes after key modified.

the problem i'm running in how implement key modification class(es). conceptually, i'd like

public class node implements runnable {     private int key;     private node prev, next;     private blockingqueue<integer> queue;      public void update(int i) {         queue.offer(i);     }      public void run() {         while(true) {             int temp = queue.take();             temp += key;             if(prev.getkey() > temp) {                 // remove node, update key temp, perform backward linear traversal, , insert             } else if(next.getkey() < temp) {                 // remove node, update key temp, perform forward linear traveral, , insert             } else {                 key = temp; // node doesn't change position             }         }     } } 

(the insert sub-method being called run uses cas in order handle problem of 2 nodes attempting simultaneously insert @ same location (similar how concurrentskiplistmap handles conflicting inserts) - conceptually same if first node locked nodes adjacent insertion point, except overhead reduced case there's no conflict.)

this way can ensure list in order (it's okay if key update bit delayed, because can update eventually happen; however, if list becomes unordered things might go haywire). problem being implementing list way generate awful lot of threads, 1 per node (with several thousand nodes in list) - of them blocking @ given point in time, i'm concerned several thousand blocking threads still result in high of overhead.

another option make update method synchronized , remove runnable interface node, rather having 2 threads enqueuing updates in node takes care of processing these updates on separate thread, 2 threads instead take turns executing node#update method. problem potentially create bottleneck; if 8 different threads decided update same node @ once queue implementation scale fine, synchronized implementation block 7 out of 8 threads (and block 6 threads, five, etc).

so question is, how implement queue implementation except reduced number of threads, or else how implement synchronized implementation except without potential bottleneck problem.

i think may able solve threadpoolexecutor, like

public class node {     private int key;     private node prev, next;     private concurrentlinkedqueue<integer> queue;     private atomicboolean lock = new atomicboolean(false);     private threadpoolexecutor executor;     private updatenode updater = new updatenode();      public void update(int i) {         queue.offer(i);         if(lock.compareandset(false, true)) {             executor.execute(updater);         }     }      private class updatenode implements runnable {         public void run() {             {                 try {                     int temp = key;                     while(!queue.isempty()) {                         temp += queue.poll();                     }                     if(prev.getkey() > temp) {                         // remove node, update key temp, perform backward linear traversal, , insert                     } else if(next.getkey() < temp) {                         // remove node, update key temp, perform forward linear traveral, , insert                     } else {                         key = temp; // node doesn't change position                     }                 } {                     lock.set(false);                 }             } while (!queue.isempty() && lock.compareandset(false, true));         }     } } 

this way have advantages of queue approach without having thousand threads sitting blocked - instead execute updatenode each time need update node (unless there's updatenode being executed on node, hence atomicboolean that's acting lock), , rely on threadpoolexecutor make inexpensive create several thousand runnables.