X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=src%2Fvdu.h;fp=src%2Fvdu.h;h=5405a5931c94fd28b3c3b45277fbd82822f0bbf7;hb=ccb17d318604f151217973ef658e151113479d76;hp=0000000000000000000000000000000000000000;hpb=8cf13bb177d92c93eb73dc8939777150536c2d00;p=util-vserver.git

diff --git a/src/vdu.h b/src/vdu.h
new file mode 100644
index 0000000..5405a59
--- /dev/null
+++ b/src/vdu.h
@@ -0,0 +1,374 @@
+#ifndef __VDU_H
+#define __VDU_H
+
+typedef ino64_t KEY;
+typedef KEY *PKEY;
+typedef struct stat64 VAL;
+typedef VAL *PVAL;
+
+static inline
+unsigned int
+HASH(PKEY key){
+    return (int) *key;
+}
+
+static inline
+unsigned int // boolean
+EQUAL(PKEY key1, PKEY key2){
+    return *key1 == *key2;
+}
+
+#ifndef MIN
+#define MIN(x,y) (((x)<(y))?(x):(y))
+#endif // MIN
+
+#ifndef MAX
+#define MAX(x,y) (((x)>(y))?(x):(y))
+#endif // MAX
+
+
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+// hash table support for efficient lookup of duplicate inodes */
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+
+#define Multiplier  (0x9e3779b9)
+#define MaxLogBuckets  (((sizeof (unsigned long))*8) - 2)
+#define MaxBuckets     (1<<MaxLogBuckets)
+#define MinLogBuckets  (4)
+#define MinBuckets     (1<<MinLogBuckets)
+
+// Thresholds for rehashing the table: *)
+// to avoid crazy oscillations, we must have MaxDensity > 2*MinDensity; *)
+// to avoid excessive probes, we must try to keep MaxDensity low. *)
+// Divide by 100 before using
+#define MaxDensity 75 /* max numEntries/NUMBER(buckets) */
+#define MinDensity 20 /* min numEntries/NUMBER(buckets) */
+#define IdealDensity 50
+#define BITSIZE(x) (sizeof(x)*8)
+
+#define NEW(type,num) ((type*)malloc(sizeof(type)*num))
+#define DISPOSE(ptr) (free((void*)ptr))
+
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+// Generic Hash Entry Type
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+
+typedef struct VoidList {
+  struct VoidList *tail;
+} VoidList, *PVoidList;
+
+typedef struct HashTable {
+  PVoidList *buckets;
+  unsigned int numBuckets;    // number of buckets
+  unsigned int minLogBuckets; // minimum value for Log_2(initial size) 
+  unsigned int logBuckets;    // CEILING(Log2(NUMBER(buckets^))) 
+  unsigned int maxEntries;    // maximum number of entries 
+  unsigned int minEntries;    // minimum number of entries 
+  unsigned int numEntries;    // current num of entries in table 
+  PVoidList cache;            // cache of removed elements 
+  int cacheSize;              // current size of the cache 
+  int maxCacheSize;           // maximum size, -1 means unbounded, 0 no cache 
+} HashTable, *PHashTable;
+
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+// Hash Prototypes
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+
+PHashTable
+Init(PHashTable tbl, unsigned int n, int maxCacheSize);
+
+void
+Dispose(PHashTable tbl);
+
+unsigned int
+Log_2(unsigned int x);
+
+void
+NewBuckets(PHashTable tbl, unsigned int logBuckets);
+
+//
+// Generic Hash Table support
+//
+
+PHashTable
+Init(PHashTable tbl, unsigned int n, int maxCacheSize){
+  int idealBuckets;
+  int minBuckets;
+  
+  idealBuckets = MIN(((n*100)/IdealDensity),MaxBuckets);
+  minBuckets = MAX(MinBuckets, idealBuckets);
+  tbl->minLogBuckets = Log_2(minBuckets);
+
+  NewBuckets(tbl, tbl->minLogBuckets);
+  tbl->numEntries = 0;
+  tbl->maxCacheSize = maxCacheSize;
+  tbl->cacheSize = 0;
+  tbl->cache = 0;
+  return tbl;
+} // Init()
+
+
+//
+// Internal procedures
+//
+
+unsigned int
+Log_2(unsigned int x){
+  // return CEILING(LOG_2(x))
+  unsigned int log = 0;
+  unsigned int n= 1;
+
+  assert(x != 0);
+  while ((log < MaxLogBuckets) && (x > n)){
+    log++; 
+    n += n;
+  }
+  return log;
+} // Log_2()
+
+void
+NewBuckets(PHashTable tbl, unsigned int logBuckets){
+  // Allocate "2^logBuckets" buckets.
+  unsigned int numBuckets = 1 << logBuckets;
+  PVoidList *b;
+  unsigned int i;
+
+  tbl->buckets = NEW(PVoidList, numBuckets);
+  tbl->numBuckets = numBuckets;
+  b = tbl->buckets;
+
+  for (i=0; i<tbl->numBuckets; i++){
+    b[i] = NULL;
+  }
+  tbl->logBuckets = logBuckets;
+  tbl->maxEntries = MaxDensity * numBuckets / 100;
+  tbl->minEntries = MinDensity * numBuckets / 100;
+} // NewBuckets()
+
+#ifndef NULL
+#define NULL (void*)0
+#endif // !NULL
+
+#ifndef TRUE
+#define TRUE 1
+#endif // !TRUE
+
+#ifndef FALSE
+#define FALSE 0
+#endif // !FALSE
+
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+// Type specific hash entry
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+typedef struct EntryList {
+  struct EntryList *tail;
+  KEY key;
+  VAL val;
+}EntryList, *PEntryList;
+
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+// Type specific Hash implementation functions
+////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////
+
+static
+void
+Rehash(PHashTable tbl, unsigned int logBuckets) {
+  // Reallocate "2^logBuckets" buckets, and rehash the entries into
+  // the new table.
+
+  PVoidList *oldBucketPointer;
+  PEntryList *ob, obi;
+  PEntryList *nb, *nbh;
+  PEntryList that, tail;
+  unsigned int index; 
+  unsigned int i;
+  unsigned int oldNumBuckets;
+
+  return;
+  assert(logBuckets <= MaxLogBuckets);
+  assert(logBuckets >= tbl->minLogBuckets);
+  oldBucketPointer = tbl->buckets;
+  ob = (PEntryList*)tbl->buckets;
+  oldNumBuckets = tbl->numBuckets;
+
+  NewBuckets(tbl, logBuckets);
+  nb = (PEntryList*)tbl->buckets;
+
+  for(i=0;i<oldNumBuckets;i++){
+    obi = ob[i];
+    that = obi;
+    while (that != NULL) {
+      index = (HASH(&(that->key))*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
+      nbh = &(nb[index]);
+      tail = that->tail;
+      that->tail = *nbh;
+      *nbh = that;
+      that = tail;
+    }
+  }
+  DISPOSE (oldBucketPointer);
+}
+
+static inline
+unsigned int // boolean
+Get(PHashTable tbl, PKEY key, PVAL *val){
+  PEntryList that;
+  unsigned int index;
+
+  index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
+  that = (PEntryList)tbl->buckets[index];
+  while ((that != NULL) && !EQUAL(key,&(that->key))) {
+    that = that->tail;
+  }
+  if (that != NULL){
+    *val = &that->val;
+    return TRUE;
+  }
+  else {
+    return FALSE;
+  }
+} // Get()
+
+static inline 
+unsigned int // boolean
+Put(PHashTable tbl, PKEY key, PVAL *val){
+  PEntryList that;
+  PEntryList *first;
+  unsigned int index;
+  unsigned int res;
+
+  index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
+  first = (PEntryList*)&(tbl->buckets[index]);
+  that = *first;
+  while ((that != NULL) && !EQUAL(key, &(that->key))){
+    that = that->tail;
+  }
+  
+  // found an entry in the hash table given above key
+  if (that != NULL){
+    res = TRUE;
+  }
+  else {
+    // check if we can reuse something from the cache
+    if (tbl->cache != NULL) {
+          that = (PEntryList)tbl->cache;
+          tbl->cache = (PVoidList)tbl->cache->tail;
+          that->key = *key;
+          that->tail = *first;
+          *first = that;
+    }
+    else {
+          that = NEW(EntryList,1);
+	  that->key = *key;
+	  that->tail = *first;
+	  *first = that;
+    }
+    that->val = **val;
+
+    tbl->numEntries++;
+    if ((tbl->logBuckets < MaxLogBuckets)
+	&& (tbl->numEntries > tbl->maxEntries)){
+      Rehash(tbl, tbl->logBuckets + 1); // too crowded
+    }
+    res = FALSE;
+  }
+  *val = &that->val;
+  return res;
+
+} // Put()
+
+static inline
+int
+Delete(PHashTable tbl,PKEY key){
+  PEntryList that, prev;
+  PEntryList *first;
+  unsigned int index;
+
+  index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
+  first = (PEntryList*)&(tbl->buckets[index]);
+  that = *first;
+  prev = NULL;
+
+  while ((that != NULL) && !EQUAL(key, &(that->key))){
+    prev = that;
+    that = that->tail;
+  }
+  if (that != NULL) {
+    if (prev == NULL) {
+      *first = that->tail;
+    }
+    else {
+      prev->tail = that->tail;
+    }
+    if ((tbl->maxCacheSize == -1)||(tbl->cacheSize < tbl->maxCacheSize)) {
+      that->tail = (PEntryList)tbl->cache;
+      tbl->cache = (PVoidList)that;
+      tbl->cacheSize++;
+    }
+    else {
+      DISPOSE (that);
+    }
+    tbl->numEntries--;
+    if (tbl->maxCacheSize == 0) {
+      if ((tbl->logBuckets > tbl->minLogBuckets)
+	  && (tbl->numEntries < tbl->minEntries)) {
+	Rehash(tbl, tbl->logBuckets - 1); // too sparse
+      }
+    }
+    return TRUE;
+  }
+  else {
+    return FALSE;
+  }
+} // Delete()
+
+typedef void (*callback)(PKEY key, PVAL val);
+
+void
+Iterate(PHashTable tbl, callback fn)
+{
+  PVoidList that;
+  unsigned int i;
+  
+  for(i=0;i<tbl->numBuckets;i++) {
+    that = tbl->buckets[i];
+    while ( that != (PVoidList)0 ) {
+      PEntryList entry = (PEntryList)that;
+      fn(&entry->key,&entry->val);
+      that = that->tail;
+    }
+  }
+}
+
+void
+Dispose(PHashTable tbl)
+{
+  PVoidList that, next;
+  unsigned int i;
+
+  for(i=0;i<tbl->numBuckets;i++) {
+    that = tbl->buckets[i];
+    while( that != NULL) {
+        next = that->tail;
+        DISPOSE (that);
+        tbl->numEntries--;
+        that = next;
+    }
+  }
+  DISPOSE(tbl->buckets);
+  assert(tbl->numEntries = 0);
+} // Dispose;
+
+
+
+#endif // __VDU_H