C 程序--原子

时间：2011-06-04 来源：cpoint

原子是一个指向唯一的、不可改变的0个或任意多个字节序列的指针。大多数原子都是指向以空字符结束的字符串，但是任何一个指向任意字节序列的指针都可以是原子。任何原子只可以出现一次。原子通常被当作数据结构中的关键字使用。 Atom接口：（atom.h）

#ifndef ATOM_INCLUDEED
#define ATOM_INCLUDEED
extern   int Atom_length(const char *str);
extern const char *Atom_new(const char *str,int len);
extern const char *Atom_string(const char *str);
extern const char *Atom_int(long n);
#endif

实现：（atom.c）

#include "atom.h"
#include "limits.h"
#include "mem.h"
#define NELEMS(x) ((sizeof(x))/(sizeof((x)[0])))
static struct atom{
  struct atom *link;
  int len;
  char *str;
}*buckets[2048];


const char *Atom_string(const char *str){
   assert(str);
   return Atom_new(str,strlen(str));
}

const char *Atom_int(long n){
  char str[43];
  char *s=str+sizeof(str);
  unsigned long m;
  if(n==LONG_MIN)
    m=LONG_MAX+1UL;
  else if(n<0)
    m=-n;
  else
    m=n;
  do{

    *--s=m%10+'0';
   }while((m/=10)>0);
  if(n<0)
    *--s='-';
  return Atom_new(s,(str+sizeof(str)-s));
}


const char *Atom_new(const char *str,int len){
   unsigned long h;
   int i;
   struct atom *p;
   assert(str);
   assert(len>=0);
   for(h=0,i=0; i<len; i++)
      h=(h<<1)+scatter[(unsigned char)str[i]];
   h&=NELEMS(buckets)-1;
   for(p=buckets[h];p;p=p->link){
     if(len==p->len){
        for(i=0;i<len&&p->str[i]==str[i];)
          i++;
        if(i==len)
          return p->str;

     }
   p=ALLOC(sizeof(*p)+len+1);
   p->len=len;
   p->str=(char*)(p+1);
   if(len>0)
     memcpy(p->str,str,len);
   p->str[len]='\0';
   p->link=buckets[h];
   buckets[h]=p;

   }

}

int Atom_length(const char *str){

  struct atom *p;
  int i;
  assert(str);
  for(i=0; i<NELEMS(buckets); i++)
     for(p=buckets[i]; p; p=p->link)
       if(p->str==str)
         return p->len;
  assert(0);
  return 0;

}

相关阅读更多 +